Homework- question $n (> 1)$ lotus leafs are arranged in a circle. A frog jumps from a particular leaf by the following rule: It always moves clockwise. From staring point it skips 1 leaf and jumps to the next. Then it skips $2$ leaves and jumps to the following. That is in the $3^{rd}$ jump it skips $3$ leaves and $4^{th}$ jump it skips $4$ leaves and so on. In this manner it keeps moving round and round the circle of leaves. It may go to one leaf more than once. If it reaches each leaf at least once then $n$ (the number of leaves) cannot be odd.
 A: We can label the leaves 0 to $n-1$. We start on leaf 0. On our first move we skip leaf 1 and land on leaf 2. Then we skip leaves 3 and 4 and land on leaf 5. Each jump we skip one more leaf than we did the previous turn before landing. We can use this information to come up with a function that describes which leaf we are on after $k$ jumps. This function turns out to be $.5k(k+3) \pmod{n}$. This formula is derived from the formula for the sum of the first $k$ natural numbers. We can now think of the outputs of this function as a sequence.
The first trick is to see that when $n$ is odd, the sequence has period $n$. In other words, you have to show that $.5k(k+3) \equiv .5(k+n)(k+n+3) \pmod{n}$. 
The second trick is to see that plugging in $n-1$ and $n-2$ into the function result in the same value. That is, you have to show that $.5(n-1)(n-1+3) \equiv .5(n-2)(n-2+3) \pmod{n}$. 
Once we know those two things, we can put them together to get the result using the pigeonhole principle. When $n$ is odd, our sequence repeats every $n$ terms. So if we want to get every distinct residue, we have to do so within the first $n$ terms. However, we've seen that the $n-1$ and $n-2$ terms give us the same value. Thus at least one value didn't show up in the first $n$ terms. Therefore we can say that we can't land on all of the leaves when $n$ is odd. So if we do manage to land on all of the leaves, $n$ can't be odd.
Another version of the second trick is to see that plugging $n-3$ into our function gives us 0. Since we start on 0, again we have the case where a value is repeated within the first $n$ terms, and so by the pigeonhole principle we can't get all of the distinct residues. 
One more observation is that it seems that the frog will only succeed if $n$ is a power of 2. There might be a more simple or clever argument based on this idea.
