In the problems based on invariance principle, a final stage is reached after performing certain steps. We are often asked to find the final stage. A very interesting branch of mathematics!
1. The numbers 1, 2, 3, .....n are written in the natural order. Numbers in odd places are struck off to form a new sequence. This process is continued till only one number is left.
Q 1: If n = 1997, the number left is?
Q 2: If the number left is 512, the maximum possible value of n is
Solution:
The given sequence is 1, 2, 3, ....n
After step 1, we have 2, 4, 6, 8, ......
After step 2, we have 4, 8, 12, 16, ....
After step 3, we have 8, 16, 24, 32, ......
After the last step (m th step) we have the highest power of 2m ≤ n.
1. If n = 1997, after step 10, we are left with only 1024 (as 210 ≤ 1997)
2. If the last number left is 512, the maximum possible value of n is 1023.
2. Given a set of n rays in a plane, we define a reversal as the operation of reversing precisely one ray and obtaining a new set of n rays.
Q1: if n = 2001 and if k reversals are performed such that all the rays are reversed, then a possible value of k is
a. 4000 b. 4002 c. 2011 d. 1999
Sol: there are n rays. If we reverse all of them, we would have a complete reversed set after n reversals. After that any reversal that we perform has to be undone with another reversal to obtain complete reversal. We can have a complete reversal after k reversals if k = n + 2m (m ∈ N). i.e., k could be some number greater than (or equal to) n and of the same type (even/odd)
So n = 2001 then k = 2001 + 2m
So k = 2011
Q 2: If there are n rays and all of them are reversed after 2006 reversals, then a possible value of n is
a. 2007 b. 2003 c. 2008 d. 2002
Sol: n has to be same number less than (or equal to) k and of the same type as k.
k = 2006 then n = 2002.
3. There are 150 'zeroes' and 151 'ones' written on a black board. A step involves choosing three digits and replacing them with a single digit. If all the three digits are identical, they are replaced with the same digit. Otherwise, the digit that appears twice replaces the three chosen digits. What is the minimum number of steps after which there will be no zero written on the blackboard?
If we strike out 3 zeros, we are in effect reducing two zeroes. So we need 74 steps to reduce 148 zeroes. There are 2 zeroes and 151 ones left now. The remaining zeroes can be reduced in 2 steps. Hence the answer is 76.
4. P is a set of four numbers 1, 2, 3 and 1. In every step, one is added to any two numbers in the set P. In how many such steps is it possible to make all the four numbers in the set P equal?
Sol: If all the four numbers are equal, then their sum in the end of the process must be multiple of 4.
Now the sum of the given numbers is equal to 7. Each time we are adding 1 to two of any two numbers, so the sum increases by 2 each time. So the sum never becomes a multiple of 4 as odd + even = always odd.
5. The integers 1, 2, … , 40 are written on a blackboard. The following operation is then repeated 39
times: In each repetition, any two numbers, say a and b, currently on the blackboard are erased and a new
number a + b – 1 is written. What will be the number left on the board at the end?
(1) 820 (2) 821 (3) 781 (4) 819 (5) 780
Initial sum of the number 1 to 40 = $\displaystyle\frac{{n\left( {n + 1} \right)}}{2} = \frac{{40 \times 41}}{2} = 840$
After erasing two numbers a and b, and replacing with (a + b − 1), the new sum of the terms of the
sequence = 820 − 1
Similarly, after every operation, the sum of the terms of the sequence reduces by 1.
∴ The last number left (i.e. final sum) = 820 − 39 = 781
Hence, option 3.
6. 40 people are sitting around a circular table. Starting from 1 every 2nd person is killed. This process continues till only one person remains. How is the survivor? (Josephus riddle)
Sol 1:
Write the given number in Binary form: 101000
Shift the left digit to the right hand side: 010001
Convert this number into decimal and this could be the number of the survivor: 17
Sol 2: Write the given number as a sum of 2K + M where K should be maximum power less than the given number.
Survivor number is given by 2M + 1
this this case 40 < 25 + 8
So M =8, Survivor number = 2(8) + 1 = 17
7. Consider the set N = {2, 3, 4, ..., 2n + 1}, where n is a positive integer larger than 10005. If O is the average of the odd integers in N and E is the average of the even integers in N then what is the value of O –E?
a. 0 b. 1 c. n+ 1/2n d. 10006
1. The numbers 1, 2, 3, .....n are written in the natural order. Numbers in odd places are struck off to form a new sequence. This process is continued till only one number is left.
Q 1: If n = 1997, the number left is?
Q 2: If the number left is 512, the maximum possible value of n is
Solution:
The given sequence is 1, 2, 3, ....n
After step 1, we have 2, 4, 6, 8, ......
After step 2, we have 4, 8, 12, 16, ....
After step 3, we have 8, 16, 24, 32, ......
After the last step (m th step) we have the highest power of 2m ≤ n.
1. If n = 1997, after step 10, we are left with only 1024 (as 210 ≤ 1997)
2. If the last number left is 512, the maximum possible value of n is 1023.
2. Given a set of n rays in a plane, we define a reversal as the operation of reversing precisely one ray and obtaining a new set of n rays.
Q1: if n = 2001 and if k reversals are performed such that all the rays are reversed, then a possible value of k is
a. 4000 b. 4002 c. 2011 d. 1999
Sol: there are n rays. If we reverse all of them, we would have a complete reversed set after n reversals. After that any reversal that we perform has to be undone with another reversal to obtain complete reversal. We can have a complete reversal after k reversals if k = n + 2m (m ∈ N). i.e., k could be some number greater than (or equal to) n and of the same type (even/odd)
So n = 2001 then k = 2001 + 2m
So k = 2011
Q 2: If there are n rays and all of them are reversed after 2006 reversals, then a possible value of n is
a. 2007 b. 2003 c. 2008 d. 2002
Sol: n has to be same number less than (or equal to) k and of the same type as k.
k = 2006 then n = 2002.
3. There are 150 'zeroes' and 151 'ones' written on a black board. A step involves choosing three digits and replacing them with a single digit. If all the three digits are identical, they are replaced with the same digit. Otherwise, the digit that appears twice replaces the three chosen digits. What is the minimum number of steps after which there will be no zero written on the blackboard?
If we strike out 3 zeros, we are in effect reducing two zeroes. So we need 74 steps to reduce 148 zeroes. There are 2 zeroes and 151 ones left now. The remaining zeroes can be reduced in 2 steps. Hence the answer is 76.
4. P is a set of four numbers 1, 2, 3 and 1. In every step, one is added to any two numbers in the set P. In how many such steps is it possible to make all the four numbers in the set P equal?
Sol: If all the four numbers are equal, then their sum in the end of the process must be multiple of 4.
Now the sum of the given numbers is equal to 7. Each time we are adding 1 to two of any two numbers, so the sum increases by 2 each time. So the sum never becomes a multiple of 4 as odd + even = always odd.
5. The integers 1, 2, … , 40 are written on a blackboard. The following operation is then repeated 39
times: In each repetition, any two numbers, say a and b, currently on the blackboard are erased and a new
number a + b – 1 is written. What will be the number left on the board at the end?
(1) 820 (2) 821 (3) 781 (4) 819 (5) 780
Initial sum of the number 1 to 40 = $\displaystyle\frac{{n\left( {n + 1} \right)}}{2} = \frac{{40 \times 41}}{2} = 840$
After erasing two numbers a and b, and replacing with (a + b − 1), the new sum of the terms of the
sequence = 820 − 1
Similarly, after every operation, the sum of the terms of the sequence reduces by 1.
∴ The last number left (i.e. final sum) = 820 − 39 = 781
Hence, option 3.
6. 40 people are sitting around a circular table. Starting from 1 every 2nd person is killed. This process continues till only one person remains. How is the survivor? (Josephus riddle)
Sol 1:
Write the given number in Binary form: 101000
Shift the left digit to the right hand side: 010001
Convert this number into decimal and this could be the number of the survivor: 17
Sol 2: Write the given number as a sum of 2K + M where K should be maximum power less than the given number.
Survivor number is given by 2M + 1
this this case 40 < 25 + 8
So M =8, Survivor number = 2(8) + 1 = 17
7. Consider the set N = {2, 3, 4, ..., 2n + 1}, where n is a positive integer larger than 10005. If O is the average of the odd integers in N and E is the average of the even integers in N then what is the value of O –E?
a. 0 b. 1 c. n+ 1/2n d. 10006
Sol: No need to solve this question. Simply take n = 5. So N = {2, 3, 4, 5, ......11}
Now average of add integers = (3 + 5 + ........11)/5 = 7.
Average of Even integers = (2 + 4 + .....10) / 5 = 6
O - E = 1
So correct answer is option B.
8. There are 13 which, 15 black, 16 red hats on a table. In one step, you may chose two hats of different colors and replace each one by a hat of the third color. After how many steps this can be reached?
Let the initial number of hats are (a, b, c). In one step the hats color may change into one of the following (a+2, b-1, c-1), (a-1, b+2, c-1), (a-1, b-1, c+2). In each of these cases, difference between any two colored hats should be divisible by 3 to reach mono chromatic stage. ie., a + b + c should also be divisible by 3.
In this case sum is not divisible by 3 so the final stage cannot be reached.
9. A dragon has 100 heads. A soldier can cut off 15, 17, 20 or 5 heads, respectively with one blow of his sword. In each of these cases, 24, 2, 14, 17 new heads grow on its shoulders. If all heads are cut off, the dragon dies. Can the dragon ever die?
Sol: Here the difference in the cutoff heads and newly grown heads is 3. 100 is not divisible by 3. The dragon never die.
