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
2 years, 4 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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.

- 2 years, 4 months ago

Log in to reply

thanks sir

- 2 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...