Problem 29 · 2015 Math Kangaroo
Stretch
Logic & Word Problems
work-backwardcareful-counting
The 96 members of a counting club are standing in a circle counting. They start with 1, 2, 3, etc., each person in the circle saying the next number in turn. If a member of the club says an even number, he steps out of the circle. The remaining members continue, starting the second round with 97. They continue in this way until only one member of the club is left. Which number did this person say in round one?
Show answer
Answer: D — 65
Show hints
Hint 1 of 2
Saying an even number = being eliminated, so this is the every-second-person Josephus elimination.
Still stuck? Show hint 2 →
Hint 2 of 2
Use the 2·L+1 rule after writing 96 as a power of two plus a remainder.
Show solution
Approach: Josephus elimination with step 2
- Saying an even number removes that person, so persons are knocked out two-at-a-time in the classic every-second elimination.
- Writing 96 = 64 + 32, the survivor's position is 2·32 + 1 = 65.
- In round one the person in position 65 says the number 65 (D).
Mark:
· log in to save