MathDB

Let

\alpha, \beta

be two rational numbers strictly between 0 and 1. Alice and Bob play a game. At the start of the game, Alice chooses a positive integer

n

. Knowing that, Bob then chooses a positive integer

T

. They then do the following for

T

rounds: at the

i

th round, Bob chooses a set

X_i

n

positive integers that form a complete residue system modulo

n

. Then Alice chooses a subset

Y_i

X_i

such that the sum of elements in

Y_i

is at most

\alpha

times the sum of elements in

X_i

. After the

T

rounds, Alice wins if it is possible to pick an integer

s

between 0 and

n-1

such that there are at least

\beta T

positive integers among the elements in

Y_1, Y_2, . . . , Y_T

(counted with multiplicities) that are equal to

s \pmod n

, and Bob wins otherwise. Find all pairs

(\alpha, \beta)

of rational numbers strictly between 0 and 1 such that Alice has a winning strategy.
Proposed by Hans

Problem Statement