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

        riddles >> medium >> Cutting and translating Triangle into Square
        
(Message started by: Aryabhatta on Jan 5th, 2008, 11:39am)
Title: Cutting and translating Triangle into Square
Post by Aryabhatta on Jan 5th, 2008, 11:39am
Two polygons P1 and P2 of equal area are said to be translationally-equi-dissectible if one of them (say P1) can be cut up (with straight cuts) so that the resulting (polygonal) pieces can be translated to give the other one (P2).

(Note that no rotation/flipping is allowed. Only translation. Also, no overlapping of pieces.)

Show that a triangle and a square (of same area) are not translationally-equi-dissectible.
Title: Re: Cutting and translating Triangle into Square
Post by Hippo on Jan 5th, 2008, 3:12pm
Or show that a triangle with angles 45,45,90 degrees cannot be rotated by 45 degrees by such transformations.
Title: Re: Cutting and translating Triangle into Square
Post by jollytall on Jan 9th, 2008, 12:46am
I am not sure I understand Hippo correctly, but if the question is that a triangle and a square can never be dissectible, then Hippo's example is clearly a counterexample. Cut the square diagonally, and attach two sides together to form a triangle.
So, is the question that there are triangles that cannot be converted to square then it is a different question.
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 9th, 2008, 1:11am
The point is that you are only allowed to translate the pieces, not to rotate them.
Title: Re: Cutting and translating Triangle into Square
Post by Aryabhatta on Jan 9th, 2008, 11:08am

on 01/05/08 at 15:12:51, Hippo wrote:
Or show that a triangle with angles 45,45,90 degrees cannot be rotated by 45 degrees by such transformations.


Just showing this won't be a complete proof.

The problem states that _any_ triangle cannot be converted to a square...
Title: Re: Cutting and translating Triangle into Square
Post by Hippo on Jan 9th, 2008, 1:28pm
I haven't propose a proof ;) I just asked a connected (probably easier) question. But when I thing about it now, it seems to me any parallelogram can be easily transformed to a square. Therefore the angles in the triangle are not important. ... can any triangle be rotated 180 degrees?
... Why have I asked 45 degrees? ... I cannot remember ;). 90 degrees would be more interesting ;).
Title: Re: Cutting and translating Triangle into Square
Post by Joe Fendel on Jan 10th, 2008, 8:50am
For any angle, t, we can define the "net length" of this angle on any polygon (or collection of polygons) by the total length of all sides of the polygon at this angle with the interior on the left, minus the total length of all sides of the polygon at this angle with the interior on the right.

So, for example, suppose we have a triangle defined by the points (0,0), (0,1) and (1,0).  Then for the angle 0 (horizontal-right), we have a net length of 1, and for the angle pi (horizontal-left), we have a net length of -1.  For the angle pi/2 (vertical-up), there is a net length of -1.  For the angle 3pi/4, there is a net length of sqrt(2).

Then simply notice that the net length of t is invariant under dissection (because dissection adds two equal-length sides one with interior on the left and one with interior on the right), translation (angles are unchanged), and fusing (since this is the reverse of dissection).

Also notice that the net length of every angle for a square (or any parallelogram) is 0.  But this is not so for a triangle - every triangle has three angles with nonzero net lengths.  Thus a triangle and square are not translationally-equi-dissectible.

I'm intrigued by the claim that any parallelogram can be transformed into a square ("easily"!).  I see how one can always transform a parallelogram to a rectangle.  But a square?  For example, how does one transform a generalized n*m rectangle into a square of side-length sqrt(nm)?  I can see how to do it for some particular cases, such as 1*4 (that one is easy), or 1*2 (a bit trickier), but I don't see a general method.  (Though this seems like it would be a "classic" problem.)
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 10th, 2008, 9:13am
Transformation of a rectangle to a square:  the method is straightforward once you have seen an example.

Compute the square side size.  It is between the smaller and the longer rectangle dimension.

Cut along a line going from one corner to an opposite long border.  Glue the 2 small corners together.  You now have a parallelogram with one side equal to the wanted square size.  Use that side as one edge of a square covering the parallelogram and extend it to a square grid.  Cut wherever the paralellogram overlaps from one to another square and translate all pieces modulo the grid size into one square.
Title: Re: Cutting and translating Triangle into Square
Post by Hippo on Jan 10th, 2008, 12:49pm

on 01/10/08 at 08:50:21, Joe Fendel wrote:
For any angle, t, we can define the "net length" of this angle on any polygon (or collection of polygons) by the total length of all sides of the polygon at this angle with the interior on the left, minus the total length of all sides of the polygon at this angle with the interior on the right.

So, for example, suppose we have a triangle defined by the points (0,0), (0,1) and (1,0).  Then for the angle 0 (horizontal-right), we have a net length of 1, and for the angle pi (horizontal-left), we have a net length of -1.  For the angle pi/2 (vertical-up), there is a net length of -1.  For the angle 3pi/4, there is a net length of sqrt(2).

Then simply notice that the net length of t is invariant under dissection (because dissection adds two equal-length sides one with interior on the left and one with interior on the right), translation (angles are unchanged), and fusing (since this is the reverse of dissection).

Also notice that the net length of every angle for a square (or any parallelogram) is 0.  But this is not so for a triangle - every triangle has three angles with nonzero net lengths.  Thus a triangle and square are not translationally-equi-dissectible.

I'm intrigued by the claim that any parallelogram can be transformed into a square ("easily"!).  I see how one can always transform a parallelogram to a rectangle.  But a square?  For example, how does one transform a generalized n*m rectangle into a square of side-length sqrt(nm)?  I can see how to do it for some particular cases, such as 1*4 (that one is easy), or 1*2 (a bit trickier), but I don't see a general method.  (Though this seems like it would be a "classic" problem.)


Exactly ... this is invariant I want to describe ;), to the question already answered by Grimbal ... the trick is the square is "rotated". What is no problem as there are 0's for all directions ;)
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 11th, 2008, 12:17am
This brings an interesting question: How can you rotate a square by dissection and rotation translation?
Title: Re: Cutting and translating Triangle into Square
Post by Aryabhatta on Jan 11th, 2008, 1:31am

on 01/11/08 at 00:17:42, Grimbal wrote:
This brings an interesting question: How can you rotate a quare by dissection and rotation?


I don't understand.

Don't dissect, just rotate... or did you mean something else?
Title: Re: Cutting and translating Triangle into Square
Post by Aryabhatta on Jan 11th, 2008, 1:32am

on 01/10/08 at 08:50:21, Joe Fendel wrote:
<snip> proof


Well done!
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 11th, 2008, 6:34am

on 01/11/08 at 01:31:44, Aryabhatta wrote:
Don't dissect, just rotate... or did you mean something else?

Uh... yes, I meant translation, not rotation.

(It's not me, it is my fingers, they type faster than I think!)
Title: Re: Cutting and translating Triangle into Square
Post by Joe Fendel on Jan 11th, 2008, 8:21am

on 01/10/08 at 09:13:09, Grimbal wrote:
Transformation of a rectangle to a square:  the method is straightforward once you have seen an example.

Compute the square side size.  It is between the smaller and the longer rectangle dimension.

Cut along a line going from one corner to an opposite long border.  Glue the 2 small corners together.  You now have a parallelogram with one side equal to the wanted square size.  Use that side as one edge of a square covering the parallelogram and extend it to a square grid.  Cut wherever the paralellogram overlaps from one to another square and translate all pieces modulo the grid size into one square.


Ah, yes.  Thanks, Grimbal.  I see how this works now.

So here's a question: We've established that for polygons P and Q to be translationally-equi-dissectible, necessary conditions are that they have the same:

a) "Net length" for all angles, as defined in my proof above.
b) Area

Are these conditions sufficient?  (This seems like a hard problem to me...)
Title: Re: Cutting and translating Triangle into Square
Post by Joe Fendel on Jan 11th, 2008, 8:32am

on 01/11/08 at 00:17:42, Grimbal wrote:
This brings an interesting question: How can you rotate a square by dissection and rotation translation?


By an arbitrary angle?  Good question!
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 11th, 2008, 9:10am
I think it is sufficient.  Any polygon with zero "net-length" can be reassembled into a square of the same area.

Cut the polygon horizontally through every vertex.  You get trapezoids and triangles of various heights.
Choose a non-vertical angle and collect all pieces having this angle on either side.

Any piece having the angle on both side can be transformed into a rectangle and put aside.

For the remaining pieces, match 2 complementary pieces, glue 2 sides together aligning the bases and cut the top of the higher piece.  You now have one less trapezoid in the set having the chosen angle.
In a finite number of steps, you have no more of that angle left.

Restart with a different angle until you did all angles.  In the process, you have less and less trapezoids and triangles, and more and more rectangles.

In the end, you have only rectangles.

Rectangles can be resized to any other rectangle of the same area, because every rectangle can be transformed into a square of the same area and a square can be rotated.
Using this, transform all the rectangles you have put aside to give them the same width, and pile these to make a square.

QED

This makes so many tiny pieces that it is not practical.  A much simpler dissection can probably always be made by hand.  But it proves that it can always be done.
Title: Re: Cutting and translating Triangle into Square
Post by Hippo on Jan 11th, 2008, 11:56am

on 01/11/08 at 08:21:35, Joe Fendel wrote:
Ah, yes.  Thanks, Grimbal.  I see how this works now.

So here's a question: We've established that for polygons P and Q to be translationally-equi-dissectible, necessary conditions are that they have the same:

a) "Net length" for all angles, as defined in my proof above.
b) Area

Are these conditions sufficient?  (This seems like a hard problem to me...)


I wanted to stay new riddle ... "contradicting" your question ;) ... proove that disc cannot be transformed to a square. ... Both have "directed integral in-out differences" equal 0.

[hide]I suppose the invariant using "second derivative instead first" should be used.[/hide]

... I am leaving for a week ... so hope an exactly formulated proof will be formed during it. ;)

Actually this is not contradicting as only finite number of angles are expected in your riddle ;)
Title: Re: Cutting and translating Triangle into Square
Post by Aryabhatta on Jan 11th, 2008, 2:22pm
Hippo, If i remember correctly, someone has shown that we can transform the circle into a square. (but i am not sure what kind of transforms were allowed, but they had something to do with dissection)

Let me edit this post later, when I get my hands on the book which has the reference.
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 12th, 2008, 3:24am
There is a nice solution for a 12-gon.
i.e. dissect a 12-gon into a square.  But you can rotate the pieces.
Title: Re: Cutting and translating Triangle into Square
Post by towr on Jan 12th, 2008, 5:16am

on 01/11/08 at 14:22:15, Aryabhatta wrote:
Hippo, If i remember correctly, someone has shown that we can transform the circle into a square.
Yes, and you can even dissect it and put it back together to form two circles that are the same size as the original. ;D
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 12th, 2008, 10:09am
I read that about a ball.
You can dissect a ball into 4 pieces that can be recombined (with rotations) to form 2 balls of the original size.

I didn't know you can do that with disks or transform a square into a ball.  Do you have a reference?
Title: Re: Cutting and translating Triangle into Square
Post by ThudanBlunder on Jan 12th, 2008, 11:08am

on 01/12/08 at 05:16:53, towr wrote:
Yes, and you can even dissect it and put it back together to form two circles that are the same size as the original. ;D
3D circles?   :P


on 01/12/08 at 10:09:46, Grimbal wrote:
I read that about a ball.
You can dissect a ball into 4 pieces that can be recombined (with rotations) to form 2 balls of the original size.?

Banach-Tarski (http://en.wikipedia.org/wiki/Banach-Tarski_paradox) requires countably many pieces.  
Title: Re: Cutting and translating Triangle into Square
Post by Icarus on Jan 12th, 2008, 11:17am
It requires a minimum of 5 pieces (at least, according to the best result I've heard of), although one of those pieces is a single point.

The most general form of the Banach-Tarski paradox says that for any two sets in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gif3 with non-empty interior, it is possible to divide one into a finite number of subsets which when rigidly transformed will recombine to form the other.

Note, though, that this requires 3 dimensions. The same thing is not possible in 2 dimensions. It is possible to extend the concept of area to all sets, provided that you only require finite additivity (the area of the union of any two disjoint sets is the sum of their areas, but there exist infinite collections of pairwise-disjoint sets for which the area of the union is not the sum of the individual areas). [edit](I also should add that there are infinitely many such extensions with nothing to suggest one is better than another, which is why normally we stick with just the sets for which area has a natural definition.)[/edit]

So towr's comment can only be true if his dissection is infinite.

[Edit] T&B: Check again - Banach-Tarski uses a finite number of pieces. Though I suppose finite is countable...[/Edit]
Title: Re: Cutting and translating Triangle into Square
Post by ThudanBlunder on Jan 12th, 2008, 3:09pm

on 01/12/08 at 11:17:30, Icarus wrote:
[Edit] T&B: Check again - Banach-Tarski uses a finite number of pieces. Though I suppose finite is countable...[/Edit]

Welcome back, Icarus.

My understanding is that it requires a countably infinite number of non-measurable pieces.

If a finite number of pieces is sufficient, why is AC (http://en.wikipedia.org/wiki/Axiom_of_choice) an essential part of the proof?
Title: Re: Cutting and translating Triangle into Square
Post by Grimbal on Jan 12th, 2008, 3:15pm
The axiom of choice is necessary to decide for each orbit where to cut it to distribute its points over the various pieces.
Title: Re: Cutting and translating Triangle into Square
Post by Icarus on Jan 18th, 2008, 8:37pm
The axiom of choice is necessary to pick the points that make up each of the partitions, but the number of partitions is finite.

At least two of the partitions have to be unmeasurable, since otherwise the additivity of set measure would make the result impossible. If Banach-Tarski didn't involve the axiom of choice, then it would provide a non-AC proof of unmeasurable sets.

In two dimensions, you are correct. The two-dimensional equivalent to Banach-Tarski requires an infinite number of partitions in order for area not to be preserved. This, however, doesn't really justify the name "paradox", as you expect things to break down once infinite numbers are involved.

The 3 (and higher) dimensional Banach-Tarski theorem is called a "paradox" exactly because it violates all our intuition by changing volume with only a finite number of pieces. It proves as well that we cannot extend the idea of volume to all sets, even if we are willing to sacrifice infinite additivity of volumes. In 2 dimensions this is possible - though not in any natural way.
Title: Re: Cutting and translating Triangle into Square
Post by Hippo on Jan 19th, 2008, 12:30pm
It does not surprise me that uncountable number of cuts is sufficient to transform the disk to square (of the same area). The same would work for triangle square transform.
But countable number of cuts (countable number of connected pieces without holes ... any 2 points of the piece are connected by open polygon entirely in the piece and an interior of a closed polygon entirely lying in the piece entirely lies in the piece, too) seems to me to be unsufficient.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board