Bead Removal
There are 100 beads on a necklace. 1 of them is red, the rest are blue. Working in the clockwise direction, we start from the red bead and remove every other bead. Right when the red bead is removed, how many blue beads are there left on the necklace?
Note: The first bead removed is the blue bead that is right next to the red bead in the clockwise direction.
The answer is 12.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
5 solutions
Comments and replies:
Calvin:
This is correct (after replacing ball with bead).
It was tempting to generalize after 2 cycles that the red bead is the last one removed. You were able to explain why this is not true.
Can you think about how to solve the general case, where there are N beads on the necklace?
Kristian M:
For a general N beads [with 1 red bead and (N-1) blue beads], we can express N = (2k-1) 2^q for some integers k and q with k>0 and q>=0. Note that If q = 0, then we can remove the red bead after the first cycle leaving us with k blue beads. This is because If q = 0, then N is odd. We can label the beads starting from the right of the red bead as 1, 2, 3, ... (2k - 1) and in the first cycle we remove beads 1, 3, ... (2k -1) or a total of k balls, including the red ball, leaving us with (2k-1) - k = k -1 blue balls. Now if q>0, then we can't remove the red bead in the first cycle since the label of the red bead is an even number and we are removing odd-numbered beads. The last bead removed in the first cycle is the bead on the left of the red bead. Hence we removed a total of N/2 beads. On the second cycle, we are now considering the case when we have N/2 beads. Thus for every positive r<=q, after the rth cycle, we are left with N/2^r = (2k-1) 2^(q-r) beads with one of them red. Thus, after q cycles, we are left with 2k-1 beads and on the (q+1)th cycle, we can now remove the red bead leaving us with k -1 blue balls.
Consider a 'round' to be cycling through the necklace and returning to the red bead. A bead will be removed when it is an even number of beads away from the last bead that was removed. In the first round, the red bead is 99 beads away from the first blue bead that is removed, so the red bead will not be removed. In the first round, 50 blue beads are removed, leaving 9 9 − 5 0 = 4 9 blue beads. In the second round, the red bead is 4 9 beads away from the first blue bead that is removed, so the red bead will not be removed. In the second round, 25 blue beads are removed, leaving 4 9 − 2 5 = 2 4 blue beads. In the third round, the red bead is 24 beads away from the first blue bead that is removed, so the red bead will be removed. So, we have that 12 blue beads are removed, followed by the red bead, hence there are 2 4 − 1 2 = 1 2 blue beads remaining when the red bead is removed.
Number the beads 1 to 100 starting from the red bead as #1. The last blue bead after the red bead is #100. As removal starts at #2 all even-numbered beads are removed. For the first round 50 (100/2) beads are removed. Renumber the beads again the last bead is #50. Again even-numbered beads are removed and the second round 25 beads are removed. Renumber again,the last bead is #25, a odd number. This time the last bead is not removed and the first red bead will be removed and our required condition is met. The number of beads removed in the third round is 12. Therefore the remaining blue beads after three rounds of removal are 99 - 50 - 25 - 12 = 12.
Note that the red bead can be labeled bead 0 or bead 100 [I think this does not change the answer].
Now bead 1 is removed first. Then bead 3 is removed. Then bead 5 is removed. It can be concluded that first, all the odd numbered beads are removed. So proceeding this way, bead 99 is removed. Then bead 2 is removed. Then bead 6 is removed. Then bead 10 is removed. So we can conclude that the beads numbered of the form 4k+2 are removed [k being an integer]. Proceeding this way, bead 98 is removed. Then bead 4 is removed. Then bead 8 is removed. So we can conclude that all beads numbered of the form 4k are removed. Proceeding this way, bead 100 is removed.
So before the red bead is removed, all the blue beads numbered odd, of the form 4k, and of the form 4k+2 are removed.
Now to find the number of odd beads from 1 to 100.
They are listed below.
1, 3, 5, 7, 9, 11, 13, ..., 99
They form an A.P with the common difference 2, initial term 1, and final term 99.
So if 99 is the pth term...
99=1 + 2(p-1) Or, p-1= 98/2= 49 Or, p= 50
So 50 blue beads are removed first.
Now to find the number of beads of the form 4k+2 from 1 to 100.
They are listed below.
2, 6, 10, 14, 18, ..., 98
They form an A.P with intial term 2, common difference 4, and final term 99.
So if 98 is the qth term...
98= 2 + 4(p-1) Or, p= 15
So after that, 15 blue beads are removed.
Now to find the number of beads of the form 4k.
They are listed below.
4, 8, 12, 16, 20, 24, ... 96 [100 is not included since we want to find no. of blue beads before the red bead is removed]
They form an A.P with initial term 4, final term 96, and common difference 4.
So if 96 is the rth term...
96= 4 + 4(r-1)
Or, r=14
Therefore, after that 14 beads were removed.
So before the red bead was removed, the number of blue beads removed are 50+15+19= 79
This leaves out 100-79=21 beads. Out of these 21 beads, one of them is the red bead.
So there are 20 blue beads before the red bead is removed.
Comments and replies:
Sreejato Bhattacharya:
So if 98 is the qth term…
98= 2 + 4(p-1) Or, p= 15
It should have been...
98= 2 + 4(q-1) Or, q= 15
Very sorry for the mistake.
Calvin:
I believe the value should be 25, and not 15?
Sreejato:
Note that the red bead can be labeled bead 0 or bead 100 [I think this does not change the answer].
Now bead 1 is removed first. Then bead 3 is removed. Then bead 5 is removed. It can be concluded that first, all the odd numbered beads are removed. So proceeding this way, bead 99 is removed. Then bead 2 is removed. Then bead 6 is removed. Then bead 10 is removed. So we can conclude that the beads numbered of the form 4k+2 are removed [k being an integer]. Proceeding this way, bead 98 is removed. Then bead 4 is removed. Then bead 8 is removed. So we can conclude that all beads numbered of the form 4k are removed. Proceeding this way, bead 100 is removed.
So before the red bead is removed, all the blue beads numbered odd, of the form 4k, and of the form 4k+2 are removed.
Now, the union of the sets of numbers of the form 4k and 4k+2 is the set of even numbers. So we can also say this that before the red bead is removed, all blue beads numbered odd and all blue beads numbered even are removed.
In other words, all the blue beads are removed before the red bead.
So the answer is 0.
Very sorry for the previous mistake.
Calvin:
I think you have oversimplified the problem, and failed to consider what actually happens. The model of description that you gave works, until it doesn't work.
Sreejato Bhattacharya:
Note that the red bead can be labeled bead 0 or bead 100 [I think this does not change the answer].
Now bead 1 is removed first. Then bead 3 is removed. Then bead 5 is removed. It can be concluded that first, all the odd numbered beads are removed. So proceeding this way, bead 99 is removed. Then bead 2 is removed. Then bead 6 is removed. Then bead 10 is removed. So we can conclude that the beads numbered of the form 4k+2 are removed [k being an integer]. Proceeding this way, bead 98 is removed. Then bead 4 is removed. Then bead 12 is removed. Then bead 20 is removed. So we can conclude that all beads numbered of the form 8k+4 are removed. Proceeding this way, bead 100 is removed.
So before the red bead is removed, all the blue beads numbered odd, of the form 4k+2, and of the form 8k+4 are removed.
No. of odd beads from 1 to 100= 50. No. of beads of the form 4k+2 from 1 to 100= 25 No. of beads of the form 8k+4 from 1 to 100= 12
So, before the red bead is removed, number of blue beads = 100-50-25-12= 13
Sorry for the mistake.
Calvin:
I disagree that there are 13 blue beads on the necklace before the red bead is removed. What you have shown is that, before the red bead is removed, the number of beads on the necklace is 13.
Sreejato Bhattacharya:
General case for N beads.
Label the beads. The first bead is labeled 1. The second bead is labeled 2.
The Nth bead [or the red bead] is labeled N.
Now in the first cycle, we remove all the odd beads. So if N is odd, we will reach the red bead in the first cycle. Before the red bead is removed, (N-1)/2 blue beads will be removed. So, N-(N-1)/2= (N+1)/2 blue beads will be left.
Now assume N is not odd. We now have (N+1)/2 blue beads removed. Then we remove bead 2. Then we remove bead 6. Then we remove bead 10. So all the beads of the form 4k+2 are removed. If N is of the form 4k+2 [or 2(2k+1)], we will remove the red bead in the second cycle. The number of beads removed in the second cycle will be (N-2)/4. So total number of beads removed= N/2 + N-2/4 = 3N-2/4 [note that if N is even, N/2 beads will be removed in the first cycle]. So number of beads removed will be N-(3N-2/4) = N+2/4.
Now assume that N is not of the form 4k+2. Then N must be of the form 4k. Note that if N is of the form 4k, N/2 beads will be removed in the first cycle and N/4 beads will be removed in the second cycle. Now N-2 is clearly of the form 4k+2, so it is removed in the second cycle.
So N-2 have been removed, we have left beads of the form 4k. Now we remove bead 4, then bead 12, then bead 20. We can conclude that all beads of the form 8k+4 are removed. So if N is of the form 8k+4 [or 2^2[2k+1]], we will reach the red bead in the third cycle. The number of steps taken to do this will be (N-4)/8. So, total N/2 + N/4 + (N-4)/8 beads will be removed.
Now some observations have to be made. Note that if N is odd, 0 is the largest power of 2 that divides N, and (N-1)/2 beads will be removed before the red bead is removed. If N is of the form 4k+2, 1 is the largest power of 2 that divides N, and N/2 + (N-2)/4 beads will be removed before the red bead. If N is of the form 8k+4, 2 is the largest power of 2 that divides N, and N/2 + N/4 + (N-4)/8 beads will be removed before the red bead.
We wish to show that this is true for all N[i.e. if x is the largest power of 2 that divides N, we will reach the red bead in the (x+1)th cycle, and N + N/2 + N/4 + ... +N/2^x + (N-2^x)/2^(x+1) beads will be removed before the red bead.
By strong induction [on x] assume that this is true for 1, 2, ..., p-1, p.
Now, since p is the largest power that divides N, we will reach the red bead in the (p+1)th cycle, and N + N/2 + N/4 + ... +N/2^p + (N-2^p)/2^(p+1) beads will be removed before the red bead.
Now p is the largest power of 2 that divides N implies that N is of the form 2^p [2k+1]= 2^(p+1)*k + 2^p.
So we remove the red bead in the (p+1)th cycle if N is of the form 2^(p+1)*k + 2^p. If not, after we remove the (N-2^p)th bead, we start removing all the beads of the form 2^(p+1)[2k+1] (this is because in the previous cycles, all the beads of the form 2^q[2k+1], where q is less than p, have been removed].
So if N is of the form 2^(p+1)[2k+1], we reach the red bead in the (p+2)th cycle. Now since we remove all beads of the form 2^(p+2)*k + 2^(p+1), in the last cycle we will remove {N-2^(p+1)}|/2^(p+2) beads. But in the previous cycles a total of N + N/2 + N/4 + ... +N/2^(p+1) beads were removed. So before we reach the red bead, N/2 + N/4 + ... +N/2^(p+1) + {N-2^(p+1)}|/2^(p+2) blue beads were removed. The rest of this proof follows from strong induction.
So, we can conclude the general case for N this way.
If x is the highest power of 2 that divides N, we reach the red bead in (x+1) cycles, and before the red bead is removed, the number of blue beads left are N-[N + N/2 + N/4 + ... +N/2^x + (N-2^x)/2^(x+1)]
For example, take N=100= 2^2 * 25. Then x= 2. So, we reach the red bead in the 3rd cycle. Number of blue beads left= 100-[100/2 + 100/4 + (100-4)/8]= 100-[50+25+12]= 100- 87= 13
This matches with the answer.
Calvin:
I like that you did induction on $latex x$, the highest power of 2 that divides $latex N$, as opposed to on $latex N$ directly. This makes a lot of sense, when considering how the cycles defined operate. Induction on $latex N$ would be more tricky, as the red bead need not be the first (or last, depending on your view) anymore.
However, you do not need strong induction, the standard induction is sufficient, since your proof only used the p case. Showing the number of beads that is removed also follows from standard induction on x .
Also, your base case (when x = 0 ) has been wrongly calculated. Take for example when N = 1 , x = 0 . There are no blue beads on the necklace, but your conclusion is that 2 N + 1 = 1 blue bead will be left on the necklace. The issue here is similar to my comment on your previous post.
Sreejato Bhattacharya:
Now assume N is not odd. We now have (N+1)/2 blue beads removed.
It should have been...
Now assume N is not odd. We now have N/2 blue beads removed. [because N is even]
let the red bead be the 100th bead then, we remove bead number 1,3,5,7,....99 so 50 beads are removed
Now,50 beads remain.Now the red bead becomes the 50th bead so we remove bead number 1,3,5,7,....,49 so 25 beads were removed
Now,25 beads reamin. Now the red bead becomes the 25th bead so we remove bead numbers 1,3,5,7,....,23 and finally the red bead no.25 so 13 beads were removed
So the total no. of beads removed is 50+25+13=88 so the no. of bloue beads remaining is 12.
Comments and replies:
Calvin:
Can you explain what is exactly happening? Why does bead number 1 get removed 3 times? What do you mean by "let the red bead be the 100th bead" and then "Now the red bead becomes the 50th bead"? Do the bead numbers change? If so, can you explain why / how do they change?
Shourya Pandey:
After t we remove the beads 1,3 ,5,7,....,99 the bead numbers left are 2,4,6,...,100.
We re-number 2 as1,4 as 2,....100 as 50.
So since the red bead was actually the 100th bead, it now becomes the 50th bead.
So,now we remove bead numbers 1,3,5,...,49 according to the newly allotted numbers.
Calvin:
That's clearer now. Remember that when you relabel objects, you have to let your reader know that. Otherwise it will be very confusing to them. This is especially true for algebra questions if you relabel your $latex x$ and $latex y$, you could even end up confusing yourself.
Since initially we have 100 (an even number), on the first cycle we remove 100/2 = 50 blue balls leaving 50 balls with one of them red. The first cycle stopped (the last bead removed in the first cycle) is the blue ball on the left of the red ball. Now the second cycle is like the first only we have now 50 balls and we also begin removing the blue ball right next to the red ball (since we stopped removing the blue ball on the left of the red in the first cycle). Hence we remove 50/2 = 25 blue balls leaving 25 balls with one of them red. Now we have 25 balls and it can be shown that on the third cycle, we finally be able to remove the red bead since we only have an odd number of balls and we also begin removing the bead on the right of red. Hence with the red ball marked as 25 and the ball right next to it as 1, 2,.. ,24, on the third cycle we remove beads 1, 3, 5, ..., 25 or a total of 13 beads leaving as with 25 - 13 = 12 blue beads.