Sum Game#13008

Sum Game (Editorial)

Author:

Adrian Miclaus

Solved by:

First to solve:

pretests passed (4)

For any subset S\subseteq\{1,\dots,N\} define its (unsigned) subset sum modulo : f(S)=\sum_{i\in S} a_i \pmod M. If there exist two distinct subsets S\neq T with f(S)=f(T), then \sum_{i\in S\setminus T} a_i - \sum_{i\in T\setminus S} a_i \equiv f(S)-f(T)\equiv 0 \pmod M. Ana chooses “” on S\setminus T, “” on T\setminus S, and erases the rest. Since S\neq T, the remaining set is non-empty. Thus, Ana can win iff there are two distinct subsets with equal subset-sum modulo . There are 2^N subsets, but only possible residues modulo . If 2^N > M, then by the pigeonhole principle two distinct subsets collide, so Ana can always form a signed sum divisible by . If 2^N \le M, Bob chooses a_i = 2^{i-1}, 1\le i\le N. Then every subset sum as an integer lies in [0,2^N-1] and is unique, hence also unique modulo because 2^N-1 < M. So, no two distinct subsets have the same residue, and in particular no nonempty subset sums to modulo . In this case, Ana cannot win.