Can you make $2015$ positive integers $1,2, \ldots , 2015$ to be a certain permutation which can be ordered in the circle such that the sum of any two adjacent numbers is a multiple of $4$ or a multiple of $7$?
Problem
Source: China Southeast Math Olympiad 2015 Day 1 P3
Tags: combinatorics, graph theory
07.06.2017 07:35
The answer is yes
25.05.2018 13:05
As claimed above, the answer is $\boxed{\text{YES}}$. Here is one example. Consider the following path $\mathcal{P}$, with $28$ vertices. \begin{align*} &15\to 6\to 1\to 13\to 8\to 20\to 22\to 27 \to \\ &9\to 5\to 2\to 12\to 16\to 19\to 23\to 26\to \\ &10\to 4\to 3\to 11\to 17\to 18\to 24\to 25 \to \\ &7\to 14\to 28\to 21 \end{align*}Connect this with $28+\mathcal{P}$ (increase each element by $28$), which is clearly possible. Then consider $$\mathcal{P}\to 28+\mathcal{P}\to 56+\mathcal{P}\to...\to 1988+\mathcal{P}$$which is hamiltonian cycle. Observe that we have added $2016$, but this is not trouble since we can just delete it. Hence we are done.
12.07.2022 12:22
MarkBcc168 wrote: As claimed above, the answer is $\boxed{\text{YES}}$. Here is one example. Consider the following path $\mathcal{P}$, with $28$ vertices. \begin{align*} &15\to 6\to 1\to 14\to 8\to 20\to 22\to 27 \to \\ &9\to 5\to 2\to 12\to 16\to 19\to 23\to 26\to \\ &10\to 4\to 3\to 11\to 17\to 18\to 24\to 25 \to \\ &7\to 14\to 28\to 21 \end{align*}Connect this with $28+\mathcal{P}$ (increase each element by $28$), which is clearly possible. Then consider $$\mathcal{P}\to 28+\mathcal{P}\to 56+\mathcal{P}\to...\to 1988+\mathcal{P}$$which is hamitonian cycle. Observe that we have added $2016$, but this is not a trouble since we can just delete it. Hence we are done. I think that you might have a mistake As claimed above, the answer is $\boxed{\text{YES}}$. Here is one example. Consider the following path $\mathcal{P}$, with $28$ vertices. \begin{align*} &15\to 6\to 1\to 13\to 8\to 20\to 22\to 27 \to \\ &9\to 5\to 2\to 12\to 16\to 19\to 23\to 26\to \\ &10\to 4\to 3\to 11\to 17\to 18\to 24\to 25 \to \\ &7\to 14\to 28\to 21 \end{align*}Connect this with $28+\mathcal{P}$ (increase each element by $28$), which is clearly possible. Then consider $$\mathcal{P}\to 28+\mathcal{P}\to 56+\mathcal{P}\to...\to 1988+\mathcal{P}$$which is hamitonian cycle. Observe that we have added $2016$, but this is not a trouble since we can just delete it. Hence we are done.