Ponder This Challenge - December 2003 - Similar dissection of quadrilaterals

Ponder This Challenge:

This month's puzzle is based on a suggestion from R. Nandakumar.

We are interested in the possibility that a given polygon P can be dissected into some finite set of (at least two) mutually similar polygons qi, which we will call "tiles". The tiles qi are similar to each other (each pair qi,qj is related by scaling, rotation, and/or translation), but not necessarily similar to the original P. We will call this a "similar dissection".

Example 1: if P is any triangle, we can dissect it into four smaller triangles qi, each similar to P and congruent to each other, by joining the midpoints of the sides of P.

Example 2: a parallelogram P can be dissected into two triangles by cutting along a diagonal. Further dissect one of those into four smaller triangles. Now the five triangles are similar to each other (but not all congruent), and not similar to P.

Puzzle (Part 1): Show that every trapezoid (quadrilateral ABCD with sides AB and DC parallel, no other assumptions) has a "similar dissection".

Puzzle (Part 2): Exhibit, with proof, a quadrilateral which has no "similar dissection".

A bonus puzzle for your amusement. Please don't send us the answer, and we're not going to publish the answer.

Two players play a game. Fifty coins are in a line; their values are positive numbers known to both players. Player 1 selects and removes either the leftmost or the rightmost coin. Player 2 selects and removes either the leftmost or the rightmost coin from the remaining 49. Continue until all coins are gone. Show that Player 1 has a strategy by which he can accumulate at least half the total value of the coins.

This problem will appear in a forthcoming book Mathematical Puzzles: a Connoisseur's Collection, by Peter Winkler, published by A K Peters, available January 2004.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Solution:

  (Part 1):

  If |AB|=|DC| then P is a parallelogram, which we already solved. Assume |AB| > |DC| (AB is longer than DC). Let h denote the height, the distance between the parallel lines AB and DC. Continue sides AD and BC until they meet at point E, at height g=h*(|AB|)/(|AB|-|DC|) above AB. Draw a line parallel to AB, at distance √{(g-h)*g} = g*√{|DC|/|AB|} from E. This line partitions P into two trapezoids, similar to each other, one larger than the other by a factor √{|AB|/|DC|}.

  (Part 2):

  Let P be a convex quadrilateral whose angles are linearly independent over the rationals; that is, no nontrivial integer linear combination of the four angles gives 0. For concreteness, suppose their measures (in degrees) are

  α1=180/√(5), α-2=180/√(7), α3=180/√(11), α4=360-α1-α2-α3.

  Suppose P admits a "similar dissection" into n tiles, each having k sides. Let the angles of the tile be β1,...,βk, where each βi is strictly between 0 and 360, and none is 180. (A k-gon with an angle of 180 is really a k-1-gon.)

  The dissected polygon has (say) a total of m+r+4 vertices: m interior vertices where the angles of the various tiles sum to 360; r vertices where the angles of the various tiles sum to 180 (these vertices can be on a side of P or on a side of another tile, which would contribute the other 180 degrees); and the four vertices A,B,C,D of the original polygon. Since each tile contributes 180(k-2) degrees, we have

  360*m+180*r+(α1+α2+α3+α4)=180*(k-2)*n, 2*m+r+2=(k-2)*n.

  We have m+r+4 equations, each expressing an angle (αi, 360 or 180) as a nonnegative integer combination of βj. When βj appears in one of these equations, we say that βj is a "component" of the appropriate angle (αi, 360 or 180).

  Suppose first that one of these m interior vertices meets only two tiles, so that two angles sum to 360: βa+βb=360, with βa>βb. So βa>180, and since P is convex, βa is not a component of any αi, nor of any of the r instances of 180. So βa appears n times in our m+r+4 equations, each time as a component of 360. In each of these appearances, if it is not exactly βa+βb=360, but rather βa+(∑ cj βj), we will find another of our equations that contains βb but not βa, and exchange the (∑ cj βj) with the βb, to produce an equation of the form βa+βb=360. Our equations no longer correspond to the dissection, but that's all right.

  If we eliminate the n equations of the form βa+βb=360, and eliminate the two angles βa and βb from our tiles, we come up with a set of (m-n)+r+4 equations relating the k-2 remaining tile-angles. It is as if we had started with (k-2)-gons, m-n vertices of 360, r vertices of 180, and the four angles αi.

  Continue until there is no equation of the form βi+βj=360.

  So we can assume that each of the m equations for 360 involves at least three tile angles (counting multiplicity), and each of the r equations for 180 involves at least two. Among the m+r+4 equations, the number of tile angles (including multiplicity) is then

  n*k ≥ 3*m + 2*r + 4.

  Combine with the earlier equation

  n*(k-2) = 2*m + r + 2,

  (subtracting 3 times the equation from 2 times the inequality)

  to obtain

  n*(6-k) ≥ r+2.

  So k is at most 5.

  Because no linear relation exists among αi, the four equations expressing αi as sums of βj must involve at least four distinct βj. So k must be at least 4.

  If k=4, then from α1+α2+α3+α4=360=β1+β2+β3+β4, we must have αi=βi, i=1,2,3,4. Then r must be 0 (no combination of βi gives 180). Our transformations (to get rid of βa+βb=360) did not change r, nor did they decrease the number of tile angles composing αi, so that in the original dissection we must have had r=0 (no tile vertices along the sides of the large polygon) and each angle αi was just one tile angle. So the dissection was a single tile.

  Suppose k=5. If αi=βi for each i=1,2,3,4, then from ∑ αi=360 and ∑ βi=540 we would have β5=180, impossible. Not all βj are components of αi, since otherwise ∑ αi=360 would be at least ∑ βi=540. So exactly four of the βj are components of αi, and we can write 360=∑ αi=c1*β1+...+c4*β4, with all cj positive integers. One of them, say c1, is at least 2.

  Take one of the occurrences of angle β5, either as one of the m equations expressing 360, or as one of the r equations expressing 180; in the latter case, multiply by 2 to get 360 on the right hand side. We get an equation giving 360 as a nonnegative integer linear combination of β1,...,β5: say 360=d1*β1+...+d5*β5, with d5>0. So we have three equations on the βi:

  c1*β1 + ... + c4*β4 = 360, d1*β1 + ... + d5*β5 = 360, β1 + ... + β5 = 540, with ci and dj nonnegative integers and c1 ≥ 2, c2 ≥ 1, c3 ≥ 1, c4 ≥ 1, d5 ≥ 1.

  Compute (3*d5-2) times the first equation, plus 2 times the second equation, minus (2*d5) times the third equation. The right-hand sides cancel, as do the β5. We are left with the equation f1*β1 + .. + f4*β4 = 0, with fi integers.

  But since (α1,...,α4) are linearly independent over the integers, (β1,...,β4) are also linearly independent, so that fi=0.

  In particular,

  0 = f1 = (3*d5-2)*c1 + 2*d1 - 2*d5.

  The only solution satisfying d5 ≥ 1, c1 ≥ 2, d1 ≥ 0 is d5=1, c1=2, d1=0.

  So we learn that d5=0.

  Now looking at fi, i=2,3,4:

  0 = fi = (3*d5-2)*ci + 2*di - 2*d5 0 = c*i + 2*di - 2.

  The only integer solution with ci ≥ 1 and di ≥ 0 is ci=2, di=0.

  Then β5=360, again impossible.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Dan Dima (12.7.2003 @04:33:54 PM EDT)
• Hagen von Eitzen (12.8.2003 @04:18:10 AM EDT)
• Gyozo Nagy (12.8.2003 @10:30:14 AM EDT)
• Aditya Utturwar (12.8.2003 @02:23:00 PM EDT)
• Kennedy (12.9.2003 @02:21:11 AM EDT)
• Alex Wagner (12.9.2003 @07:15:00 PM EDT)
• Michael Brand (12.9.2003 @02:54:21 PM EDT)
• Algirdas Rascius (12.12.2003 @12:01:00 PM EDT)
• Mark Stubbings (12.15.2003 @08:43:00 AM EDT)
• David Friedman (12.18.2003 @01:44:48 PM EDT)
• John Ritson (12.22.2003 @06:13:07 PM EDT)
• IQSTAR (12.31.2003 @03:30:44 PM EDT)