tag:blogger.com,1999:blog-3722233.post9038733708392236603..comments2024-05-23T03:24:52.112-05:00Comments on Computational Complexity: Can you put n pennies on an n x n chessboard so that all of the distances are distinct/how to look that up? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-53778344435231849922023-06-24T16:00:56.358-05:002023-06-24T16:00:56.358-05:00This answer from Puzzling Stack Exchange gives the...This answer from Puzzling Stack Exchange gives the 7x7 solution: https://puzzling.stackexchange.com/a/109625/2187<br /><br />This post proves that n pennies on an nxn board is impossible for all n>=15: https://oscarcunningham.com/670/unique-distancing-problem/<br /><br />All n from 8 to 14 were ruled out by computer search.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64504475311846548342023-06-24T12:58:55.011-05:002023-06-24T12:58:55.011-05:00The erdos-guy paper has solutions until n=6. It al...The erdos-guy paper has solutions until n=6. It also states that for n>15 this is impossible. I haven't followed up citations to that paper. I just wrote "lattice distinct distances" in the search box.<br />Kodluhttps://www.blogger.com/profile/12418167413500125327noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18871705853470174052023-06-24T12:57:38.406-05:002023-06-24T12:57:38.406-05:00https://users.renyi.hu/~p_erdos/1970-03.pdfhttps://users.renyi.hu/~p_erdos/1970-03.pdfKodluhttps://www.blogger.com/profile/12418167413500125327noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4431126457011225432023-06-24T12:18:59.183-05:002023-06-24T12:18:59.183-05:00I searched "all distances distinct chessboard...I searched "all distances distinct chessboard" on Google, this was the second result. Glad it helped!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79688246494219504652023-06-24T11:19:11.572-05:002023-06-24T11:19:11.572-05:00You can see the Erdos and Guy paper from 1970 http...You can see the Erdos and Guy paper from 1970 https://users.renyi.hu/~p_erdos/1970-03.pdf which to my understanding states it is possible up to n=6 and impossible for n>15. I know that a more general problem was solved by Pach and Guth according to https://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/Kodluhttps://www.blogger.com/profile/12418167413500125327noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83117569765057284442023-06-24T10:39:54.775-05:002023-06-24T10:39:54.775-05:00(Bill again) What you pointed to is not quite my p...(Bill again) What you pointed to is not quite my problem. You pointed to getting as many pawns as possible, diff distances, on an 8x8 board. What you pointed to shows how to get 6 on an 7x7 board (it ends up not using the entier 8x8 board) and how to get 7 on an 8x8 board, but not 6 o 6x6 or 7 on 7x7. The prior comment had 6 on 6x6Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6952679348273872892023-06-24T10:36:53.323-05:002023-06-24T10:36:53.323-05:00(Bill again). The pointer you gave shows how to pu...(Bill again). The pointer you gave shows how to put 6 pawns on an 7x7 board, and later how to put 7 pawns on an 8x8 board, but not how to put 6 on a 6x6 board (the next commenter does that) or 7 on a 7x7 board (which might be impossible). Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17927763030494017032023-06-24T10:33:00.913-05:002023-06-24T10:33:00.913-05:00Here is the first solution formatted in a more rea...Here is the first solution formatted in a more readable way:<br /> pos1 pos1_coords pos2 pos2_coords distance<br /> 1: 1 (1,1) 2 (2,1) 1.000000<br /> 2: 24 (6,4) 36 (6,6) 2.000000<br /> 3: 2 (2,1) 10 (4,2) 2.236068<br /> 4: 10 (4,2) 24 (6,4) 2.828427<br /> 5: 33 (3,6) 36 (6,6) 3.000000<br /> 6: 1 (1,1) 10 (4,2) 3.162278<br /> 7: 24 (6,4) 33 (3,6) 3.605551<br /> 8: 10 (4,2) 33 (3,6) 4.123106<br /> 9: 10 (4,2) 36 (6,6) 4.472136<br />10: 2 (2,1) 24 (6,4) 5.000000<br />11: 2 (2,1) 33 (3,6) 5.099020<br />12: 1 (1,1) 33 (3,6) 5.385165<br />13: 1 (1,1) 24 (6,4) 5.830952<br />14: 2 (2,1) 36 (6,6) 6.403124<br />15: 1 (1,1) 36 (6,6) 7.071068Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6127594788022260202023-06-24T10:31:10.556-05:002023-06-24T10:31:10.556-05:00(This is Bill G) THANKS! Not sure why I couldn'...(This is Bill G) THANKS! Not sure why I couldn't find that page since I looked for a long time. What key word did you use? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76668656267138481612023-06-24T10:28:52.829-05:002023-06-24T10:28:52.829-05:00(This is Bill G- I have had trouble getting my com...(This is Bill G- I have had trouble getting my comments labelled as from me so I add this note.) THANKS! I wonder if perhaps they said at the talk that 7 was the first n such that it can't be done OR if I misheard them entirely. Can your code be modified easily for n=7? higher? I would be curious (1) what is the first n such that it can't be done, (2) for that n, is there a nice non-computer proof, (3) the function that, given n, tells how many ways to do this- how fast does that grow? Does it go up and then down and then 0, or just up up up and then 0, or what? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11512021810900441622023-06-24T10:27:45.175-05:002023-06-24T10:27:45.175-05:00It is possible at n=7 and impossible at n=8: https...It is possible at n=7 and impossible at n=8: https://puzzling.stackexchange.com/questions/112705/all-distances-different-on-a-chess-boardAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47188540498325683282023-06-24T10:21:00.097-05:002023-06-24T10:21:00.097-05:00I just brute forced it in R, but I got 16 total so...I just brute forced it in R, but I got 16 total solutions for the n = 6 case, where each value corresponds to its box placement if you read the gird like a book (so 22 is 4th row, 4th column):<br /> a b c d e f<br /> 1: 1 2 10 24 33 36<br /> 2: 1 3 6 22 29 35<br /> 3: 1 3 17 19 30 36<br /> 4: 1 4 6 21 26 32<br /> 5: 1 4 13 27 35 36<br /> 6: 1 7 18 20 34 36<br /> 7: 1 11 12 16 19 31<br /> 8: 1 13 22 29 30 31<br /> 9: 2 8 15 31 34 36<br />10: 3 6 18 28 31 32<br />11: 4 6 14 24 25 31<br />12: 5 6 9 19 31 34<br />13: 5 11 16 31 33 36<br />14: 6 7 8 15 24 36<br />15: 6 12 13 23 31 33<br />16: 6 18 21 25 26 36Anonymousnoreply@blogger.com