N sheets of card in which 1, 2, 3, ...., N is written each are clockwise arranged in the small order of the number circularly.
When removing one card at a time in accordance with the following rule, it is considered which card remains at the end.
<Rule 1>
The card in which 1 is written is removed first.
<Rule 2>
When a certain card is removed, the 2nd card from the card counted clockwise and will be removed.
This operation is repeated until only one card remains.
For example, in case of N = 13, cards are removed as shown in Fig. 1, and #10 card finally remains.
(× mark expresses the removed card.)
Answer the following questions.
(1) Answer the number written to the card which remains at the end in case of N = 8.
(2) When cards are removed at the 1st round in case of N = 16, as shown in Fig. 2, eight cards remain.
The card in which 2 was written is removed next.
Answer the number written to the card which remains at the end in case of N = 16.
Moreover, answer the number written to the card which remains at the end, respectively in case of N = 32 and N = 64.
(3) When the cards in which 1, 3, and 5 are written at the 1st round are removed in case of N = 35, 32 cards remain.
The card in which 7 was written is removed next.
Answer the number written to the card which remains at the end in case of N = 35.
(4) When 36 cards are removed to the 1st round in case of N = 100, 64 cards remain.
Answer the number written to the card which remains at the end in case of N = 100.
(5) Answer the number written to the card which remains at the end in case of N = 2009.
Answer
(1) 8
(2) 16, 32, 64
(3) 6
(4) 72
(5) 1970
Solution
(1) Arrange cards from 1 to 8 and remove.
Cards being removed at the 1st round is 1, 3, 5, 7.
At the 2nd round is 2, 6.
At the 3rd week is 4.
Therefore, the remaining card is 8.
(2) Remove cards using Fig. 2.
Cards being removed at the 1st round is 1, 3, 5, 7, 9, 11, 13, 15.
At the 2nd round is 2, 6, 10, 14.
At the 3rd round is 4, 12.
At the 4th round is 8.
Therefore, the remaining card is 16.
As for the case of n= 32, odd number is removed at the 1st round.
Since it begins from 2 and card is removed every four at the 2nd round, cards removed is 2, 6, 10, 14, 18, 22, 26, 30.
Since it begins from 4 and card is removed every eight at the 3rd week, cards removed is 4, 12, 20, 28.
Since it begins from 8 and card is removed every 16 at the 4th week, cards removed is 8, 24.
At the 5th round is 16.
Therefore, the remaining card is 32.
This operation shows that in the case of n = 2 × 2 × 2 = 8, n = 2 × 2 × 2 × 2 = 16, and n = 2 × 2 × 2 × 2 × 2 = 32, 8, 16, and 32 remain.
The card in which it remains in the case of 64= 2 × 2 × 2 × 2 × 2 × 2 is 64.
(3) In case of n = 35, when three cards, 1, 3, and 5, are removed, it can be considered as n= 32.
And in the case of n= 32, it began to take from 1, but in this case, it can be considered that it begins to take from 7 which is next to 5.
In the case of n= 32, it began to take from 1 and the remaining number is 32 which is just before 1 in the arrangement of numbers.
When it thinks the same way also in this case, the number to be remained is 6 which is just before 7 which is the number to be removed first.
(4) Consider as the same way as (3).
Since the 37th card removed is the 37th odd number counted from 1, it becomes 1, 3, 5, 7, 9 -------, 1 + 2 × (37 - 1) = 73.
Therefore, the card which remains in this case is 72 which is just before 73 which is considered as the first card removed.
(5) 64 × 2 = 128, 128 × 2 = 256, 256 × 2 = 512, 512 × 2 = 1024, 1024 × 2 = 2048.
Among these numbers, the number which is less than 2009 and is nearest to 2009 is 1024.
According to the calculation of 2009 - 1024 = 985, when 985 pieces are removed, it can be considered as the case of 1024.
The 985th odd number is 1 + 2 × (985 - 1) = 1969.
1024 pieces of cards remain when 1969 is removed.
Therefore, since the first card to be removed is 1971, the card to remain is 1970 which is just before 1971.
