There are 1000 lily pads on a pond arranged in a circle and labelled 1, 2, ..., 1000 in order. (The first four lily pads may also be described using the labels 1001, 1002, 1003 and 1004, respectively.) The first n lily pads are each occupied by a frog with the remaining lily pads not occupied.
Each minute, exactly one of the frogs makes a move. Suppose the frog is on lily pad k. That frog may either:
(i) Swim to lily pad k + 4 or k - 4, provided that it is not occupied; or
(ii) Jump to lily pad k + 3 or k - 3 provided that this lily pad is not occupied and the two lily pads jumped over are both occupied. When this happens, the two frogs that were jumped over dive into the pond and don't participate in any further moves.
For which values of n is it possible, by a sequence of moves, to end with exactly one frog remaining on the lily pads?
n=4 ✗ Since each jump removes two frogs, we cannot go from 4 frogs to 2 and then to 1.
Even values of n are impossible, since the parity of the number of frogs does not change: each jump removes two frogs.
Check n=5.
Consider the 1000 lily pads modulo 4. Let n(0), n(1), n(2), and n(3) be the numbers of frogs on lily pads whose labels have remainders 0, 1, 2, and 3, respectively.
Action (i) has no effect on n(0), n(1), n(2), or n(3).
Action (ii):
When n=5:
n(0)1n(1)2n(2)1n(3)1
Consider the parity of n(0), n(1), n(2), and n(3) modulo 2.We need to apply action (ii) twice, since
5−2×2=1.
But then three of n(0), n(1), n(2), and n(3) are odd. So we cannot have exactly one frog.
Check n=7.
7−3×2=1.
So we need to use action (ii) three times. Frogs are on lily pads 1,2,3,4,5,6,7.So we cannot have one frog after three applications of action (ii), since n(1), n(2), and n(3) are odd.
Check n=9.So n=9 is good.
Check n=11.Now we have 9 frogs on consecutive lily pads.
By Hint 9, n=11 is good too.
n1✓2×3✓4×5×6×7×8×9✓10×11✓
We can guess that 8k+1 and 8k+3 are good, and 8k+5 and 8k+7 are bad.
Let's first reject 8k+5 and 8k+7.
8k+5−2(4k+2)=1.
So we need to use action (ii) 4k+2 times.
For 8k+5, the frogs initially occupy lily pads
1,2,3,…,8k+5.
After 4k+2 applications of action (ii), three of n(0), n(1), n(2), and n(3) are odd. So we cannot have only one frog.
Let's reject 8k+7.
8k+7−2(4k+3)=1.
So we need to use action (ii) 4k+3 times.
For 8k+7, the frogs initially occupy lily pads
1,2,3,…,8k+7.
After 4k+3 applications of action (ii), three of n(0), n(1), n(2), and n(3) are odd. So we cannot have only one frog.