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 
about this problem before, so I may go down some blind alleys.  
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 
more on your own. 

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