Question

Consider an infinite sequence of positions 1, 2, 3, . . . and suppose we have a stone at position 1 and another stone at position 2. In each step, we choose one of the stones and move it according to the following rule: Say we decide to move the stone at position i; if the other stone is not at any of the positions i + 1, i + 2, . . . , 2i, then it goes to 2i, otherwise it goes to 2i + 1.

For example, in the first step, if we move the stone at position 1, it will go to 3 and if we move the stone at position 2 it will go to 4. Note that, no matter how we move the stones, they will never be at the same position.

Use induction to prove that, for any given positive integer n, it is possible to move one of the stones to position n. For example, if n = 7 first we move the stone at position 1 to 3. Then, we move the stone at position 2 to 5 Finally, we move the stone at position 3 to 7.

Answer 1

IF YOU HAVE ANY DOUBTS COMMENT BELOW I WILL BE TTHERE TO HELP YOU..ALL THE BEST..

ANSWER:

Base case :- For n = 1,2,3,4 , we can always move one stone at either of these positions such that highest position index of stone is position n.

Induction hypothesis :- For all n<=m, we can always move the stones such that out of two stones, stone at highest position index among two stones is at position n for any n<=m.

Inductive step :- For n = m+1.

Case 1:- If m+1 is even number.

Then by induction hypothesis, we can move one stone at position (m+1)/2 without other stone at position greater than (m+1)/2. Then since there are no stone at any of position (m+1)/2+1 , (m+1)/2+2,...,(m+1) , so in the next step, stone can be moved at position (m+1).

Case 2:- If m+1 is odd number.

Then by induction hypothesis, we can move one stone at position m/2 without other stone at position greater than m/2. Then we can move the second stone at lower position to higher index. When we move the second stone at higher index, there will be time when second stone will cross the index m/2. Since second stone will move either twice of its index or one more than twice of its index, hence the position of second stone when it just cross the stone at index m/2 will be in range m/2+1 to m.

Hence for the first stone at position m/2, since there is another stone between position m/2+1 to m, hence second stone will move to position 2*m/2 + 1 = m+1. Hence we will be able to move stone at position m+1.

Hence our induction hypothesis is correct for n=m+1, and hence the statement is true.

I HOPE YOU UNDERSTAND..

PLS RATE THUMBS UP..ITS HELPS ME ALOT..

THANK YOU...!!

Answer 2

Why is the base case of 1 allowed if its position is less than 2 which is the starting position of another stone