TH-TMO 2013 Problem 11

Let $m, n$ be positive integers. There are $n$ piles of gold coins, so that pile $i$ has $a_i > 0$ coins in it $(i = 1, ..., n)$ . Consider the following game:

Step 1. Nadech picks sets $B_1, B_2, ... , B_n$ , where each $B_i$ is a nonempty subset of $\{1, 2, . . . , m\}$ , and gives them to Yaya.

Step 2. Yaya picks a set $S$ which is also a nonempty subset of $\{1, 2, . . . , m\}$ .

Step 3. For each $i = 1, 2, . . . , n$ , Nadech wins the coins in pile $i$ if $B_i \cap S$ has an even number of elements, and Yaya wins the coins in pile $i$ if $B_i \cap S$ has an odd number of elements.

Show that, no matter how Nadech picks the sets $B_1, B_2, . . . , B_n$ , Yaya can always pick $S$ so that she ends up with more gold coins than Nadech