wu :: forums « wu :: forums - 3x1 rectangle to square » Welcome, Guest. Please Login or Register. Dec 9th, 2023, 10:33am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: Grimbal, william wu, SMQ, Eigenray, towr, Icarus, ThudnBlunder)    3x1 rectangle to square « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: 3x1 rectangle to square  (Read 7368 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
 Re: 3x1 rectangle to square   3_1_rectangle_to_square.gif « Reply #2 on: Feb 6th, 2005, 5:39am » Quote Modify

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: 7523
 Re: 3x1 rectangle to square   cut3.jpg « Reply #3 on: Feb 7th, 2005, 3:24am » Quote Modify

 IP Logged

Sir Col
Uberpuzzler

impudens simia et macrologus profundus fabulae

Gender:
Posts: 1825
 Re: 3x1 rectangle to square   « Reply #4 on: Feb 7th, 2005, 6:02am » Quote Modify

You're good! Nicely done, Grimbal.
 IP Logged

mathschallenge.net / projecteuler.net
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
 Re: 3x1 rectangle to square   3x1_Rect.JPG « Reply #6 on: Feb 9th, 2005, 10:35am » Quote Modify

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
 Re: 3x1 rectangle to square   6x1_in6.GIF « Reply #9 on: Feb 10th, 2005, 11:07am » Quote Modify

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:

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
 Re: 3x1 rectangle to square   SqTo8by1.gif « Reply #13 on: Feb 10th, 2005, 6:12pm » Quote Modify

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
 Re: 3x1 rectangle to square   Square_to_3Squares.GIF « Reply #23 on: Feb 14th, 2005, 6:46am » Quote Modify

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
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »