Least PerimeterDate: 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 |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/