Associated Topics || Dr. Math Home || Search Dr. Math

### Least Perimeter

Date: 10/13/2002 at 11:33:45
From: Nathan
Subject: the least perimeter

I cannot find a formula for the least perimeter.

Number of tiles 	Least Perimeter
1                       (3)4
2                       (4)6
3                       (5)8
4                       (4)8
5                       (5)10
6                       (4)10
7                       (5)12
8                       (4)12
9                       (3)12
10                       (4)14
11                       (3)14
12                       (2)14
13                       (3)16
14                       (2)16
15                       (1)16
16                       (2)18
17                       (1)18
18                       (0)18
19                       (-1)18
20                       (-2)18
21                       (-1)20
22                       (-2)20
23                       (-3)20
24                       (-4)20
25                       (-5)20
26                       (-4)22
27                       (-5)22
28                       (-6)22
29                       (-7)22
30                       (-8)22

Can you give me a clue?

Thank you,
- Nathan

Date: 10/13/2002 at 19:50:25
From: Doctor Ian
Subject: Re: The least perimeter

Hi Nathan,

I'm not sure what you mean by 'least perimeter'.  I thought you meant
something like this. Given 4 tiles, here are all the ways they can be
arranged:

+--+--+--+--+
|  |  |  |  |         Perimeter = 10
+--+--+--+--+

+--+--+--+
|  |  |  |           Perimeter = 10
+--+--+--+
|  |
+--+

+--+--+--+
|  |  |  |           Perimeter = 10
+--+--+--+
|  |
+--+

+--+--+
|  |  |              Perimeter = 8
+--+--+
|  |  |
+--+--+

But then for 16 tiles, you have a least perimeter of 18, which is
larger than the perimeter of this arrangement:

+--+--+--+--+
|  |  |  |  |        Perimeter = 16
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+

So before we go any farther, have I misunderstood the concept, or
have you miscalculated some of the values?

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/

Date: 10/25/2002 at 06:22:59
From: Nathan
Subject: The least perimeter

Yes, that is what I meant. Can you help me?

- Nathan

Date: 10/25/2002 at 10:05:36
From: Doctor Ian
Subject: Re: The least perimeter

Hi Nathan,

Trying to draw all the possible cases can get awfully difficult
(especially using a keyboard), but maybe we can look at some
particular cases and determine whether a formula _can_ exist, before
trying to find out what it is.

For a square number,

1 = 1^2
4 = 2^2
9 = 3^3
16 = 4^2

and so on, the smallest perimeter is going to be obtained by
arranging the tiles in a square. And the perimeter is going to be 4
times the square root of the number:

1 tile      p = 4 * sqrt(1) = 4 * 1 =  4

4 tiles     p = 4 * sqrt(4) = 4 * 2 =  8

9 tiles     p = 4 * sqrt(9) = 4 * 3 = 12

But what happens in between? Suppose we have 8 tiles. One way to deal
with this is to start with a square of 9 tiles, and just remove one
from the center. But that opens up the question of what we mean by
'perimter'. Is the perimeter of

###
# #
###

equal to 12 (counting just the outside), or 16 (counting both the
inside and outside surfaces)? Let's assume that we have to pack the
tiles solidly (with no holes) for now, okay?

In that case, our only choice is to remove a tile from the corner:

##
###
###

Interestingly, we get the same perimeter. We've just exchanged an
outside corner for an inside one. This will be the case for any square
that we can construct. So here is what we know so far:

1) For a square number N^2, the least perimeter is 4*N.

2) For N^2-1, the least perimeter isn't greater than 4*N.

This isn't to say that it couldn't be smaller, but we know that it
won't be _larger_ than this.

Note that we can keep chopping tiles off one side of a square without
changing the perimeter:

#####   ####    ##      #
#####   #####   #####   #####
##### = ##### = ##### = #####
#####   #####   #####   #####
#####   #####   #####   #####

So we can say this:

1) For a square number N^2, the least perimeter is 4*N.

2) For N^2-1 down to N^2-(N-1), the least perimeter isn't
greater than 4*N.

But let's look at 8 tiles again. There are other ways that we can
arrange them:

########      perimeter = 2*8 + 2*1 = 18

####          perimeter = 2*4 + 2*2 = 12
####

So for 8, we can't do better by making rectangles.

(Forgive me if I seem to be wandering a little. I've never thought
Depending on how you look at it, that's what makes a problem like
this either frustrating or enjoyable.)

At this point, a question occurs to me: So long as we have two sides
of a square, does it matter what else we do if we stay inside the
boundaries where the other two sides would be?

#####   #         #     #####
#####   ##        #     ##
#####   ###       #     ###
#####   ####     ###    ##
#####   #####   #####   #####

p=20    p=20    p=20    p=28

So it seems to work as long as we keep the shape convex. And that sort
of makes sense. What stays the same is the number of times we have to
move up, down, left, and right. In a convex shape, we can exchange
outside corners for insider corners, and it doesn't matter:

4 5 6        5 6
3 # # #      4 # #
3
2 # # #    2 # # #

1 # # #    1 # # #

We're just taking the same steps in the same order. As long as we
don't have to backtrack (which is what happens in a concave shape),
we aren't adding any extra steps.

So now we have a rule:

1. For K tiles, where K is less than or equal to N^2, the
least perimeter isn't greater than 4*N.

So now we can write a table like this:

Tiles    Smallest N^2     Least perimeter not greater than
-----    ------------     --------------------------------
1           1           4*1

2           4           4*2
3           4           4*2
4           4           4*2

5           9           4*3
6           9           4*3
7           9           4*3
8           9           4*3
9           9           4*3

This should be enough to get you started in thinking about the problem

I'll give you one more thing to think about. Consider a number like
24. We can't arrange 24 tiles in a square, but we can arrange them
into lots of rectangles:

########################   1 x 24     p = 2*1 + 2*24 = 50

############               2 x 12     p = 2*2 + 2*12 = 28
############

########                   3 x 8      p = 2*3 + 2*8  = 22
########
########

######                     4 x 6      p = 2*4 + 2*6  = 20
######
######
######

In general, if you make a rectangle that is (a) tiles by (a+b) tiles,
the perimeter will be

p = 2*a + 2(a+b)

= 2*2 + 2*a + 2*b

= 4*a + 2b

In other words, the rectangle with the smallest perimeter will be the
one that will fit inside the smallest square.

Does this help?

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/

Date: 10/28/2002 at 12:51:48
From: Nathan
Subject: Thank you (The least perimeter)

I would like to thank you for spending so much time on helping me. It
has helped me a lot.

- Nathan
Associated Topics:
High School Puzzles
High School Triangles and Other Polygons
Middle School Puzzles
Middle School Triangles and Other Polygons

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search