Saturday, June 24, 2023

Can you put n pennies on an n x n chessboard so that all of the distances are distinct/how to look that up?

 In Jan 2023 I went to the Joint Math Meeting of the AMS and the MAA and took notes on things to look up later. In one of the talks they discussed a problem and indicated that the answer was known, but did not give a reference or a proof. I emailed the authors and got no response. I tried to search the web but could not find it. SO I use this blog post to see if someone either knows the reference or can solve it outright, and either leave the answer in the comments, point to a paper that has the answer in the comments, or email me personally. 

--------------------------------------------------------------------

A chessboard has squares that are 1 by 1. 

Pennies have diameter 1.

QUESTION: 

For which n is there a way to place n pennies on squares of the n x n chessboard so that all of the distances between centers of the pennies are DIFFERENT?

-----------------------------------------------------------

I have figured out that you CAN do this for n=3,4,5. I THINK the talk said  it cannot be done for n=6. If  you know or find a proof or disproof then please tell me. I am looking for human-readable proofs, not computer proofs.  Similar for higher n.

I have a writeup of the n=3,4,5 cases here (ADDED LATER- I will edit this later in light of the very interesting comments made on this blog entry.) 

----------------------------------------------------------------------

With technology and search engines it SHOULD be easier to find out answers to questions then it was in a prior era. And I think it is. But there are times when you are still better off asking  someone, or in my case blog about it, to find the answer. Here is hoping it works!

ADDED LATER: Within 30 minutes of posting this one of my readers wrote a program and found tha tyou CAN do it for n=6 and gives the answer. Another commenter pointed to a website with the related quetion of putting as many pawns as you can on an 8x8 board.

ADDED LATER: There are now comments on the blog pointing to the FULL SOLUTION to the problem, which one can find here. In summary: 

for n=3,...,7  there IS a way to put n pennies on a chessboard such that all distances are distinct.

for n=8,...,14 a computer search shows that there is no such way.

for n=15 there is an INTERESTING PROOF that there is no such way (good thing - the computer program had not halted yet. I do not know if it every did.) 

for n\ge 16 there is a NICE proof that there IS such way. 

I am ECSTATIC!- I wanted to know the answer and now I do and its easy to understand!


12 comments:

  1. 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):
    a b c d e f
    1: 1 2 10 24 33 36
    2: 1 3 6 22 29 35
    3: 1 3 17 19 30 36
    4: 1 4 6 21 26 32
    5: 1 4 13 27 35 36
    6: 1 7 18 20 34 36
    7: 1 11 12 16 19 31
    8: 1 13 22 29 30 31
    9: 2 8 15 31 34 36
    10: 3 6 18 28 31 32
    11: 4 6 14 24 25 31
    12: 5 6 9 19 31 34
    13: 5 11 16 31 33 36
    14: 6 7 8 15 24 36
    15: 6 12 13 23 31 33
    16: 6 18 21 25 26 36

    ReplyDelete
  2. It is possible at n=7 and impossible at n=8: https://puzzling.stackexchange.com/questions/112705/all-distances-different-on-a-chess-board

    ReplyDelete
    Replies
    1. (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?

      Delete
    2. (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).

      Delete
    3. (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 6x6

      Delete
    4. I searched "all distances distinct chessboard" on Google, this was the second result. Glad it helped!

      Delete
  3. (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?

    ReplyDelete
  4. Here is the first solution formatted in a more readable way:
    pos1 pos1_coords pos2 pos2_coords distance
    1: 1 (1,1) 2 (2,1) 1.000000
    2: 24 (6,4) 36 (6,6) 2.000000
    3: 2 (2,1) 10 (4,2) 2.236068
    4: 10 (4,2) 24 (6,4) 2.828427
    5: 33 (3,6) 36 (6,6) 3.000000
    6: 1 (1,1) 10 (4,2) 3.162278
    7: 24 (6,4) 33 (3,6) 3.605551
    8: 10 (4,2) 33 (3,6) 4.123106
    9: 10 (4,2) 36 (6,6) 4.472136
    10: 2 (2,1) 24 (6,4) 5.000000
    11: 2 (2,1) 33 (3,6) 5.099020
    12: 1 (1,1) 33 (3,6) 5.385165
    13: 1 (1,1) 24 (6,4) 5.830952
    14: 2 (2,1) 36 (6,6) 6.403124
    15: 1 (1,1) 36 (6,6) 7.071068

    ReplyDelete
  5. 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/

    ReplyDelete
  6. https://users.renyi.hu/~p_erdos/1970-03.pdf

    ReplyDelete
  7. 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.

    ReplyDelete
  8. This answer from Puzzling Stack Exchange gives the 7x7 solution: https://puzzling.stackexchange.com/a/109625/2187

    This post proves that n pennies on an nxn board is impossible for all n>=15: https://oscarcunningham.com/670/unique-distancing-problem/

    All n from 8 to 14 were ruled out by computer search.

    ReplyDelete