Friday, March 6, 2009

Solving The Rectangles Problem

I keep posting problems and you do all the solving. I figured I better walk the walk, so I worked on Lee's problem from last week's post. It was really a nice one. The idea was to give the dimensions of five rectangles such that
1) the sides have unique integer dimensions between 1 and 10
2) they can be arranged into a square.

The first thing I did was narrow the size of the possible squares. I did it originally with an area argument. The minimum area of 5 rectangles that meet criteria 1 would be 1*10+2*9+3*8+4*7+5*6 = 110. The max would be 10*9+8*7+6*5+4*3+2*1= 190. So, 110<11^2, 12^2, 13^2<190. That limits the squares I was considering to only three different dimensions. (Later I found another way to argue for these as the only three possibilities.)

I have to admit I had a little more information than you guys did on the blog. Lee is a puzzle maker and he brought in a wood version of one of the solutions to show me. I was playing around with it on my desk one day and found it surprisingly hard to arrange into a square. It took me around 5 minutes to arrange 5 rectangles into a square.



Seeing the correct configuration was the insight that broke the problem for me. The rectangles looked something like this when assembled.



Note that this isn't drawn to scale, but essentially you have one rectangle in the middle with the others spiraling around it. The dimensions of the middle depend on the dimensions you choose for your outer rectangles.


That's when I started playing with me three possible areas.

1) If the overall square is 11 by 11, then what are my options for the inner rectangle. 10 can't be one of the sides of the inner triangle because I have to add two numbers to it to get 11. 9 also can't be it because I'd have to add two one's to it to get 11, and I'm only allowed one one. 8 is the highest possible side of the inner rectangle, because the outer rectangles could have 2 and 1 as sides.

But then since the sides of the whole rectangle are 11, we can fill in...

Now only 3,4,5,6,7 are left, and the only pairs that add to 11 are (5,6) and (4,7). That means 3 has to be the other dimension of the center rectangle.

What two remaining numbers could you add to 3 to get 11? There aren't any. Conclusion: 8 can't be the largest dimension of the inner rectangle. Try 7. And so the process repeats through all possible cases. I really didn't do it that systemattically, but this makes for a better demonstration.

When I got through with the process I only found two solutions: An 11x11 rectangle like this

and a 13x13 like this

At this point, I freaked out. I thought my logic was impeccable but Lee promised 4 solutions. At some point I thought to go back and look at the solution he gave me and saw that the sides were identical to mine, but his solution had flipped two of my sides giving different dimensions to the surrounding four rectangles. I'll show you with the 13x13,

So that's it, Lee also has a solution page on his website check it out. What I want now is a proof that 5 rectangles with unique sides cannot be arranged into a square in any other way (than the way I described above). There has to be a simple topological proof of this. Help?

3 comments:

Tinyc Tim said...

Hendree -

A beautifully described approach to problem solving. The longer I tutor the more I realize how important it is to wait for a student to explain stuff to me because then I know where to take them. Here on the blog the same thing applies: wait till people have had a chance to think about problems and then either react to what others come up with or offer up your own idea. You mention my site. Here's a specific link on it that will take you to the problem at hand.

http://primepuzzle.com/1-31-9.html

- Lee

HM said...

Lee,

I meant to put the link in. Thanks for posting that I just edited the post so it is there for people who don't read the comments.

I hear you about waiting for people to think the problems over. However, with the exception of Paul's sequence problem, I've been getting very few people posting solutions to problems. I thought maybe if I started solving some that that would encourage people. Maybe the best approach might be to post ideas/observations germaine to the problem in the comments. The problem solving might be more collaborative that way. What do think about that?

HM said...

Roger also sent in this nice solution via email. He did it without the additional info I had.

Anyway, first I determined that 11x11, 12x12, and 13x13 were the only feasible square sizes much in the same way yofx did it. That was the end to the similarities (other than the results). Next, starting with 11x11, I began finding combinations of rectangles with a total area of 121. When I'd find one, I'd see if it could make the 11x11 square. In building the square, I always started with the 10x[whatever] piece across the top first and then worked my way around the outside in a clockwise spiral. This seemed to be the easiest way to eliminate certain combinations early (for example: If you had a 10x5 piece, the long side of the 1x[whatever] piece had to be 6 or bigger, otherwise you couldn't fit anything into the narrow space leftover on the right side of the square. Also, 10x1 would not be possible for an 11x11, because you need the 1 to complete the top side of the square.) Eventually, I found the two 11x11 solutions. Next, I tried the 12x12 and I was quickly skeptical that it was going to work. It seemed like any combination that added up to 144 contained a 2x6 in it. Since the 2 would be needed to complete the top side of the square with the 10x[whatever] and there can only be one 6, there was no way to finish the right side with the 2x6 on it. So, I decided to try out the 13x13, finding combinations of 169. I eventually discovered the two 13x13 solutions and there was great rejoicing.