13
$\begingroup$

I posted this question on MSE, and failed to get the type of answer I wanted. That's why I would like to post it here and wait for the experts to reply. Here's the link to the MSE post, which I anyways copy paste here as well-

I got this interesting arrangement of numbers from $1$ to $32$ in a group in Facebook- enter image description here

This being an interesting property to look at, I was trying to figure out whether $32$ is something special, or does this hold for other numbers as well. So, let's say, we want to construct one such circle for a general $n$. My idea was to take any $m\in \mathbb N_n=\{1,2,\dots ,n\}$ and find two different integers $x,y\in\mathbb N_n$ so that both $(m+x)$ and $(m+y)$ are perfect squares. Then, we need to find $x^\prime, y^\prime\in \mathbb N_n$ different from $x$, $y$ and $m$ such that both $(x+x^\prime)$ and $(y+y^\prime)$ are perfect squares. Then, we can continue in this manner.

Now, for any two $a,b\in \mathbb N_n$, we have $2\leq a+b\leq 2n$. So, for our given $m$, when we are looking for the mentioned $x$ and $y$, we only need to check through all the perfect squares in the interval $[m,2n]$. So, to reduce our work, we can take our initial choice $m$ to be equal to $n$.

But, now comes the main problem. Let's say, we want to work it out for $\mathbb N_{33}$. So, let's say, our initial $m$ is $33$. The values of $x$ and $y$ can be from the set $\{3,16,31\}$. The question is, which two of these three to choose so that eventually we don't run into a repitition. Note that, in the $\mathbb N_{32}$ case (which is the one in the diagram), taking $m=32$ leaves us with an advantage of having only two choices $4$ and $17$. But, in the next step, for finding the appropriate $x^\prime$ for $x=4$, we have the choices $\{5,12,21\}$ (since $32$ is already taken). The given diagram uses $x^\prime =21$. I tried using $x^\prime =5$ and then using values of my choice, but soon ran into an unavoidable repitition.

So, is there a way to make more circles with other values of $n$, or does $32$ have some profound property which makes it the only possible choice for $n$? I thought, maybe $32$ being a power of $2$ has to do something with it. So, I tried using $n=2,4,8,16$. But, these are trivially NOT solutions since there aren't enough perfect squares in $[n,2n]$ for these values of $n$. Note that this "not enough squares" angle immediately gives a lower bound of $n\geq 19$ by trial and error. As Peter Taylor pointed out, this "not enough squares" argument also rules out $n\le 30$ since $18$ is always a vertex of degree $1$ otherwise. So, we have a lower bound of $n\ge 31$. Also, I was too lazy to even attempt $n=64$.

So, is this case a rare coincidence, or can we have other values of $n$ satisfying this property as well? If there are other values, what family do they belong to? Also, for any case, is that arrangement unique?

Edit: I got one interesting answer that uses graph theory. But, that has a computer program to check that it holds for all $100\geq n\geq 32$. However, I want more "mathy" arguments. I want to see why this happens instead of to only confirm that it happens. I want to know whether it happens for all $n$ or whether there are cases where it breaks down. Please consider these questions as well.

One answer I got is this which (as I already mentioned) is only good enough to check using a computer program that our desired property holds for $100\geq n\geq 32$. But, it does provide a very nice insight into the question using Graph Theory in terms of Hamiltonian cycles. So, added to the questions I asked in the "Edit" paragraph of the main post, one more question I would like to ask on this platform is, has there been any formal research on this topic? That is, are there any papers dealing with finding Hamiltonian cycles in this particular case? If yes, please let me know.

$\endgroup$
17
  • 3
    $\begingroup$ The "not enough squares" argument rules out $18 \le n \le 30$ because $18$ pairs with $7$ and then nothing below $31$. $\endgroup$ Nov 11, 2021 at 11:00
  • 2
    $\begingroup$ Let $X_n$ denote the $n$-vertex instance of this graph. Then $X_{n+1}$ is obtained from $X_n$ by adding vertex $n+1$ and has a Hamilton cycle if (and only if) there is a Hamilton path in $X_n$ starting and ending at distinct neighbours of $n+1$. So I asked the computer about Hamilton paths in $X_n$. For $n$ around $30$-$40$ there are quite a few pairs of vertices that are not connected. Strangely though, for $n$ at least 51 up to 70, there is a unique pair of vertices (always 14 and 31) that are not connected by a Hamilton path in $X_n$. So $X_n$ is very close to being Hamilton connected. $\endgroup$ Nov 12, 2021 at 2:00
  • 2
    $\begingroup$ In fact, for $n > 70$ and up to $85$, the graph is Hamilton connected, and I expect this to continue. But I can't see any obvious way of using this inductively. $\endgroup$ Nov 12, 2021 at 2:25
  • 3
  • 2
    $\begingroup$ @SayanDutta Peter Taylor's observation is that for $n$ between 19 and 30, the vertex "18" is a vertex of degree 1 in the graph and so cannot be contained in a cycle. $\endgroup$ Nov 12, 2021 at 7:07

1 Answer 1

2
$\begingroup$

There is at least one published mention of this problem. Two sequences in the Online Encyclopedia of Integer Sequences, A071983 and A071984, are very relevant. The entry for A071983 gives a reference:

Ruemmler, Ronald E., "Square Loops," Journal of Recreational Mathematics 14:2 (1981-82), page 141; Solution by Chris Crandell and Lance Gay, JRM 15:2 (1982-83), page 155.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.