Mrs. Perkins Quilts

Ed Pegg Jr

Dividing a square into smaller squares is often called the Mrs. Perkins' Quilt problem. I mentioned a while ago that Erich Friedman found a way to divide a side-67 square into 20 smaller squares all with double-digit sides. Can you find his solution?  Answer. The only solver of this puzzle was Lance Gay.  Lance followed up by finding better solutions for squares of size 88 to 90.  Robert Wainwright sent me better answers for sizes 53 and 91.  All of these new solutions were graciously accepted by Richard Guy, for the next edition of Unsolved Problems in Geometry. John Conway let me know that Dudeney named the puzzle.  Geoffrey Morley sent in transcriptions of Duijvestijn's solutions.  Erich Friedman sent me this list of best solutions (Antony Boucher and Lance Gay filled in the blanks). The current best known solutions are as follows: {1 | 1}, {4 | 2}, {6 | 3}, {7 | 4}, {8 | 5}, {9 | 6,7}, {10 | 8,9}, {11 | 10-13}, {12 | 14-17}, {13 | 18-23}, {14 | 24-29}, {15 | 30-39,41}, {16 | 40,42-53}, {17 | 54-70}, {18 | 71-91}, {19 | 92-108}.   Lance Gay:  "Since seeing your write-up on mathpuzzle.com last month, I have written some Mrs. Perkins quilt search software to look for solutions. For fun, I added a routine to print out the bitmaps of solutions. I run my searches on a pair of 1.8 GHz MS-Windows machines. It appears that computers have gotten faster since people have last done some serious searching. For now, I have completed all searching for sides up to 100. I am now concentrating on larger squares (such as attempting to beat the order-20 side-154 square). My search algorithm is not exhaustive so the trick is reducing the search space to the most fruitful areas."  John Conway: "You might add the two 1950s papers both called "Mrs Perkins's Quilt", one by me and one by G.B.Trustrum, in Proc. Camb. Phil. Soc.  I gave the answers for low n, and an upper bound of order n^(1/3) for general n, which Trustrum improved to order log(n).  Since there's an obvious logarithmic lower bound, all that remains is to find the best constant.  I don't know if there's been any progress on that problem since those two papers." Antony Boucher sent me some corrections for the list, and also sent solving code.