[math-fun] Mrs. Perkins Quilt -- Orders 89, 90 improved over UPIG
Lance Gay has cracked a problem in Unsolved Problems in Geometry. Quoting RK Guy -- known records with "some slightly increasing lack of confidence" 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-50}, {17 >> 51-66,68,70}, {18 >> 67,69,71-87}, {19 >> 88-100} RK can pencil in a correction for that last bit. Lance Gay (Lance.Gay@ngc.com) found order-18 solutions for side 89 and 90 Mrs. Perkins Quilts. These appear to be better than the current known values. Side=89 Order=18 - [48 41][5 5 11 20][2 8][41 9][2 9][3 7][12][8 28][20] Side=90 Order=18 - [49 41][8 12 21][41 9 7][3 9][2 8][11][2 28][5 5][21] Lance also asks for a source for the best know solutions for side 100-250. The only source I knew of was Duijvestijn, A. J. W. ftp://ftp.cs.utwente.nl/pub/doc/dvs/TableI. -- but this seems to be down. Other pertinent refs: http://mathworld.wolfram.com/MrsPerkinsQuilt.html http://mathworld.wolfram.com/PerfectSquareDissection.html I must humbly take blame for botching a diagram on Eric's site -- the order 7 square there is wrong (but the sequence right under is correct). Nick Gardner pointed out the mistake to me. For an exercise, try to dissect the order 7 square into 9 smaller squares. An Ascii solution is below, along with the Duijvestijn code. --Ed Pegg Jr, www.mathpuzzle.com (Fixed width Ascii art) ___ ___ ___ ___ ___ ___ ___ | | | | | | | | | | | | | |___ ___|___ ___| | | | | | |___ ___ ___|___|___| | | | | | | |___|___ ___| | | | | | | | | | | | | | | | |___ ___ ___ ___|___ ___ ___| [3 2 2][1 1 2][4 1][3]
On Thu, 9 Oct 2003, Ed Pegg Jr wrote:
Lance Gay has cracked a problem in Unsolved Problems in Geometry. Quoting RK Guy -- known records with "some slightly increasing lack of confidence" 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-50}, {17 >> 51-66,68,70}, {18 >> 67,69,71-87}, {19 >> 88-100}
Let me say that there should have been no lack of confidence up to 15, because I proved the above numbers best possible up to there long ago (I think in fact up to 16, but am not quite sure of that).
Other pertinent refs: http://mathworld.wolfram.com/MrsPerkinsQuilt.html http://mathworld.wolfram.com/PerfectSquareDissection.html
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. By the way, the name "Mrs Perkins's Quilt" comes from a problem in one of Dudeney's books, wherein he gives the answer for n = 13. John conway
Let me say that there should have been no lack of confidence up to 15, because I proved the above numbers best possible up to there long ago (I think in fact up to 16, but am not quite sure of that).
Up to 15, you are definitely correct, and Gardner mentions the size 41 square as a particularly difficult case in his column. For order 16, the order 53 square seems best, and that seems to be a more recent discovery. Here's the pertinent square {{29,24},{6,5,13},{24,4,1},{5},{3,4},{7},{6,3},{16},{13}} If that's familiar, you are correct about 16. --Ed Pegg Jr.
Ed, Thanks for this. Would you copy this message to Lance Gay, Bob Wainwright, Bouwkamp & anyone else you're in touch with & might be interested, or know of earlier knowledge? I didn't know of the 3 Wainwright results. I wonder if Bob had observed that his 91 and 154 results were members of a sequence in which squares of edges 28 52 91 154 256 421 688 1120 1819 2950 4780 ... can be tiled with 14 16 18 20 22 24 26 28 30 32 34 ... smaller squares. The second of these may be new, and justifies the slight increasing lack of confidence, confirming JHC's doubt about 16. The sequence appears not to appear in the Online Ency of Integer Sequences, and is briefly described as 3u_k - 11 where u_k is the k-th Fibonacci number, and a square of this edge can be tiled with 2k squares. The 52 tiling, in Duijvestijn notation, is [28,24][4,5,15][24,7,1][6][9,4][6,13][8,1][7] If my calculations are correct, this gives a sequence for which f(n) ~ 1.388483827... log n where the log is to base 2. This must be well known to those who well know it (I've been too lazy to look up the Trustrum and Conway papers) but, modulo my usual mistakes, the 3 Lance Gay solutions are members of 3 similar sequences: ** 7 8 9 10 11 12 13 14 15 16 ... 14 16 18 20 22 24 26 28 30 32 ... 27 50 88 149 248 408 667 1086 1764 2861 ... 28 48 89 150 252 415 680 1108 1801 2922 ... 28 49 90 152 255 420 688 1121 1822 2956 ... ** none of which are in OEIS, p'r'aps 'cos I've made misteaks? First row is k. Second row is 2k, the number of tiling squares. Other 3 rows are edges of squares so tilable. The first two columns agree with C3 in UPIG, and are consistent with JHC's remarks. The 3rd col contains the LG solutions (new to me). My guess at the formula for the first of these three is 3u_n - u_n-5 - 11 The Wainwright 53 solution is a member of the sequence 16 29 53 90 151 249 408 665 1081 1754 ... I believe that the characteristic polynomial is always (x - 1)(x^2 - x - 1) R. On Sat, 11 Oct 2003, Ed Pegg Jr wrote:
Let me say that there should have been no lack of confidence up to 15, because I proved the above numbers best possible up to there long ago (I think in fact up to 16, but am not quite sure of that).
Up to 15, you are definitely correct, and Gardner mentions the size 41 square as a particularly difficult case in his column. For order 16, the order 53 square seems best, and that seems to be a more recent discovery.
Here's the pertinent square {{29,24},{6,5,13},{24,4,1},{5},{3,4},{7},{6,3},{16},{13}}
If that's familiar, you are correct about 16.
--Ed Pegg Jr.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Ed Pegg Jr -
Ed Pegg Jr
-
John Conway -
Richard Guy