Jump of a frog Problem | I.S.I. B.Math 2014 Solution

This post contains an interesting problem from ISI BMath 2014 based on the jump of a frog and the lotus. Solve and enjoy this problem.

Problem: Jump of a frog Problem

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 3rd jump it skips 3 leaves and 4th 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.

Discussion:
Suppose we number the leaves as 1, 2, 3, upto n. Leaf 1 being the starting point of the frog.
Step 1 - Leaf 1
Step 2 - Leaf 3 (because the frog skips 1 leaf)
Step 3 - Leaf 6 (1+2+3) ( because it skips 2 leaves in second jump)
In this manner the frog will be in the
$\mathbf{ \frac{m(m+1)}{2} }$ (modulo n) leaf in the mth step.

If n = 2k+1 (that is if we have odd number of leaves) then in the 2k step and 2k+1 step it will be on Leaf 2k+1.
This is because $\mathbf{\frac{(2k+1)(2k)}{2} = k(2k+1) \equiv 0 \text{mod} 2k+1 }$ and $\mathbf{\frac{(2k+1)(2k + 2)}{2} = (k+1)(2k+1) \equiv 0 \text{mod} 2k+1 }$
Also notice that after the first 2K+1 steps the position of the frog repeats.
This is because for even value (2m) $\mathbf{\frac{2m(2m+1)}{2} \equiv m(2m+1) \equiv \frac{(2m + 2k + 1) (2m+ 2k + 2)}{2} \equiv (2m+2k+1)(m+k+1) mod 2k+1 }$
Since $\mathbf{ (2m+2k+1)(m+k+1) \equiv (2m)(m+k+1) + (2k+1)(m+k+l) \equiv 2m^2 + 2mk + 2m }$
But $\mathbf{ 2m^2 + 2mk + 2m \equiv 2m^2 + m + 2mk + m \equiv m(2m+1) + m(2k+1) \equiv m(2m+1) mod 2k+1 }$
Similarly for odd values (2m+1)
$\mathbf{\frac{(2m+2)(2m+1)}{2} \equiv (m+1)(2m+1) \equiv \frac{(2m + 1 + 2k + 1) (2m + 1 + 2k + 2)}{2} \equiv (m+k+1)(2m+2k+3) mod 2k+1 }$
Since $\mathbf{(m+k+1)(2m+2k+3) \equiv (2m+2)(m+k+1) + (2k+1)(m+k+l) \equiv 2m^2 + 2mk + 2m + 2m + 2k +2 }$
But $\mathbf{ (2k+1)m + (2k+1) + 1 + 3m + 2m^2 \equiv (m+1)(2m+1) mod 2k+1 }$

As every 2k+1 values (modulo 2K+1) need to be distinct if the frog visits every leaf, it visits leaf number 2k+1 in the last two steps, hence some leaf must be missing.

Special Note

Extension: The frog may visit each leaf if and only if number of leaves is a power of 2.

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 3rd jump it skips 3 leaves and 4th 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.

Discussion:
Suppose we number the leaves as 1, 2, 3, upto n. Leaf 1 being the starting point of the frog.
Step 1 - Leaf 1
Step 2 - Leaf 3 (because the frog skips 1 leaf)
Step 3 - Leaf 6 (1+2+3) ( because it skips 2 leaves in second jump)
In this manner the frog will be in the
$\mathbf{ \frac{m(m+1)}{2} }$ (modulo n) leaf in the mth step.

If n = 2k+1 (that is if we have odd number of leaves) then in the 2k step and 2k+1 step it will be on Leaf 2k+1.
This is because $\mathbf{\frac{(2k+1)(2k)}{2} = k(2k+1) \equiv 0 \text{mod} 2k+1 }$ and $\mathbf{\frac{(2k+1)(2k + 2)}{2} = (k+1)(2k+1) \equiv 0 \text{mod} 2k+1 }$
Also notice that after the first 2K+1 steps the position of the frog repeats.
This is because for even value (2m) $\mathbf{\frac{2m(2m+1)}{2} \equiv m(2m+1) \equiv \frac{(2m + 2k + 1) (2m+ 2k + 2)}{2} \equiv (2m+2k+1)(m+k+1) mod 2k+1 }$
Since $\mathbf{ (2m+2k+1)(m+k+1) \equiv (2m)(m+k+1) + (2k+1)(m+k+l) \equiv 2m^2 + 2mk + 2m }$
But $\mathbf{ 2m^2 + 2mk + 2m \equiv 2m^2 + m + 2mk + m \equiv m(2m+1) + m(2k+1) \equiv m(2m+1) mod 2k+1 }$
Similarly for odd values (2m+1)
$\mathbf{\frac{(2m+2)(2m+1)}{2} \equiv (m+1)(2m+1) \equiv \frac{(2m + 1 + 2k + 1) (2m + 1 + 2k + 2)}{2} \equiv (m+k+1)(2m+2k+3) mod 2k+1 }$
Since $\mathbf{(m+k+1)(2m+2k+3) \equiv (2m+2)(m+k+1) + (2k+1)(m+k+l) \equiv 2m^2 + 2mk + 2m + 2m + 2k +2 }$
But $\mathbf{ (2k+1)m + (2k+1) + 1 + 3m + 2m^2 \equiv (m+1)(2m+1) mod 2k+1 }$

As every 2k+1 values (modulo 2K+1) need to be distinct if the frog visits every leaf, it visits leaf number 2k+1 in the last two steps, hence some leaf must be missing.

Special Note

Extension: The frog may visit each leaf if and only if number of leaves is a power of 2.

4 comments on “Jump of a frog Problem | I.S.I. B.Math 2014 Solution”

I.S.I. B.Stat B.Math Subjective 2014 | CHEENTA Blog says:
May 18, 2014 at 8:40 pm
[…] 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 3rd jump it skips 3 leaves and 4th 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. Solution […]
Reply
Dave says:
July 6, 2014 at 5:49 pm
What if we removed the leaf as we went around the circle? Which is to say it can't go to a leaf more than once. For example, if n = 10, in the post the solution should be leaf 5 in the 10th step. But with removal, the solution should be leaf 7 in the 10th step. I don't know how to express this mathematically.
Reply
1. Alexander says:
  April 30, 2019 at 10:11 am
  When you are removing a leaf everytime after u reach there, u will reach every leaf no matter how many are there. This is because if you go on eliminating leaves eventually u will be left with only 2 leaves and then u remove one n then only 1 is left after which even that one goes out. So there is no chance of you being able to not visit any leaf even if it is odd or even or whatever
  Reply
neelanjan mondal says:
October 17, 2015 at 8:08 pm
give me the solution of problem 1 and problem 4 of b stat and b math 2014
Reply