Waste less time on Facebook — follow Brilliant.
×

Frog problem

Consider \(n>1\) lotus leaves placed around a circle. A frog jumps from one leaf to another in the following manner. It starts from some selected leaf. From there it skips exactly one leaf in the clockwise direction and jumps to the next one. Then it skips exactly two leaves in the clockwise direction and jumps to the next one and so on. Notice that the frog may visit the same leaf more than once. Suppose it turns out that if the frog continues this way then all the leaves are visited by the frog sometime or the other. Show that \(n\) cannot be odd.

Note by Pratik Roy
8 months, 1 week ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Looks intimidating at first!
On the \(n^{th} \) jump, the frog skips \( n \) leaves.
Let's number the leaves as such: \( 0, 1, 2, ..., n - 1 \), such that the starting leaf is leaf \(0\).
Let \(T(n) \) be the number of the leaf on which the frog is on, after \( n \) jumps.
\( T(0) = 0 \).
Clearly, \(T(n) \in {0, 1, 2, ..., n - 1}\).

We have, \( T(k) \equiv T(k - 1) + k + 1 \mod{n} \) (as there are k leaves skipped).

\(\Rightarrow T(n) \equiv \dfrac{(n + 1)(n + 2)}{2} - 1 \mod{n} \)

If n is odd, \(\dfrac{(n + 1)(n + 2)}{2} - 1 \) is a multiple of \( n \) (as 2 does not divide \(n\)).
\(\Rightarrow T(n) \equiv 0 \mod {n} \Rightarrow T(n) = 0 \).

But this means the frog has returned to its original position.

Now, skipping \( n + 1 \) leaves, is the same as skipping \(1\) leaf.
Thus the cycle repeats - which means we only have to check the first cycle.

But, see that \( T(n - 1) - T(n - 2) \equiv (n - 1) + 1 \equiv 0 \mod{n} \).
This means that the frog remained in its place for the \((n - 1)^{th} \) jump.
Thus, the frog visited at most \( n - 1 \) leaves in the \( n \) jumps of the cycle - and repeats in this for every cycle, and definitely missing at least one leaf. Ameya Daigavane · 8 months ago

Log in to reply

@Ameya Daigavane thanks sir Pratik Roy · 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...