Ponder This Challenge - June 2003 - Partitioning a square into rectangles

Ponder This Challenge:

This month's puzzle was proposed by Harry Nelson and sent in by John G. Fletcher.

Partition a unit square into N > 1 mutually non-congruent rectangles, all of the same area 1/N. For what values of N is this possible?

Clarification: A complete solution will give an implicit list of all the values of N for which it is possible, a clear way of constructing such a partition, and a numerical example for least such value of N.

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

  We began by seeking a solution for the least possible value of N, first determining its topology. Clearly two adjacent rectangles cannot have sides that exactly coincide, since then the two equal rectangles would be congruent. Also, we can assume that no rectangle has a side of 1, because then the other rectangles would exhibit an acceptable topology for a smaller N. Exhaustively considering cases, one finds only the following three possible topologies for N <= 7: where the labels refer to lengths of segments of the sides of the rectangles. The requirement of equal areas yields N equations in N+1 unknowns:

  (0) 5a = 1/(x+y) , (1) 7a = 1/(w+x+y) , (2) 7a = 1/(w+x+y) ,
  5(b+c) = 1/x , 7(b+c) = 1/w , 7b = 1/(w+x) ,
  5b = 1/y , 7d = 1/(w+x) , 7(c+d) = 1/w ,
  5c = 1/(y+z) , 7b = 1/(x+y) , 7c = 1/x ,
  5(a+b) = 1/z ; 7c = 1/x , 7d = 1/(x+y+z) ,
  7(c+d) = 1/(y+z) , 7(b+c) = 1/y
  7(a+b) = 1/z ; 7(a+b+c) = 1/z .

  One may eliminate a, b, c, and (except in case (0)) d from the above to obtain the homogeneous equations

  (0) 1/y + 1/(y+z) = 1/x ,
  1/(x+y) + 1/y = 1/z ;

  (1) 1/(x+y) + 1/x = 1/w ,
  1/x + 1/(w+x) = 1/(y+z) ,
  1/(w+x+y) + 1/(x+y) = 1/z ;

  (2) 1/x + 1/(x+y+z) = 1/w ,
  1/(w+x) + 1/x = 1/y ,
  1/(w+x+y) + 1/(w+x) + 1/x = 1/z .

  Solving first (except in case (0)) for w and then for z and then eliminating these, one finds

  (0) z = y(x + y)/(x + 2y) ,
  x**2 + xy -y**2 = 0 ;

  (1) w = x(x + y)/(2x + y) ,
  z = (x + y)(3x + y)/(5x + 2y) ,
  y(38x**2 + 38xy + 9y**2) = 0 ;

  (2) w = x(2y - x)/(x - y) ,
  z = y(2x - y)/(3x - 2y) ,
  (x + y)(9x**2 - 20xy + 9y**2) = 0 .

  In case (0) it follows that z = x, making some of the rectangles congruent.

  The last equation for case (1) means either that y = 0 or that either x or y is negative. All of these alternatives are unacceptable, as is the alternative y = -x for case (2).

  So using the second factor in the last equation for case (2), one may solve for y in terms of x and then use that result together with the other 6 independent equations for case (2) and an 8th equation,

  w + x + y + z = 1 ,
  to find, where Q = +sqrt(19),

  w = (8-Q)/15 = 0.242740 , a = (8-Q)/21 = 0.173386 ,
  x = (1+Q)/15 = 0.357260 , b = 5/21 = 0.238095 ,
  y = (-1+Q)/15 = 0.223927 , c = 5(-1+Q)/42 = 0.399869 ,
  z = (7-Q)/15 = 0.176073 , d = (7-Q)/14 = 0.188650 ,

  yielding rectangles with (vertical by horizontal) sides

  (8+Q)/15 by (8-Q)/21 , 3/5 by 5/21 ,
  (8-Q)/15 by (8+Q)/21 , (1+Q)/15 by 5(-1+Q)/42 ,
  (7+Q)/15 by (7-Q)/14 , (-1+Q)/15 by 5(1+Q)/42 , and
  (7-Q)/15 by (7+Q)/14 .

  (The solution with the opposite sign for Q is rejected because then some of these quantities would be negative.) We have established that the least N = 7.

  A non-unique solution for each N > 7 can be built up recursively, starting with the unique solution for N = 7. Given a solution for N, a solution for N+1 can be constructed as follows: If N is odd, attach a 1/N by 1 rectangle at either the top or the bottom and then shrink the vertical dimensions of all rectangles by a factor N/(N+1); if N is even, attach a 1 by 1/N rectangle at either the left or the right and then shrink all horizontal dimensions by a factor N/(N+1). Clearly each added rectangle, being longer that any of its predecessors, is congruent to none of them. However, one must also be sure that none of the 7 original rectangles become mutually congruent as they shrink, which is now shown: The cumulative change in the vertical-to-horizontal ratios of the sides of the rectangles is by a rational factor f = (7/8)(9/8)(9/10)(11/10)...(N/(N+1)) or ((N+1)/N), so that 7/8 <= f <= 1. Consequently sides of two distinct original rectangles can become equal only if they start (when N = 7) with a rational ratio r in the range 1 <= r <= 8/7. However, the only rational original ratios are 14/25, 14/15, and 7/5, all of which lie outside this range. Therefore there is a solution for each N >= 7 but none for any N < 7. QED

  ---

  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

• Alan O'Donnell (6.02.2003 @6:01:12 AM EDT)
• (6.3.2003 @07:00:42 AM EDT)
• Vitaly Stakhovsky (6.3.2003 @07:00:42 AM EDT)
• Dmitry Litvinenko (6.4.2003 @05:31:11 AM EDT)
• Mark Stubbings (6.4.2003 @08:42:35 AM EDT)
• Gyozo Nagy (6.5.2003 @06:01:22 PM EDT)
• Phillippe Fondanaiche Paris (6.6.2003 @04:12:22 PM EDT)
• Hagen von Eitzen (6.5.2003 @09:22:55 PM EDT)
• Vince Lynch (6.8.2003 @07:29:49 PM EDT)
• Christopher Howe (6.9.2003 @05:20:03 PM EDT)
• Joe Fendek (6.11.2003 @12:35:07 PM EDT)
• Ariel Flat (6.11.2003 @04:22:18 PM EDT)
• Steve Horvath (6.13.2003 @09:00:06 AM EDT)
• Bill Schennicke (6.13.2003 @03:42:00 PM EDT)
• Miguel Cuartas (6.13.2003 @03:54:12 PM EDT)
• Erick Bryce Wong (6.16.2003 @01:19:15 AM EDT)
• Claudio Baiocchi (6.16.2003 @04:54:18 AM EDT)
• Ken Crounse (6.16.2003 @02:38:34 PM EDT)
• Pascal Brisset (6.16.2003 @04:07:39 PM EDT)
• José H. Hieto (6.17.2003 @09:06:25 AM EDT)
• Carl D'Sousa (6.17.2003 @07:37:47 PM EDT)
• Algirdas Rascius (6.19.2003 @04:03:19 AM EDT)
• Mark Buisseret (6.19.2003 @09:08:51 AM EDT)
• Zhi Xing Shu (6.19.2003 @01:00:16 PM EDT)
• Chris Hills (6.20.2003 @08:22:08 AM EDT)
• Francis Golding (6.23.2003 @01:54:03 PM EDT)
• Alex Wagner (6.23.2003 @01:50:25 PM EDT)
• Dave Blackston (6.23.2003 @07:47:42 PM EDT)
• Thomas Zheng (6.25.2003 @06:23:00 PM EDT)
• Klaus Hoffmann (6.26.2003 @12:10:32 AM EDT)
• Daniel Chong Jyh Tar (6.29.2003 @11:04:29 AM EDT)
• Amit Sinha (6.30.2003 @01:39:00 AM EDT)