The Partridge Puzzle

I recently stumbled across the Partridge Puzzle invented by mathematician Robert T. Wainwright. Consider a collection of square tiles, the smallest of which is 1 unit by 1 unit in size (and there is one of them) and the largest of which is N units by N units in size (and there are N of them). The total area of all the tiles would be 1x(1×1) + 2x(2×2) + … + Nx(NxN). That sum of cubes turns out to be [(N x (N+1) / 2]^2. This means that the area covered by the tiles is the same as the area of a single large square whose length and width are [N x (N+1)]/2. So wouldn’t it be cool if you could find an arrangement for all those tiles that allows them to fit inside that larger square? That’s the Partridge Puzzle.

Now it turns out there are zero solutions for N=1 through N=7 and there are 18,656 solutions for N=8 (so far, solutions have been found for N=8 through N=33).  You can buy an N=8 one from Kadon Enterprises:

It’s really nicely made; here’s a picture of mine:

Although there are 18,656 solutions to this thing, after several frustrating days I was able to find precisely zero of them. So I wrote a program to solve it, which I suppose is either winning at the meta-level or cheating depending on how you want to look at it. I (or if you prefer, my program) found all the solutions to the N=8 puzzle and I let it run long enough to generate a solution or two for N=9 through N=13. Here’s my GitHub repository where I’ve parked my source code, solutions, and some analysis:

This was a fun diversion and gave me an excuse to learn Python, Java, GitHub, and AWS EC2 management. I will leave you with a picture of my favorite of the 18,656 solutions:

It’s my favorite because it is the most fragmented of all the solutions. That is, this solution has the fewest number of same-sized tiles touching each other. If you want to learn more, here are some excellent links to explore: