Author 
Topic: 3x1 rectangle to square (Read 7600 times) 

JocK
Uberpuzzler
Gender:
Posts: 877


3x1 rectangle to square
« on: Feb 5^{th}, 2005, 3:34pm » 
Quote Modify

Can you dissect a 3x1 rectangle such that you can form a square of area 3 from the pieces? What is the minimum number of pieces you need to do so?


IP Logged 
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: 3x1 rectangle to square
« Reply #1 on: Feb 5^{th}, 2005, 4:06pm » 
Quote Modify

Yes! Well, I don't know if I can. But someone could. Well, that answers the first question.


IP Logged 



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825

I haven't managed to solve it yet, but maybe what I've done so far can inspire someone else to finish it... Diagram 1: Start by removing a unit square. Draw unit circle from right side of 2x1 rectangle. Draw tangent from bottom right of rectangle to circle: this completes the construction of a (red) right triangle with one leg equal to [sqrt]3 (thick side). Diagram 2: Remove the green and yellow regions, translating them to the locations shown. Diagram 3: Use a circle to complete the construction of a 3 square (thick lines). Remove and translate blue triangle. Reinsert unit square. Diagram 4: We know that the grey regions are congruent, but we need to show how it is possible to remove the grey region outside the 3 square and dissect it to fill the grey region inside the 3 square in a finite number of steps.

« Last Edit: Feb 6^{th}, 2005, 5:40am by Sir Col » 
IP Logged 
mathschallenge.net / projecteuler.net



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527



IP Logged 



JocK
Uberpuzzler
Gender:
Posts: 877


Re: 3x1 rectangle to square
« Reply #5 on: Feb 7^{th}, 2005, 2:57pm » 
Quote Modify

Wow... well done Grimbal! You might want to try the general case: dissecting a Nx1 rectangle in as few pieces as possible such that the pieces can be rearranged into a [sqrt]N x [sqrt]N square. Let's note the minimum number of pieces for a Nx1 rectangle as P(N). Given Grimbal's solution, we can start filling out a table of P(N) values: N P(N) 1 1 2 3 3 4 4 2 5 ? 6 ? 7 ? 8 ? 9 3 ... Can you fill in the missing values? Obviously, P(n^{2}) = n. Is it true that P(N) [ge] [sqrt]N for all N [in] [bbn]? What can you say about the behaviour of P(N)/[sqrt]N when N grows without bound?

« Last Edit: Feb 7^{th}, 2005, 3:03pm by JocK » 
IP Logged 
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



Barukh
Uberpuzzler
Gender:
Posts: 2276

The 3x1 rectangle can be dissected to only 3 pieces to form a square. The same dissection may be used for every rectangle r:1, where 1 < r < 4 (r not necessarily an integer). 5:1 rectangle can be done with 4 pieces.


IP Logged 



JocK
Uberpuzzler
Gender:
Posts: 877


Re: 3x1 rectangle to square
« Reply #7 on: Feb 9^{th}, 2005, 2:26pm » 
Quote Modify

Truly amazing, and the best that can happen when you post a problem: someone comes with a solution that beats your own..! This 3piece construction (a big triangle with sides 1, [sqrt]3, 2; a small triangle with sides 3[sqrt]3, [sqrt]31, 2[sqrt]32; and a rectangle with sides [sqrt]3 and 1 that has a corner missing) indeed seems to work. Very well done Barukh! How did you arrive at this solution? You are also right about the fact that a 5x1 rectangle can be dissected into 4 pieces forming a square (SWF's solution in the thread http://www.ocf.berkeley.edu/~wwu/cgibin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1107643164 should direct you to the right pattern). Time to update the table.... N P(N) 1 1 2 3 3 3 (!!) 4 2 5 4 6 ? 7 ? 8 ? 9 3 ...

« Last Edit: Feb 9^{th}, 2005, 3:13pm by JocK » 
IP Logged 
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #8 on: Feb 9^{th}, 2005, 3:13pm » 
Quote Modify

So [lceil][sqrt]n + 1[rceil] for nonsquares it is then.. To be honest, it should have struck me the first time I read Barukhs post.

« Last Edit: Feb 9^{th}, 2005, 3:26pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Barukh
Uberpuzzler
Gender:
Posts: 2276

on Feb 9^{th}, 2005, 2:26pm, JocK wrote:Very well done Barukh! How did you arrive at this solution? 
 You give me too much credit, JocK. I read about this solution in a book “Recreational Problems in Geometric Dissections” by H. Lindgren (ed. 1972). on Feb 9^{th}, 2005, 3:13pm, towr wrote:So [lceil][sqrt]n + 1[rceil] for nonsquares it is then.. 
 According to this formula, P(6) = 4, but I have found only 6 pieces… Has anybody got better solution?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #10 on: Feb 10^{th}, 2005, 11:28am » 
Quote Modify

on Feb 10^{th}, 2005, 11:07am, Barukh wrote:According to this formula, P(6) = 4, but I have found only 6 pieces… Has anybody got better solution? 
 Try one piece of 1 x [sqrt]6 and then finish off by disecting the 1 x (6[sqrt]6) rectangle into a [sqrt]6 x ([sqrt]61) rectangle via your earlier method.

« Last Edit: Feb 10^{th}, 2005, 11:29am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #11 on: Feb 10^{th}, 2005, 11:32am » 
Quote Modify

btw, is there some sort of special program your are using to draw this stuff? Cause it doesn't look like just mspaint.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: 3x1 rectangle to square
« Reply #12 on: Feb 10^{th}, 2005, 1:55pm » 
Quote Modify

Like me, he's using Geometer's Sketchpad. You can find out more about it here: http://www.keypress.com/sketchpad/ It is an outstanding piece of software that doesn't just allow you to draw very accurate constructions, but you can dynamically adjust points to observe the effects, as well as perform a variety of transformations. Highly recommended!


IP Logged 
mathschallenge.net / projecteuler.net



SWF
Uberpuzzler
Posts: 879

Here is a method that will never fail to produce a dissection, but evidently does not always give the minimum possible. The example shown is for the 8x1 rectangle using 5 pieces. Starting with a square of side sqrt(N), make the yellow right triangle of dimesion sqrt(N) by sqrt(N/(N1)) by N/sqrt(N1). Fill the square with lines parallel to the hypotenuse of the yellow triangle distance of 1 apart. Construct the little orange right triangle. This method will require 2+ceil(sqrt(N1)) pieces. As N gets large, the square will end up sliced into a bunch of strips, many of them parallelograms that can be lined up end to end.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #14 on: Feb 11^{th}, 2005, 12:41am » 
Quote Modify

Assume N isn't square, then let k = [lfloor][sqrt]N1[rfloor] = [lceil][sqrt]N2[rceil] First disect the 1 x N rectangle into k rectangular pieces of 1 x [sqrt]N, and use the remaining 1 x (N  k [sqrt]N) rectangle to create 3 more pieces which form a [sqrt]N x ([sqrt]Nk) rectangle. Together those k + 3 = [lceil][sqrt]N+1[rceil] pieces form the square. Since 1 < ([sqrt]Nk) < 2 this can always be done.

« Last Edit: Feb 11^{th}, 2005, 12:50am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3x1 rectangle to square
« Reply #15 on: Feb 11^{th}, 2005, 4:14am » 
Quote Modify

This is absolutely brilliant, towr!


IP Logged 



JocK
Uberpuzzler
Gender:
Posts: 877


Re: 3x1 rectangle to square
« Reply #16 on: Feb 11^{th}, 2005, 10:26am » 
Quote Modify

Towr's extension of the LindgrenBarukhdissection very elegantly answers the questions posed: an r x 1 rectangle with (n1)^{2} < r < n^{2} can be dissected into n+1 pieces that form a square. A related question might now be answered as well: what is the mimimum number of pieces you need when dissecting a square such that you can rearrange the pieces into N eqally sized squares? What if you relax the conditions a bit: how many pieces do you need such that you can form N squares not necesarily of the same size?


IP Logged 
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3x1 rectangle to square
« Reply #17 on: Feb 11^{th}, 2005, 11:18pm » 
Quote Modify

on Feb 11^{th}, 2005, 10:26am, JocK wrote:Towr's extension of the LindgrenBarukhdissection 
 Frankly speaking, this dissection was proposed by Henry Dudeney  one of the greatest puzzlists of all time  almost a century ago.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #18 on: Feb 12^{th}, 2005, 1:13pm » 
Quote Modify

on Feb 11^{th}, 2005, 10:26am, JocK wrote:What if you relax the conditions a bit: how many pieces do you need such that you can form N squares not necesarily of the same size? 
 For even > 2 and uneven >7, you can trivially do it in N. Take 1, resp. 4, squares in the bottom left, and surround it by N1, resp. N4, equally sized squares on the right and top. So that leaves 2,3,5 and 7 as more interesting cases.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3x1 rectangle to square
« Reply #19 on: Feb 13^{th}, 2005, 11:31pm » 
Quote Modify

on Feb 12^{th}, 2005, 1:13pm, towr wrote:So that leaves 2,3,5 and 7 as more interesting cases. 
 I think for N=2, the best we can do is 4 pieces: two diagonal dissections give 4 right triangles that may be rearranged into two equal squares. Here’s my “argument” why less is impossible: we need 5 pieces to make two arbitrary squares out of one (see the Pythagorean dissection thread).


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #20 on: Feb 14^{th}, 2005, 12:03am » 
Quote Modify

For N=3,5,7 we can also do at least as well as [lceil][sqrt]N+N[rceil] (by first transforming it to a rectangle with aspect ratio 1:N, then cutting into N pieces) Note that this also gives an upper bound for cutting a square into any number of equal sized squares. So we should be able to save some, I think, for this easier problem.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3x1 rectangle to square
« Reply #21 on: Feb 14^{th}, 2005, 2:02am » 
Quote Modify

on Feb 14^{th}, 2005, 12:03am, towr wrote:For N=3,5,7 we can also do at least as well as [lceil][sqrt]N+N[rceil] (by first transforming it to a rectangle with aspect ratio 1:N, then cutting into N pieces) 
 I doubt it’s as simple as that: the second series will contain N1 cuts. Every such cut may split more than one piece from the first series, so theoretically we can end with more pieces. For instance, take N=3 and refer to the drawing in my post #6: after cutting the square into 3 pieces, one of the cuts parallel to the short edge of the rectangle will go through 2 pieces, and so we will end with 6 pieces overall. As far as I know, that’s the best for the equalsized squares.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #22 on: Feb 14^{th}, 2005, 3:33am » 
Quote Modify

You're right. However, each cut after forming the rectangle goes at most through two other pieces, and then only for the last pieces at one of the end (the rest are all rectangles). So the upper bound becomes [lceil][sqrt]N[rceil] + N + [lceil]2[sqrt]N[rceil] (The part where you can cut through two pieces is smaller than 2 [sqrt]N )

« Last Edit: Feb 14^{th}, 2005, 3:35am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Barukh
Uberpuzzler
Gender:
Posts: 2276

The case N=3 can be done with 4 pieces (I think that's minimal).


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3x1 rectangle to square
« Reply #24 on: Feb 14^{th}, 2005, 8:11am » 
Quote Modify

It better well be minimal, otherwise we could cut it into three squares directly (which for obvious reasons is impossible). In a similar way 5 can be done in 6 cuts _________     _______  ___    ________ And likewise 7 can be done in 8. (again, make the big square bigger, and add two small squares topleft and bottomright)

« Last Edit: Feb 14^{th}, 2005, 8:12am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



