Author |
Topic: 3x1 rectangle to square (Read 7496 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
3x1 rectangle to square
« on: Feb 5th, 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.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 3x1 rectangle to square
« Reply #1 on: Feb 5th, 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 6th, 2005, 5:40am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: 3x1 rectangle to square
« Reply #5 on: Feb 7th, 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(n2) = 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 7th, 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.
xy - y = x5 - y4 - y3 = 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 9th, 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 3-piece construction (a big triangle with sides 1, [sqrt]3, 2; a small triangle with sides 3-[sqrt]3, [sqrt]3-1, 2[sqrt]3-2; 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/cgi-bin/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 9th, 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.
xy - y = x5 - y4 - y3 = 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 9th, 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 9th, 2005, 3:26pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
on Feb 9th, 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 9th, 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 10th, 2005, 11:28am » |
Quote Modify
|
on Feb 10th, 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]6-1) rectangle via your earlier method.
|
| « Last Edit: Feb 10th, 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 10th, 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 ms-paint.
|
|
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 10th, 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/(N-1)) by N/sqrt(N-1). 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(N-1)) 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 11th, 2005, 12:41am » |
Quote Modify
|
Assume N isn't square, then let k = [lfloor][sqrt]N-1[rfloor] = [lceil][sqrt]N-2[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]N-k) rectangle.
Together those k + 3 = [lceil][sqrt]N+1[rceil] pieces form the square.
Since 1 < ([sqrt]N-k) < 2 this can always be done.
|
| « Last Edit: Feb 11th, 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 11th, 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 11th, 2005, 10:26am » |
Quote Modify
|
Towr's extension of the Lindgren-Barukh-dissection very elegantly answers the questions posed: an r x 1 rectangle with (n-1)2 < r < n2 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.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 3x1 rectangle to square
« Reply #17 on: Feb 11th, 2005, 11:18pm » |
Quote Modify
|
on Feb 11th, 2005, 10:26am, JocK wrote:| Towr's extension of the Lindgren-Barukh-dissection |
|
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 12th, 2005, 1:13pm » |
Quote Modify
|
on Feb 11th, 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 N-1, resp. N-4, 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 13th, 2005, 11:31pm » |
Quote Modify
|
on Feb 12th, 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 14th, 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 14th, 2005, 2:02am » |
Quote Modify
|
on Feb 14th, 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 N-1 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 equal-sized 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 14th, 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 14th, 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 14th, 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 14th, 2005, 8:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print