Track / Stage 5 / 396 of 400 #1476 of 2444

Problem 1476

AIME late

Combinatorics Difficulty 6.0 Prove it Mongolian National Mathematical Olympiad · Mongolia

$n$ girls are standing in a circle, each holding exactly 1 card. One girl gives her card to the girl on her left, who in turn gives 2 cards to the girl on her left. The girl who got the cards gives 1 card to the girl on her left. The girl who got the card gives 2 cards to the girl on her left. Continuing this way, each girl gives alternating 1 or 2 cards to the girl on her left. Anyone who has no card leaves the game immediately. Find all values of $n$ such that all cards are collected by one girl.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Answer: $n = 2$ , $n = 2^k + 1$ , $n = 2^k + 2$ , $k \ge 1$ .
Solution omitted.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.