PARTRIDGE NUMBERS

Patrick Hamlyn
Multiprogramming, Perth, Western Australia
path@multipro.com.au

Erich Friedman
Stetson University, DeLand, FL 32723
efriedma@stetson.edu

Introduction

The identity 13 + 23 + . . . + n3 = (1 + 2 + . . . + n)2 tells us that 1 square of side 1, 2 squares of side 2, 3 squares of side 3, up to n squares of side n have the same total area as a square of side a. It is natural to ask whether the smaller squares can be packed without overlap inside the larger square. The smallest non-trivial packing is for n=8.

In general, we define the partridge number of a shape S is the smallest value of n > 1 so that 1 copy of S, 2 copies of S scaled by a factor of 2, up to n copies of S scaled by a factor of a, can be packed without overlap inside a copy of S scaled by a factor of a. Thus the partridge number of the square is 8. This was first verified by Bill Cutler, who found all 2332 different packings. Packings were also found independently by Bill Cutler, William Marshall, Michael Reid, Nob Yoshigahara, and the first author.

Figure 1. Partridge packing of squares of size 1 through 8

We present the partridge number of several other shapes, including rectangles, triangles, and trapezoids. Most of these were found by the first author using a computer packing program that he wrote 15 years ago in C. The algorithm uses straight backtracking that exploits possible symmetries of the smallest piece. By running on the equivalent of four 850 MHz machines, it finds an optimal tiling every few days. All results not otherwise attributed are due to the first author.

Rectangles

In 1996, Bill Cutler found that the partridge number of a 2x1 rectangle is 7, and that the partridge number of a 3x1 rectangle is 6.

Figure 2. Partridge packing of 2x1 rectangles of size 1 through 7

Figure 3. Partridge packing of 3x1 rectangles of size 1 through 6

The partridge number of a 4x1 rectangle is 7.

Figure 4. Partridge packing of 4x1 rectangles of size 1 through 7

The partridge numbers of a 3x2 rectangle and a 4x3 rectangle are also 7.

Figure 5. Partridge packing of 3x2 rectangles of size 1 through 7

Figure 6. Partridge packing of 4x3 rectangles of size 1 through 7

The partridge numbers of a 5x1 rectangle and a 5x2 rectangle are 8. We can get such packings by stretching a partridge packing of the square horizontally, but there are other partridge packings as well.

For the same reason, the partridge number of any rectangle is no more than 8. By shearing these rectangles, we see that the partridge number of parallelograms are also no more than 8. We conjecture that the partridge numbers of all other parallelograms are indeed 8. We also conjecture that rectangles are the only polyominoes with finite partridge numbers.

Triangles

An equilateral triangle has partridge number 9. A packing was first found by William Marshall, and the first author confirmed this was the smallest possible. This implies that all triangles have partridge number no more than 9.

Figure 7. Partridge packing of equilateral triangles of size 1 through 9

A 30o right triangle has partridge number 4.

Figure 8. Partridge packing of 30o right triangles of size 1 through 4

A 45o right triangle has partridge number 8.

Figure 9. Partridge packing of 45o right triangles of size 1 through 8

We think it is likely that other triangles have small partridge numbers but not have been able to find any others.

Trapezoids

A triamond (the union of 3 identical equilateral triangles) has partridge number 5.

Figure 10. Partridge packing of triamonds of size 1 through 5

Michael Reid found an infinite family of trapezoids (any horizontal shear of the union of 3 identical right triangles with legs 3 and 8) with partridge number 4.

Figure 11. Partridge packings of trapezoids of size 1 through 4

The second author found an infinite family of trapezoids (any horizontal shear of the union of 3 identical right triangles with legs 1 and 2) with partridge number 6.

Figure 12. Partridge packings of trapezoids of size 1 through 6

Open Questions

1. What other rectangles have partridge number less than 8?

2. What other triangles have partridge number less than 9?

3. What other trapezoids have finite partridge number?

4. Is there a non-convex shape with finite partridge number?

5. Is there a shape with partridge number 2, 3, or more than 9?

References

[1] E. Friedman, MathMagic, August 2002. (http://www.stetson.edu/~efriedma/mathmagic/0802.html)

[2] E. Pegg, "The Partridge Puzzle". (http://www.mathpuzzle.com/partridge.html)

[3] R. Wainwright, "The Partridge Puzzle II, III, and IV". handouts at Gathering for Gardner 2, 3, and 4.

[4] R. Wainwright, "The Partridge Puzzles". "Puzzlers' Tribute, a Feast for the Mind", D. Wolfe and T. Rogers ed. A.K. Peters, 2002, 277-281.