P32 [Combinatorics] - Turkish NMO 1st Round - 2005
Source:
November 10, 2013
ceiling functionlogarithms
Problem Statement
Ali chooses one of the stones from a group of stones, marks this stone in a way that Betül cannot see the mark, and shuffles the stones. At each move, Betül divides stones into three non-empty groups. Ali removes the group with more stones from the two groups that do not contain the marked stone (if these two groups have equal number of stones, Ali removes one of them). Then Ali shuffles the remaining stones. Then it's again Betül's turn. And the game continues until two stones remain. When two stones remain, Ali confesses the marked stone. At least in how many moves can Betül guarantee to find out the marked stone?