MathDB
A Game About Breaking The Most Cups

Source: Turkey Olympic Revenge 2023 P5

March 7, 2023
combinatoricsGame Theorycombinatorial game theoryolympic revenge

Problem Statement

There are 1010 cups, each having 1010 pebbles in them. Two players AA and BB play a game, repeating the following in order each move:
\bullet BB takes one pebble from each cup and redistributes them as AA wishes.
\bullet After BB distributes the pebbles, he tells how many pebbles are in each cup to AA. Then BB destroys all the cups having no pebbles.
\bullet BB switches the places of two cups without telling AA.
After finitely many moves, AA can guarantee that nn cups are destroyed. Find the maximum possible value of nn. (Note that AA doesn't see the cups while playing.)
Proposed by Emre Osman