In the problems based on in variance principle, a final stage is reached after performing certain steps. We are often asked to find the final stage.
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.
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.