Multiprogramming, Perth, Western Australia

path@multipro.com.au

Stetson University, DeLand, FL 32723

efriedma@stetson.edu

Introduction

The identity 1^{3} + 2^{3} + . . . + n^{3} = (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.

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.

The partridge number of a 4x1 rectangle is 7.

The partridge numbers of a 3x2 rectangle and a 4x3 rectangle are also 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.

A 30^{o} right triangle has partridge number 4.

A 45^{o} right triangle has partridge number 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.

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.

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.

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.