Suppose $n$ is a natural number. In how many ways can we place numbers $1,2,....,n$ around a circle such that each number is a divisor of the sum of it's two adjacent numbers?
Problem
Source: Iran 2nd round 2012-Day1-P2
Tags: induction, combinatorics proposed, combinatorics
30.04.2012 12:43
30.04.2012 20:22
I used induction with out any case! :-( actually I missed my time! :-(
01.05.2012 17:20
My ideas: if $2$ adjacent numbers are even, they all had to be => impossible. When $2|n$ we get $n-1$ is next to two even numbers, so they have even sum: $2(n-1)$ and the numbers are $n,n-2$ and by easy induction $n-i|(n-i+1)+j$ only can when $j=n-i-1$ cause the other bigger numbers are already used. Hence one way: $n,n-1,n2,\cdots,1$ which satisfy the question. If $n=2m+1$ There can't be three consecutive odd numbers. $x,2m-1,y$ $x,y$ can't be both odd, so $x,y=2m,2m-2$ or $x+y=2m-1.$ That first case gives again the known sequence or $2m,2m-1 \cdots 2m-i+1,2m-i,2m+1,i+1$ happens ( $2m-i+1>i+1$ => $i\le m$ somewhere and then we find (when searching/looking good) that $i=m$ satisfy this and gives a new one. The second case: $2m+1$ has at least one odd neighbour, hence $2m-1$ don't may have an other, so $2m-1,2m+1,2$ is start. Looking left, we would have again odd number when $4m+1<3(2m-1)$ so $n=3,5$ left. Hence there is only $1$ way, except if $n=5$, but we constructed this one already. Hence for odd numbers from $\ge 5$ we have $2.$
01.05.2012 18:50
We can find a bijection between good permutations for $n$ and those good permutations for $n-1$ that have two adjacent numbers which add up to $n$ .Let $(\dots a \: x \: n \: y \: b \dots )$ be one good permutation for $n$ , then $n \mid x+y$ and $x+y \leq n-1 + n-2$ $\implies$ $x+y=n$ . Now omit $n$ , I claim you get a good permutation for $n-1$ . Indeed , $x \mid a+n \Leftrightarrow x \mid a+(x+y) \Leftrightarrow x \mid a+y$ and same story goes for $y$ and its two new neighbors . So we find our desired bijection . Now , note that for even $n$ , as we don't have two consecutive even numbers (It force all numbers being even!) the two adjacent number of $n-1$ are both even so they add up to $2(n-1)$ and not $n-1$ . So these two numbers have to be $n,n-2$ . An easy induction show that all numbers should be consecutive around the circle and It gives $2$ ways for even $n$ . According to above bijection , $n+1$ (it's odd) should come between $2$ adjacent numbers with sum $n+1$ , when $1,2,\dots,n$ come in this order . So $n+1$ is either between $(n,1)$ or $(\frac{n}{2} , \frac{n+2}{2})$ . It gives us $4$ ways for $n \geq 4$ . Hence final answers are : $2$ ways for $n=3$ $2$ ways for $n=2k$ ($k \geq 2$) $4$ ways for $n=2k+1$ ($k \geq 2$)
01.05.2012 22:39
mahanmath, can you find a second way for $n=7?$ So we had $1234567$ and in the reverse order (you count that too), but I proved there isn't an other way, so one of us is wrong.
01.05.2012 22:43
SCP wrote: mahanmath, can you find a second way for $n=7?$ So we had $1234567$ and in the reverse order (you count that too), but I proved there isn't an other way, so one of us is wrong. $1237456$ is also good
01.05.2012 23:02
Thanks. I was the one who was wrong, but found the mistake in the proof and will edit that part.