For what integers $ n\ge 3$ is it possible to accommodate, in some order, the numbers $ 1,2,\cdots, n$ in a circular form such that every number divides the sum of the next two numbers, in a clockwise direction?
Problem
Source: Central American Olympiad 2002, problem 1
Tags:
Brut3Forc3
30.12.2009 09:36
$ n=3$ obviously works for any permutation we choose. We now show no other $ n$ can work.
Let us draw out sections of the circular form linearly, with the understanding that the rightward direction corresponds to a clockwise direction on the circle, and that E represents an even number, while O represents an odd number.
Suppose there were two even numbers next to each other: EE_
Then the next number (clockwise) could not be odd (EEO), for we can not have an even number divide the sum of an even number and an odd number. Thus, the next number must be even. (EEE) Similarly, the following number must also be even, and so on (EEEE...), giving a clear contradiction.
Now consider an even number. It must be surrounded by odds on both sides: OEO
The arrangment EOE is impossible, since the sum of the two rightmost numbers is odd, and an even number cannot divide it. Thus, we cannot have E on the left or the right of OEO; that is, it must be arranged OOEOO, so the two number preceeding and succeding an even number must be odd.
For any even number, consider how many odd numbers are between that number and the next even number (clockwise). Our analysis shows that this number is at least 2. Thus, there are at least twice as many odds as there are evens. This is impossible for any $ n$ except 3, so we are done.
panamath
02.07.2012 03:17
See that we can't have two evens together because in that case they all will have to be even, so if we have an even it w'd have to be odd-even-odd and from this we can deduce the parity of the next and the previous, something like this: odd-odd-even-odd-odd from this we conclude that for every even we will have at least $2$ odds, if $n=2d$ there are $d$ odds and $d$ evens, so $n$ can't be even, if $n=2d+1$ there are $d$ evens and $d+1$ odds, from this last conclutions we have $d+1 \ge 2d$ thus $1 \ge d$ so $d=1$ and $n=3$.