During a break, $n$ children at school sit in a circle around their teacher to play a game. The teacher walks clockwise close to the children and hands out candies to some of them according to the following rule: He selects one child and gives him a candy, then he skips the next child and gives a candy to the next one, then he skips 2 and gives a candy to the next one, then he skips 3, and so on. Determine the values of $n$ for which eventually, perhaps after many rounds, all children will have at least one candy each.
Problem
Source: APMO 1991
Tags: combinatorics unsolved, combinatorics
07.04.2006 11:11
Not hard,$n=2^a(a\in N)$
07.04.2006 15:16
because they are the only numbers you cannot find some following numbers whose sum is $n$. Naphthalin
29.01.2007 03:26
jin wrote: Not hard,$n=2^{a}(a\in N)$ Can you please post your solution? (or someone else)
30.01.2007 21:07
Each child will be a number of the set $\{0,1,2, ... , n-1\}$, written on clockwise direction. The first child which will receive a candy is the $1$. The $k$-th is $\frac{k(k+1)}{2}(mod$ $n)$. If $n$ is odd, then $\frac{(n+2)(n+1)}{2}= 1 (mod$ $n)$. This means that $n+1$-th child is the first one, so that the teacher will take the same steps. It is obvious that the $n-1$-th and $n$-th children are the same child. So there is one child that didn't take a candy, because there is one that took two on the first teacher round. If $n$ is even. Let $C_{(1,i)}= \{i,i+\frac{n}{2}\}$, for each $i \in \{1,2,...,\frac{n}{2}\}$. Consider a circle with $C_{(1,i)}$ written on clockwise direction. Note that the steps taken on the circle with $n$ children will be seen as if the teacher had $\frac{n}{2}$ alumnies on the latter circle. So $\frac{n}{2}$ must be even, otherwise there will exist a set $C_{(1,i)}$ which wasn't awarded with a candy. If $\frac{n}{2}$ is even, call $C_{(2,i)}= \{C_{(1,i)}, C_{(1,i+\frac{n}{4})}\}$. And the same argument will be taken. Following this, the only possibility to each child get a candy is $n=2^{k}$, for some $k$ positive integer.
04.08.2020 13:11
Answer: $n = 2^k (k \in \mathbb{Z}, k \geq 0)$ Each child will be a number of the set $\{0,1,2, ... , n-1\}$, written on clockwise direction. The first child which will receive a candy is the $1$. The $k$-th is $\frac{k(k+1)}{2}(mod$ $n)$. 1) $n$ have odd prime divider $p$. Let $\forall a \in \mathbb{N}$ $\exists b \in \mathbb{N}: \frac{b(b+1)}{2} \equiv a (mod$ $n) \implies \forall a \in \mathbb{N}$ $\exists b \in \mathbb{N}: \frac{b(b+1)}{2} \equiv a (mod$ $p)$ $\forall r \in \mathbb{N}:\frac{r(r+1)}{2}\equiv \frac{(r+p)(r+p+1)}{2} (mod$ $p) \implies \forall a, b \in [1, ... p]: \frac{a(a+1)}{2} \not\equiv \frac{b(b+1)}{2}(mod$ $p)$ $\frac{p(p+1)}{2} \equiv \frac{(p-1)((p-1)+1)}{2}(mod$ $p)$ - contradiction. 2) $n = 2^k (k \in \mathbb{Z}, k \geq 0)$ Let $\exists a>b: a, b \in [0, ... 2^k - 1]$ and $\frac{a(a+1)}{2} \equiv \frac{b(b+1)}{2}(mod$ $2^k) \implies (a-b)(a+b+1)\vdots 2^{k+1}$ $\implies (a-b)\vdots 2^{k+1}$ or $(a+b+1)\vdots 2^{k+1}$ but $0<(a-b)<2^{k+1}$ and $0<(a+b+1)<2^{k+1}$ - contradiction. $\implies \frac{0(0+1)}{2}, ... \frac{(2^k-1)((2^k-1)+1)}{2}$ are different $(mod$ $2^k)$ $\implies \frac{2^{k+1}(2^{k+1}+1)}{2}; \frac{1(1+1)}{2}, ... \frac{(2^k-1)((2^k-1)+1)}{2}$ are different $(mod$ $2^k)$ $\implies$ after $2^{k+1}$ rounds, all children will have at least one candy each.