A Necklace with 100 Beads

[msu_math]

Problem:

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. Removing every other bead means that we skip a bead, remove a bead. Skip a bead, remove a bead, etc.


Solution:     

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.

Answer: 12 beads.

[bipasha]

Very interesting problem and intellectual solution

[msu_math]

The aforementioned solution can be generalized in case of a necklace with N beads where 1 of them is red and the rest are blue.

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 r^th 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 The above solution can be generalized in case of a necklace with N beads where N-1 beads are blue and number of red beads is 1.

Answer:  k -1 blue beads where N = (2k-1)*2^q for some integers k>0 and q>=0.

[Masuma Parvin]

Very interesting!!

[shirin.ns]

Interesting!!!

[ummekulsum]

really interesting one