A weekend puzzle
In a class there were 40 students with roll numbers 1 thru 40. One day, the teacher got them all to sit around in a circle sequentially in the order of their roll numbers (1 thru 40). (Of course 40 sat next to 39 on one side and 1 on the other). She then gave a wand to student number 1. What the student had to do is turn towards the next student (which would be #2) and tag him/her with the wand. Upon tagging, the tagged student steps back and is out of the game and the wand is then handed to the next student – which would be student #3 in this case
Now student #3 does the same thing – tags student #4 who steps back and is out of the game and then the wand is handed to #5.
This keeps going on and on (in circles) till only one student is left.
Can you figure out which student was the last one left?
Now for the answer:
Many of you have gotten to the right answer – 17. Not sure what the method used was but here is a generic way to solve the problem. Some have gotten to 33 – must be a quick mix up. Actually 17 and 33 are the last ones left and then 17 stays. Many got 1 but I am not sure how
Some of you have tried the brute force way – by actually enumerating every round but obviously that will not work for a larger number – like 1000. Although, I am not entirely sure how a teacher would deal with a classroom that big 🙂
First Step:
Let’s start with the first person who gets the wand. Now if that person is “1”, we realize that in first round all the even numbers step back. We are left with 1,3,5,7…. So, if there are are even number of students (number divisible by 2) to begin with, “1” survives and gets the wand back.
Now let’s see what happens as “1” starts the second round. Again, by same logic, if there are even number left (after first round of elimination), then “1” survives and gets the wand back. The original number than as to be a factor of 4.
During the next round, the same logic continues…. If the number is divisible by 8, then again after third round, “1” survives and gets the wand back.
Thus, in general, if the number of students is “2 to the power n” (2^n), then “1” will be the last person standing.
Second Step:
But we have 40 which is not a power of 2. So, what we do? we keep playing this till we get to a power of 2. The power of 2 closest to (and lower than) 40 is 32. To get to 32 people, we have to eliminate 8 people.
In first round itself, the 8th elimination happens (in fact in first round, 20 eliminations happen) and that 8th elimination happens when we have student 15 tagging student 16 and handing the wand to student 17.
Now we have student 17 holding the wand and 32 students (a power of 2) left. By logic of first step, 17 will be the last person standing.
This logic can be extended to any number you can think of.