A quick attempt (by hand) produced: 1 3 7 6 2 5 9 4 8 which contains the 13 squares: 1, 4, 9, 16, 25, 36, 49, 64, 169, 324, 625, 729, 961. Maybe more are possible. -- Roger Phillips, software developer ------------------------------------------------------- Hi Ed, I found a 3x3 matrix that contains 13 squares: 1 6 9 3 2 4 7 5 8 contains: 1, 4, 9, 16, 25, 36, 49, 64, 169, 324, 625, 729, 961. Hope I fared well :) -- Z ------------------------------------------------------ Hello! 169 324 758 seems to be best (13 squares) There are many better, if any numbers are accepted: This is one (14 squares): (0*0=0) 930 625 144 But how about nxm-rectangle? Juha ----------------------------------------------------- Don't know if this is the maximum, but I imagine it must be close. Fun little problem. 731 526 849 contains 13 squares 1,4,9,16,25,36,49,64,169,324,625,729,961 **Ali M. ------------------------------------------------------- There are 22 possible squares which are not too large and don't have any repeated digits or zeroes. They are 1, 4, 9, 16, 25, 36, 49, 64, 81, 169, 196, 256, 289, 324, 361, 529, 576, 625, 729, 784, 841, 961. 1, 4, and 9 will always be present. It's not hard to cram in all the two digit squares and 169/961: 169 includes 1, 4, 9, 16, 25, 36, 49, 64, 81, 169, 961 (11 total) 843 257 If you omit 36 you can squeeze in 625 and 729: 169 includes 1, 4, 9, 16, 25, 49, 64, 81, 169, 625, 729, 961 (12 total) 824 753 Another alternative: 169 includes 1, 4, 9, 16, 25, 49, 64, 81, 169, 289, 784, 961 (12 total) 784 253 Another 12-set which includes all the two-digit squares: 361 includes 1, 4, 9, 16, 25, 36, 49, 64, 81, 361, 529, 784 (12 total) 784 529 And another: 361 includes 1, 4, 9, 16, 25, 36, 49, 64, 81, 256, 361, 729 (12 total) 458 927 The inclusion of some squares forces other squares to exist in the square as well: 169 or 961 includes the other of these and 16. 361 includes 36 and 16. Any of 529, 256, or 625 includes 25. There are many pairs of squares which cannot both possibly exist in the square: 196 precludes 16, 169, 961, 361 361 precludes 961, 196, 169 841 precludes 81, 784 625 precludes 529, 256, 576 289 precludes 529, 729 529 precludes 625, 256, 289, 729 256 precludes 625, 529, 576 169, 961, 784, 576, and 729 each preclude one or more squares in ways redundant with the descriptions above. 324 is the only three-digit square which does NOT preclude any other square from appearing. Another way of thinking of these is as sets of squares which are mutually exclusive: You can have either 256 or 625 or (529 and/or 576). You can have either 529 or 289 or 729. You can have (169 and 961) or 361 or 196. You can have 841 or (784 and/or 81). No matter how you choose among these, you must omit 4 of the numbers from the first two groups, two from the second, and one from the third. So no more than 15 squares are possible. Additionally, there is a limitation around where numbers are placed in the grid. 324, 529, 625, and 729 all have 2 as the middle digit. You can only use more than one of these if you put the 2 in the center, which eliminates any possibility of making 256 or 289. (Of course, there are some limitations involving these numbers already. I don't think we get anything more out of this except that certain combinations from the first two mutually-exclusive groups, such as 625 and 289, also eliminate 324.) Likewise, four digits must go in the corners; these cannot appear as the middle digit of a three-digit number. The last four digits must go in the middle edge positions; these can appear at most once as the middle digit in a three-digit square and once as the first or last digit in a three-digit square, with an exception for the case of 169 and 961 (if we treat these as a single square for this rule, it remains true). Combining these, we can produce additional bits of information, such as that we may use at most two of 576, 729, and 784. Additional reasoning may come from the limits on the number of digits adjacent to a single digit. We can reduce the maximum number of squares to 14 if we consider that if 6 goes in the center, we lose one square from the first mutually exclusive group; if it goes in a corner than we lose one from the third mutually exclusive group, and if it goes in a middle edge position, we encounter the situation that led me to exclude 36 from my second construction above. To avoid losing a square from one of the mutually exclusive groups, we must use 169/961 and one of 256, 625, or 576. Additionally, 6 appears in the 2-digit squares 36 and 64. To form all of these, 6 must be surrounded by 1, 9, 3, 4, and one of 5, 2, or 7. This means 8 must be somewhere on the opposite edge from the 6, which is also the edge where the 1 is, and therefore 81 cannot be formed. So the minimum is 12 (as shown), the maximum is 14 (as proven). However, there are just too many ways to choose 13 or 14 numbers for me to work through such logic to eliminate them. The best at this point is probably simply writing a program to search the (rather small, on a computational scale) problem space: 9! ways to arrange the digits divided by 8 reflections/rotations of each for a total of 45360 combinations. Joseph DeVincentis ------------------------------------------------------- Ed, I haven't verified all configurations but after some analysis it appears that 12 is the maximum. An example layout would be: 3 2 5 1 6 9 = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 169, 784, 961} = S, and |S| = 12. 7 8 4 And since the digits 3, 2, and 5 only appear in the set above one time, it possible to rearrange the top row as any of the following: 3 5 2, 5 2 3, or 2 5 3. Therefore, I have four non-polymorphic examples of configurations producing 12 squares. Bjorn. ------------------------------------------------------- The maximum is 10 8 1 2 4 6 5 9 3 7 1, 4, 9, 16, 25 , 36, 49, 64, 81, 361 OR 8 1 2 3 6 5 4 9 7 1, 4, 9, 16, 25, 36,49 , 81, 169, 961 Thanks Arun Davidson, Systems Engineer Kuwait ------------------------------------------------------- As for the _real_ problem, I came up with 7 3 1 5 2 6 8 4 9 which contains 12 of the 22 possible squares, only 15 of which could possibly coexist, I believe. Tom ------------------------------------------------------- Maximum squares = 12; 2 cases: 169 324 758 1,4,9,16,25,36,49,64,169,324,625,961 841 526 739 1,4,9,16,25,36,64,169,324,625,841,961 Denis Borris Ottawa Ontario Canada. I'm just an imagination of your figment. ------------------------------------------------------- i found one with 11 squares... 729 546 831 it contains the following... 1 49 36 4 64 9 169 16 961 25 729 i qiut after i found this one... please let me know if there is one containing more... thanks... Matt Butts ---------------------------------------------------- Ok, here's the answer for this week's puzzle: 169 384 257 It only has 11 squares, but I think that's the best that can be done. -aron fay ---------------------------------- I might think about this more and come up with a proof for one but for now I threw this one together. 183 652 947 its got: 81-(backward top row); 169-(1st column); 961-first column); 256-(backward middle row); 25-(backward middle row); 16-(1st column); 49-(backward bottom row); 64-(diagonal bottom left corner); 9; 4; 1; I think that's all I have there, maybe I missed one or two. I'll try to get even more sometime. Tell me what you think ---------------------------- Ed, There are a number of 9's Such as: 529 784 631 I found one 10: 169 834 257 Dick Saunders Jr. ------------------ 8. 816 357 492 MJR