Decide if the vertices of a regular $30$-gon can be numbered by numbers $1, 2,.., 30$ in such a way that the sum of the numbers of every two neighboring to be a square of a certain natural number.
Problem
Source: Czech-Polish-Slovak Junior Match 2015, Individual p2 CPSJ
Tags: number theory, Sum, Perfect Square
16.03.2020 16:46
Such a numbering does not exist. Let be $A_1,A_2,\dots,A_{30}$ the vertices of the polygon, in this order and $n_k$ the number associated to the vertex $A_k$. Obviously, each vertex has exactly $2$ neighbors. With the notations $A_0\equiv A_{30}, A_{31}\equiv A_1$, results $n_k+n_{k+1}=m_k^2$, where $m_k\in\mathbb{N}$. $1+2\le m_k^2\le 30+29\Longrightarrow m_k^2\in\{4,9,16,25,36,49\}$. $\forall k\in\{1,2,\dots,30\}, n_{k-1}+n_k=m_{k-1}^2; n_k+n_{k+1}=m_k^2$. $n_{k-1},n_k,n_{k+1}$ are pairwise distinct and results $m_{k-1}\ne m_k$. Assume exists a numbering with the given conditions. Then exists $p\in\{1,2,\dots,30\}$ such that $n_p=18$. In this case, $19\le m_{p-1}^2,m_p^2\le 48$, hence $n_{p-1}+n_p,n_p+n_{p+1}\in\{25,36\}$, with the solutions $\{n_{p-1},n_{p+1}\}=\{7,18\}$. Results: either $n_{p-1}=n_p=18$, either $n_{p+1}=n_p=18$, contradiction. With other words: the vertex $A_p$ with $n_p=18$ can have a single neighbor $A_q$ such that $n_p+n_q$ is the perfect square of a natural number, respectively $n_q=7$.
03.03.2021 01:34
$S_t$ = total sum; $1+2+3+...+30=465=S_t$, since every two neighbors would sum up to a perfect square, we would have $(a_1^2+a_2^2+...+a_{30}^2)=1+2+3+...+30=2.465=930=2.S_t$, which cannot provide a solution, because we can use $a_j^2={4,9,25,36,49}$, but to maximize the sum we could use eleven $49's$, six $25's$ and two $9's$, which doesn't reach 930. $Q.E.D.$