wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 3x1 rectangle to square
        
(Message started by: JocK on Feb 5^th, 2005, 3:34pm)

Title: 3x1 rectangle to square
Post by JocK on Feb 5^th, 2005, 3:34pm

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?

Title: Re: 3x1 rectangle to square
Post by Eigenray on Feb 5^th, 2005, 4:06pm

[link=http://mathworld.wolfram.com/Wallace-Bolyai-GerwienTheorem.html]Yes[/link]! Well, I don't know if I can. But someone could. Well, that answers the first question.

Title: Re: 3x1 rectangle to square
Post by Sir Col on Feb 6^th, 2005, 5:39am

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.

Title: Re: 3x1 rectangle to square
Post by Grimbal on Feb 7^th, 2005, 3:24am

Title: Re: 3x1 rectangle to square
Post by Sir Col on Feb 7^th, 2005, 6:02am

You're good! Nicely done, Grimbal. 8)

Title: Re: 3x1 rectangle to square
Post by JocK on Feb 7^th, 2005, 2:57pm

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²) = 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?

Title: Re: 3x1 rectangle to square
Post by Barukh on Feb 9^th, 2005, 10:35am

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.

Title: Re: 3x1 rectangle to square
Post by JocK on Feb 9^th, 2005, 2:26pm

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_medium;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
...

Title: Re: 3x1 rectangle to square
Post by towr on Feb 9^th, 2005, 3:13pm

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.

Title: Re: 3x1 rectangle to square
Post by Barukh on Feb 10^th, 2005, 11:07am

on 02/09/05 at 14:26:09, 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 02/09/05 at 15:13:15, 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?

Title: Re: 3x1 rectangle to square
Post by towr on Feb 10^th, 2005, 11:28am

on 02/10/05 at 11:07:22, 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.

Title: Re: 3x1 rectangle to square
Post by towr on Feb 10^th, 2005, 11:32am

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

Title: Re: 3x1 rectangle to square
Post by Sir Col on Feb 10^th, 2005, 1:55pm

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!

Title: Re: 3x1 rectangle to square
Post by SWF on Feb 10^th, 2005, 6:12pm

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.

Title: Re: 3x1 rectangle to square
Post by towr on Feb 11^th, 2005, 12:41am

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.

Title: Re: 3x1 rectangle to square
Post by Barukh on Feb 11^th, 2005, 4:14am

This is absolutely brilliant, towr!

:D

Title: Re: 3x1 rectangle to square
Post by JocK on Feb 11^th, 2005, 10:26am

Towr's extension of the Lindgren-Barukh-dissection very elegantly answers the questions posed: an r x 1 rectangle with (n-1)² < r < n² 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?

Title: Re: 3x1 rectangle to square
Post by Barukh on Feb 11^th, 2005, 11:18pm

on 02/11/05 at 10:26:24, 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.

Title: Re: 3x1 rectangle to square
Post by towr on Feb 12^th, 2005, 1:13pm

on 02/11/05 at 10:26:24, 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.

Title: Re: 3x1 rectangle to square
Post by Barukh on Feb 13^th, 2005, 11:31pm

on 02/12/05 at 13:13:00, 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1107718071) thread).

Title: Re: 3x1 rectangle to square
Post by towr on Feb 14^th, 2005, 12:03am

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.

Title: Re: 3x1 rectangle to square
Post by Barukh on Feb 14^th, 2005, 2:02am

on 02/14/05 at 00:03:18, 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.

Title: Re: 3x1 rectangle to square
Post by towr on Feb 14^th, 2005, 3:33am

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 )

Title: Re: 3x1 rectangle to square
Post by Barukh on Feb 14^th, 2005, 6:46am

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

Title: Re: 3x1 rectangle to square
Post by towr on Feb 14^th, 2005, 8:11am

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)

Title: Re: 3x1 rectangle to square
Post by JocK on Feb 14^th, 2005, 11:19am

Nice concerted effort for the easier problem (all squares allowed to be differently sized). Only one case can be improved I think.

Title: Re: 3x1 rectangle to square
Post by towr on Feb 14^th, 2005, 2:02pm

duh, yeah.. 7 = 3+4
Cut the square in 4, then cut one of the smaller squares in 4 again.