Partition Game

Alice and Bob are playing a game as follows. Originally there are $n > 1$ piles containing $s$ stones each. Alice starts by taking the first turn and at each step, the player chooses one pile and discards the other piles. Then that player divides the stones from that one pile into $n$ piles, such that each pile still contains at least 1 stone. The player that cannot move loses.

Determine all $s$ such that Alice has a winning strategy

Solution

We classify every natural numbers into winning numbers or losing numbers with the following recursion: The numbers $1, \dots, n-1$ are losing numbers. If a number can be partitioned into losing numbers, then it's a winning number. Otherwise it's a losing number. In other words, any given partition of a losing number must contain a winning number.

Now the game is a standard Sprague-Grundy game. If a player receives a state where one pile contains a winning number, then that state is a winning state. For example, $n$ is a winning number because the player can split it into ones, regardless of what the other numbers in the pile are. If a player receives a state where all piles are losing numbers, then it's a losing state.

Let $m=n-1$. Now we establish the base cases. $1, \dots, m$ are losing numbers. Then $n$ can be partitioned into all ones, and $mn$ can be partitioned into all $m$'s. It's easy to show that all the numbers in between can also be partitioned into summands between $1$ and $m$ inclusive, so $n,\dots,mn$ are winning numbers.

Now we claim: Let $x \equiv p \mod mn$ then $x$ is a winning number if and only if $p = 0$ or $p \geq n$, and it is a losing number if and only if $p \in [1,m]$. We prove it by induction on $k = \lceil x / mn \rceil$. The case of $k = 1$ is proven by the base case above.

Now suppose we have a number $x$ with residue in $[1,m] \mod mn$ and there is a way to partition this number into $n$ summands, all while staying within $[1,m] \mod mn$. The smallest sum (in the residue space) that can be attained is $n$, and the largest sum is $mn$, and they are all outside of $[1,m]$, a contradiction. So some of the summands must have residue $0$ or $\geq n \mod mn$. Let $y$ be this summand. Note that $ \lceil y / mn \rceil < \lceil x / mn \rceil$ in each of these cases. So $x$ is a losing number by induction hypothesis.

Now suppose we have a number $y$ divisible by $mn$, then we can partition it into $n$ numbers all having residue $m$. The easiest is of course to have the first $m$ terms $m$ and have the last term $y - m^2 = kmn - m^2 = (k-1)mn + m$. Each of these numbers are losing numbers with less quotient than $y$, so $y$ is a winning number.

Next, suppose we have $y$ with residue $[n, mn-1]$. Using the same argument as above, we can see that it can always be decomposed into the sum of $n$ numbers with residue $[1,m]$. However, the quotient of the summands are not necessarily less than $y$, but we have proved that the set in $[1,m]$ with quotient $k$ are losing numbers as well.

Toggling lights 3 at a time

Alice and Bob are playing a game. $n$ lights are put on a line with individual switches, initially all off. Then the two phases happen as follow:

1. Alice turns on some of these lights

2. Bob may do these actions: choose a contiguous block of 3 lights and toggle these 3 lights. He may repeat these actions as many times as he wants for different blocks.

And the scoring of the game is as follows:

In phase 1, Alice gets a -1 point for each light that she turns on. In phase 2, Alice gets a +1 point every time Bob performs an operation. Then at the end of the game, Alice gets $i$ points if light $i$ is on. Obviously Alice wants her score to be as high as possible, and Bob wants her score to be as low as possible. Determine the maximum points that Alice can get if both players are playing optimally.

Solution

Let $T_k$ denote the action by Bob of toggling a contiguous block of $k, k+1, k+2$, where $k \in [1, 98]$. If light $k+3$ is on and light $k$ is off, by performing $T_k + T_{k+1}$ he can turn off $k+3$ and turn on $k$. The net effect to the score is -1 so this move is beneficial to Bob. Therefore, he would keep doing it as long as there are lights on at $k > 3$. Furthermore, if there are 2 lights on $k > l$ such that $k \equiv l \mod 3$ then by repeating the operation above Bob can turn off both lights. The net effect to the score is $-k-l+2\frac{k-l}{3} < 0$. This means that it is not optimal for Alice to turn on two lights that have the same residue mod 3. So at most Alice should turn on 3 lights. But even then, if we ever arrive at the condition where lights $(1,2,3)$ are on, then Bob can perform $T_1$ to turn off all the lights. So Alice should turn on at most 2 lights.

The final condition that is most beneficial to Alice is either $(3)$ or $(1,2)$, both having the same value, and both are accessible from each other in phase 2. But obviously it's more beneficial for Alice to turn on only 1 light, and it should be the largest light divisible by 3, so that Bob has to spend a lot of moves moving it to the smaller number. So Alice should turn on $3\lfloor n/3 \rfloor$, and Bob will have to move it all the way to 3.

The total score is then $-1 + 2\lfloor n/3 \rfloor + 3 = 2\lfloor n/3 \rfloor +1$

Note: the number 3 can be replaced by a larger number $p$ but the principle is the same. Any light on above $p$ can be shifted down for a net gain for Bob. However, the final condition is tricky. Take $p=5$ for example. We don't want $(1,2,3,4,5)$ because then Bob can simply turn them all off in one fell swoop. We also don't want $(3,4,5)$ because Bob can still replace it by $(1,2)$ for a net gain. In fact, the optimal condition for Alice is $(3,5)$ because while Bob can replace it by $(1,2,4)$, it costs him 1 point to do so, so it's not a beneficial move for Bob. Likewise, for $p=6$, the best condition for Alice is $(5,6)$ because it's "just under" $(1+2+3+4+5+6)/2$. The number of lights that would be left on so that the sum is just under $n(n+1)/2$ is $\lfloor (n-1)/2 \rfloor$ which can be proved by induction. However, the exact configuration is harder to determine in closed form expression. This matters because in the course of shifting the lights down during phase 2, Bob may inadvertently have to perform the same $T_k$ twice in which case he would just not perform that action, so the calculation of final point count becomes more complicated.

Hyper-triangular numbers

Triangular number $T_n$ is defined as $T_n = 1 + 2 + \dots + n$.

Tetrahedral number $R_n$ is defined as $R_n = T_1 + T_2 + \dots + T_n$.

Let $T^k_n$ denote the $k$-th dimensional triangular numbers, with $T^1_n = 1+1+\dots+1 = n$, $T^2_n = T_n$, and $T^3_n = R_n$. Specifically, the higher dimensional triangular numbers are defined as: $$ T^{k+1}_n = T^k_1 + T^k_2 + \dots + T^k_n$$ Prove that: $$T^k_n.T^m_1 + T^k_{n-1}.T^m_2 + \dots + T^k_1.T^m_n = T^{k+m+1}_{n+1}$$

Number of contiguous blocks containing black balls over all permutations

$k$ black balls and $n-k$ white balls are arranged on a straight line, where $n \geq 1$, $0 \leq k \leq n$. The score of the said arrangement is the number of contiguous subsequences that contain at least one black ball. For example, the arrangement $W W B W B$ has two subsequences of length 1, and three subsequences of length 2 that contain at least one black ball. Of course there are subsequences of length 3 or higher as well, so the total score for this arrangement is 11.

What is the sum of the score of all $\binom{n}{k}$ arrangements? You may express this quantity in a recursive formula computable in $O(n^2)$ time, $O(n \log n)$ time, or $O(n)$ time.

Solution 1

We give a recursion formula computable in $O(n^2)$ time with DP.

More to come...

Solution 2A

We prove that the number is $\binom{n+2}{k+2} . \binom{k+1}{2}$ which is computable in $O(n)$ time simply by calculating the factorial table

First let $T_n$ be the $n$-th triangular number, $T_n = n(n+1)/2 = \binom{n+1}{2}$. And we also will use the following well-known identity a lot: $$\sum_{i=1}^{n} \binom{i+p-1}{p} = \binom{n+p}{p+1}, p \geq 0$$ It can be proven many ways, either with induction on $n$ keeping $p$ fixed, induction on $p$ keeping $n$ fixed, or telescoping sum, or using combinatorial arguments (choosing $p+1$ items, and condition on the first item chosen). For $p = 0$ it is a trivial sum, and for $p = 1$ it is the definition of triangular numbers.

Note that if all balls were black, then every single contiguous blocks would contribute to the score. There are $1 + 2 + \dots + n = T_n$ such blocks and that is the score. But if there are white balls, then we want to calculate how many scores are lost due to these pockets of white balls, over the course of all different arrangements.

Now given a particular arrangement of $k$ black balls and $n-k$ white balls, we come with an associated sequence of $k+1$ integers denoting the number of white balls in between black balls, including before the first black ball and after the last black ball. For example, the sequence WWBWWWBBBW corresponds to the sequence $(2, 3, 0, 0, 1)$. Each element in this sequence must be non-negative and they must add up to $n-k$, and there must be exactly $k+1$ integers.

Lemma

Suppose $A$ is the set of all sequences of non-negative integers with length $m \geq 2$ that sum up to $M$, that is $$ A = \{ (a_1, \dots, a_m) | a_i \geq 0, a_1 + \dots + a_m = M \}$$ then:

1. There are $|A| = \binom{M+m-1}{m-1}$ possible sequences.

2. If $m \geq 2$, the number $t \in [0,M]$ occurs $m \binom{M-t+m-2}{m-2}$ times in $A$, in any position.

We prove by induction. For $m=2$, the possible sequences are $A = \{(M,0), (M-1,1,), \dots, (0,M)\}$ so $|A| = M+1$ and there are two occurrences of each number.

Now suppose it holds for $m$, now for $m+1$, consider the first element $a_1 \in [0,M]$. Once its value is chosen, then we have $m-1$ numbers that need to sum up to $M - a_1$. So there are $\binom{M-a_1+m-2}{m-2}$ ways to do this, by induction hypothesis. The total number of ways is the sum of that expression when $a_1$ ranges from $0$ to $M$. $$\sum_{a_1 = 0}^M \binom{M-a_1+m-2}{m-2} = \sum_{i=m-2}^{M+m-2} \binom{i}{m-2} = \sum_{j=1}^{M+1} \binom{j+(m-2)-1}{m-2} = \binom{M+m-1}{m-1}$$ The first two equalities are change of variables, but the last one utilizes the identity above. We have proved the first assertion. For the second assertion, consider the case where the first element $a_1 = t$. The rest of the $m-1$ elements must sum up to $M-t$, so there are $\binom{M-t+m-2}{m-2}$ ways to complete the sequence. However, the number $t$ may appear in any of the other positions as well, so in total there are $m$ times that amount.

One might ask that sometimes the number $t$ itself my appear as a duplicate in multiple elements. For example for $m=4$ and $M=11$, we have have a sequence $(2,2,5,2)$ which should only be counted once. Indeed, when we consider $a_1=1$, we contributed one count towards the total number of "2" appearing. Likewise, when we consider $a_2=2,a_4=2$ we also added one count each time, but the sequence itself contributes three counts towards the appearance of "2." So the total amount is exact and correct, and there is no need to compensate for double counting. Thus the lemma is proven

Alternatively, one could also prove the first assertion by using a combinatorial argument. Consider $M+m-1$ spaces and we are to choose $m-1$ spaces to serve as separators. The spaces between the separators will be the numbers in the sequence.

Now observe that each arrangement corresponds one-to-one with a sequence like we described above. The process to convert from an arrangement to a sequence is invertible. Therefore, the total number of contiguous blocks in all arrangements is $$ T_n \binom{(n-k)+(k+1)-1}{(k+1)-1} = T_n \binom{n}{k} $$ But a lot of these blocks would contribute zero towards the total score. That is, for each sequence $(a_1, \dots, a_{k+1})$, the total loss of scores is the number of contiguous blocks that are contained fully within those pockets of white balls, that is: $$T_{a_1} + \dots + T_{a_{k+1}}$$ So we have to add these over all the possible sequences whose sum is $n-k$. This is where we utilize the lemma. Each time the number $t$ appears, it contributes $T_t$ towards the total loss of score. But thanks to the lemma, we know that the number $t$ appears exactly $$(k+1) \binom{(n-k)-t+k-1}{k-1} = (k+1) \binom{n-t-1}{k-1}$$ times. So the total loss of scores is the sum of this quantity as $t$ ranges from one to $n-k$. (Technically $t=0$ is a valid scenario but it incurs no loss of score because $T_0 = 0$ so we ignore it). $$\sum_{t=1}^{n-k} (k+1) \binom{n-t-1}{k-1} T_t $$ At this point, this sum can be computed in $O(n \log n)$ times using FFT technique, as it's a sum of terms expressed in $t$ and $n-t$, but we can simply the terms further to arrive at a closed form solution, by repeated use of the identity above. Let $B_i = \binom{i+k-2}{k-1}$ (where $k > 0$ is fixed), and for any $m > 0$: $$ B_1 + \dots + B_m = \sum_{i=1}^{m} \binom{i+k-2}{k-1} = \binom{m+k-1}{k}$$ by direct application. Then: $$ \sum_{i=1}^{m} (m+1-i). \binom{i+k-2}{k-1} = m.B_1 + (m-1).B_2 + \dots + 1.B_{m} = B_1 + (B_1+B_2) + \dots + (B_1 + \dots + B_m) = \sum_{i=1}^{m} \binom{i+k-1}{k} = \binom{m+k}{k+1}$$ One more time: $$ \sum_{i=1}^{m} T_{m+1-i}. \binom{i+k-2}{k-1} = T_m.B_1 + T_{m-1}.B_2 + \dots + 3.B_{m-1} + 1.B_{m} $$ $$ = [1+2+ \dots + m]B_1 + [1+2+ \dots + (m-1)]B_2 + \dots + [1+2]B_{m-1} + 1.B_m$$ $$ = 1.B_1 + (2.B_1 + 1.B_2) + (3B_1 + 2B_2 + B_3) + \dots + (m.B_1 + \dots + 1.B_m)$$ $$ =\sum_{i=1}^m \binom{i+k}{k+1} = \binom{m+k+1}{k+2}$$ Now, the total loss of scores becomes: $$ \sum_{t=1}^{n-k} (k+1) \binom{n-t-1}{k-1} T_t = (k+1) \sum_{i=1}^{n-k} T_{n-k+1-i} \binom{i+k-2}{k-1}$$ due to change of variable. Now we apply the latest identity above, with $m=n-k$: $$ = (k+1) \sum_{i=1}^{n-k} T_{n-k+1-i} B_i = (k+1) \binom{n+1}{k+2}$$

So the total score is then: $$ T_n \binom{n}{k} - (k+1) \binom{n+1}{k+2} = \frac{n(n+1) n!}{2. k!(n-k)!} - \frac{(k+1)(n+1)!}{(k+2)!(n-k-1)!} = \frac{(n+1)!}{k!(n-k-1)!} \left(\frac{n}{2(n-k)} - \frac{(k+1)}{(k+2)(k+1)} \frac{n-k}{n-k} \right)$$ $$ \frac{(n+1)!}{k!(n-k)!} \left(\frac{n}{2} - \frac{n-k}{k+2} \right) = \frac{(n+1)!}{k!(n-k)!} \frac{kn+2n-2n+2k}{2(k+2)} = \frac{(n+1)!}{k!(n-k)!} \frac{k(n+2)}{2(k+2)}.\frac{k+1}{k+1} = \frac{(n+2)!}{(k+2)!(n-k)!} \frac{k(k+1)}{2} = \binom{n+2}{k+2} . \binom{k+1}{2}$$

Solution 2B

We also prove that the number is $\binom{n+2}{k+2} . \binom{k+1}{2}$ but using a different (simpler) combinatorial argument.

Given $n+2$ tokens in row, mark $k+2$ of these as blue and $n-k$ as red. There are $\binom{n+2}{k+2}$ ways to choose. And now, among the blue tokens, further mark 2 tokens as "start" and "end", with the condition that "start" must come before "end", and there must be at least one blue token between them. There are $\binom{k+2}{2} - (k+1) = \binom{k+1}{2}$ ways to choose. So the end result is an arrangement of red and blue tokens, and two tokens marked start and end containing at least a blue token in between. We will show that this arrangement corresponds to exactly one score-producing contiguous block in a particular arrangement of black and white balls, and that the mapping is invertible and thus we obtain a bijection.

Arrange the balls according to the $n$ unmarked tokens, where all $n-k$ red tokens correspond to white balls, and $k$ unmarked blue tokens correspond to black balls. The contiguous block is represented by the tokens between start and end, including all red and blue tokens. Because the start and end must flank at least one blue token, then this contiguous block contributes one point towards the score.

On the reverse, given an arrangement of balls, create the corresponding arrangement of red and blue tokens. And then insert the start token to the space right before the first ball in the contiguous block, and the end token to the space right after the last ball. Thus we have a bijection, and the number of total score is $\binom{n+2}{k+2} . \binom{k+1}{2}$.

Solution 3

We present a different combinatorial argument, this time in the permutation space, not a combination space.

First we label all the balls from $1,\dots,n$ such that all the black balls are labeled $1,\dots,k$ and the white balls are labeled $k+1, \dots, n$. Consider any given permutation of the balls, and define the score of this permutation the same way as the problem statement: the number of contiguous blocks that contain at least one black balls. Then we also consider the total number of scores of all $n!$ permutations.

Note that each arrangement of unlabeled balls corresponds to $k! (n-k)!$ permutations of labeled balls, all having the same score. So the total number of scores of all $n!$ permutations is $k! (n-k)!$ times the total score of all arrangements. We will show that the total number of scores of all permutations is $\frac{(n+2)!}{2} \frac{k}{k+2}$.

First we arrange the items $1,\dots,n, X, Y$ in a row, with the condition that $X$ happens before $Y$. There are $\frac{(n+2)!}{2}$ ways to do so. This permutation corresponds to permutation of balls, and the contiguous block is represented by the items between $X$ and $Y$. There may be some permutations where $X$ and $Y$ are next to each other, which means the contiguous block is empty, but that's okay for now. Because we have conditioned that $X$ happens before $Y$, the mapping is injective, meaning no two item permutation map to the same (ball permutation, contiguous block) tuple.

However, not all of those permutations will produce a score. In order for it to produce a score, there must be at least one of $1,\dots,k$ between $X$ and $Y$. So now we consider the permutations of these $k+2$ items. Each of the $n+2$-item permutations has a unique corresponding $k+2$-item permutation, but every $(n-k)!$ of the large permutations produces the same smaller permutation.

There are $\frac{(k+2)!}{2}$ smaller permutations because they still all have $X$ before $Y$. We want to exclude the ones where $X$ and $Y$ are together in this permutation (even if in the original permutations there may be numbers larger than $k$ between them). There are $(k+1)!$ such permutations. So the remaining permutations are: $$\frac{(k+2)!}{2} - (k+1)! = \frac{(k+2 - 2}{2} (k+1)! = \frac{k}{2} (k+1)! = \frac{k}{k+2} \frac{(k+2)!}{2} $$ In other words, the good permutations are only $k/(k+2)$ of the total number of permutations, when we consider all small permutations. But since all large permutations map to the small permutations evenly ($(n-k)!$ to one), then the number of good large permutations is $\frac{(n+2)!}{2} \frac{k}{k+2}$. Then, we map it back to the space of ball arrangement, where each permutation corresponds to $k!(n-k)$ arrangements, so the total number of score of arrangements is: $$\frac{(n+2)!}{2} \frac{k}{k+2} . \frac{1}{k!(n-k)!} .\frac{k+1}{k+1} = \frac{(n+2)!}{(n-k)!(k+2)!} \frac{(k+1)k}{2} = \binom{n+2}{k+2} \binom{k+1}{2}$$

Expected number of throws

$n$ fair coins are thrown all at once. Those that show Head are removed from the game, and the rest are thrown again. This process is repeated until there are no more coins left. What is the expected number of throws? Find a closed form formula, meaning that it may still be expressed as a sum but may not be expressed as a recurrence relation.

Solution Let $f(n)$ be the desired result. There is a $\binom{n}{k} / 2^n$ chance that $k$ of them will show heads, and the process is repeated with $n-k$ coins now. The rest of the game is expected to take $f(n-k)$ throws. If $k=0$ then we still have the same situation as before. If $k=n$, we have 0 throws left. In all of these situations, we do have to spend 1 turn doing the throw. So the recurrence relation is:

$$f(n) = 1 + \sum_{k=1}^{n-1} \frac{\binom{n}{k}}{2^n} f(k) + \frac{1}{2^n}f(n)$$ $$f(n) = \frac{2^n + \sum_{k=1}^{n-1} \binom{n}{k} f(k)}{2^n-1} $$

Given a large $n$, computing this would take $O(n^2)$ time as we have to calculate and store the previous $f(k)$ values, and each take $O(k)$ time. We can manipulate this expression further to come with a summation formula for $f(n)$ that would allow it to be computed in linear time.

First we claim and prove the following lemma. For $1 \leq m < n$

$$ \sum_{k=m}^{n} \binom{n}{k}\binom{k}{m} = \binom{n}{m}2^{n-m}$$

Proof: given $n$ white balls, we wish to pick $m$ of them and paint them black, and the rest may stay white or be painted gray. The RHS side is obvious, there are $\binom{n}{m}$ ways to choose black balls, and the rest may be painted white or gray.

To show the LHS, first we pick a number $k \in [m,n]$. We choose $k$ balls and paint them gray. Out of these $k$, we further choose $m$ to be painted black.

Alternatively we can prove the lemma by dividing both sides by $\binom{n}{m}$: $$ \sum_{k=m}^{n} \frac{n!}{k!(n-k)!} \frac{k!}{m!(k-m)!} \frac{m!(n-m)!}{n!} = 2^{n-m}$$ $$ \sum_{k=m}^{n} \frac{(n-m)!}{(n-k)!(k-m)!} = 2^{n-m}$$ $$ \sum_{i=0}^{n-m} \frac{(n-m)!}{(n-m-i)!i!} = 2^{n-m}$$

which is a well-known identity

Given the lemma, now we claim the following statement: let $a_n = \frac{2^n}{2^n-1}$ then: $$f(n) = \binom{n}{1}a_1 - \binom{n}{2}a_2 + \binom{n}{3}a_3 + \dots + (-1)^{n+1} \binom{n}{n}a_n$$ We will show that this formula matches our recurrence relation above by strong induction. Suppose they hold for $1,2,\dots,n-1$, then we first evaluate the following expression: $$\sum_{k=1}^{n-1} \binom{n}{k}f(k) = \binom{n}{1}f(1) + \binom{n}{2}f(2) + \dots + \binom{n}{n-1}f(n) $$ $$= \sum_{k=1}^{n-1} \binom{n}{k} \sum_{m=1}^{k} (-1)^{m+1} \binom{k}{m}a_m $$ we rearrange and collect each $a_m$ terms: $$= \sum_{m=1}^{n-1} (-1)^{m+1}a_m \sum_{k=m}^{n-1} \binom{n}{k} \binom{k}{m} $$ Apply the lemma: $$= \sum_{m=1}^{n-1} (-1)^{m+1}a_m \left(\binom{n}{m}2^{n-m} - \binom{n}{m} \right) = \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m} a_m \left(2^{n-m} - 1 \right) $$ We can plug this expression to our recurrence formula and compare against our claim (induction hypothesis). After multiplying both sides by $2^n-1$, we are left to show that: $$(2^n-1) a_n + \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m} a_m \left(2^{n-m} - 1 \right) = (2^n-1) \left( \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m}a_m + (-1)^{n+1}a_n \right)$$ Collect $a_n$ terms to the LHS, and the rest of the terms to RHS: $$(2^n-1)(1 + (-1)^n)a_n = \sum_{m=1}^{n-1}a_m(-1)^{m+1} c_m $$ where $$c_m = (2^n-1)\binom{n}{m} - \binom{n}{m}(2^{n-m}-1) = \binom{n}{m}(2^n - 2^{n-m}) = \binom{n}{m}2^{n-m}(2^m-1) = \binom{n}{m}2^{n-m} \frac{2^m}{a_m}$$ so what we need to show becomes: $$(2^n-1)(1 + (-1)^n)a_n = \sum_{m=1}^{n-1}a_m(-1)^{m+1} \binom{n}{m}2^{n-m} \frac{2^m}{a_m} $$ $$2^n(1 + (-1)^n) = \sum_{m=1}^{n-1}(-1)^{m+1} \binom{n}{m}2^{n} $$ $$1 + (-1)^n = \sum_{m=1}^{n-1}(-1)^{m+1} \binom{n}{m} $$ $$1 + \sum_{m=1}^{n-1}(-1)^{m} \binom{n}{m} + (-1)^n = 0$$ $$(1 -1)^n = 0$$

Positive-definite Polynomial Game

Given $n$ a positive even number. Alice and Bob are playing a game as follows. On the board initially there are $n+1$ unassigned numbers: $a_0, a_1, \dots, a_n$.

With Alice going first, each player alternatingly chooses an unassigned number and assigns a positive real value to it. Once all numbers have been assigned values, polynomial $P(x)$ is defined as:

$$P(x) = a_nx^n + \dots + a_1x +a_0$$

If $P(x) > 0$ for all $x \in R$ then Alice wins, otherwise Bob wins. Determine who has a winning strategy.

Variant 1: if the number $a_0$ is already fixed to 1, so there are only $n$ numbers on the board, who has a winning strategy?

Variant 2: if the winning condition is flipped: Alice wins if there exists an $x$ such that $P(x) < 0$.

Solution

The player who moves last has a winning strategy, regardless of winning condition. Variant 1 merely flips who moves last. If Variant 1 is in play and Alice moves first, then Bob moves last and Bob has a winning strategy. Note that $P(x)$ is positive definite iff $tP(x)$ for all $t$ positive numbers, so the magnitude of each number doesn't matter, only the relative magnitude of all coefficients. Therefore, the number "1" set by variant 1 is arbitrary and the variant merely ensures Bob's ability to win. For the rest of this solution, we assume that variant 1 is not in play and Alice goes first, and she should assign $a_0 = 1$. The rest of the proof can then be extensible to variant 1 while flipping the name Alice and Bob.

Lemma: polynomial $P(x)$ with positive coefficients are positive definite if and only if $P(1/x) > 0$ for all $x \neq 0$. This lemma is easy to see because $P(0) > 0$ anyways.

Part 1: proving that Alice can ensure positive definiteness.

Assume that $a_0 = 1$ has already been assigned. Now divide the remaining coefficients into pairs: $(a_1,a_2), (a_3,a_4), \dots, (a_{n-1},a_n)$. Whenever Bob makes a move and assigns a value to a coefficient, Alice assigns a value to its pair accordingly. We claim that Alice will be able to choose her value such that the resulting polynomial $Q_k(x) = a_{2k}.x^{2k} + a_{2k-1}.x^{2k-1} + 2/n$ is positive definite.

Proof: From the lemma, $Q_k$ is positive definite iff $R_k(x) = \frac{2}{n}x^{2k} + a_{2k-1}x + a_{2k}$ is positive definite.

If Bob chooses $a_{2k-1}$ then Alice can choose $a_{2k}$ large enough to make $R_k(x)$ positive definite. Whichever local minimum may exist due to Bob's choice, Alice can compensate it enough by adding a positive constant term to the whole polynomial.

If Bob chooses $a_{2k}$ then there exists an $a_{2k-1}$ small enough to make $R_k(x)$ positive definite. If $x \geq 0$ positive then $R_k(x) > 0$ because all coefficients are positive. But if $x < 0$ then by AM-GM:

$$ \frac{2}{n}x^{2k} + a_{2k} = \frac{2}{n}x^{2k} + \frac{a_{2k}}{2k-1} + \dots + \frac{a_{2k}}{2k-1} \geq 2k \sqrt[2k]{\frac{2}{n}.\left(\frac{a_{2k}}{2k-1}\right)^{2k-1}}.(-x) > -a_{2k-1}x$$

for small enough positive value of $a_{2k-1}$.

The final polynomial can be expressed as the sum:$P = Q_1 + \dots + Q_{n/2}$, and because at each step Alice can always ensure that the resulting $Q_k(x)$ is positive definite no matter what Bob chooses, then the final polynomial is also guaranteed to be positive definite.

Part 2: proving that Alice can ensure non-positive definiteness.

If $n=2$ then Alice can always ensure that the discriminant of the quadratic polynomial is positive, therefore the polynomial has two real roots. For $n > 2$, the general strategy is as follows: divide the coefficients into pairs as above, and Alice's assignment is always the pair of Bob's assignment as well. But this time the difference is that, after each of her move, Alice ensures that the TOTAL polynomial $P(x)$ is negative for some values of $x$ and maintains this invariant throughout the game.

First note that if Bob ever chooses an even coefficient $a_2,a_4,\dots$ then Alice's job is really easy. Take the current value of $P(-1)$ (after including Bob's addition), and by choosing her corresponding odd coefficient large enough, she can make $P(-1)$ negative because she's adding a multiple of $x^{2k-1}$ which is negative at $x=-1$.

Consider the first round. If Bob chooses $a_{2k}$ then Alice chooses large enough $a_{2k-1}$ as described above. But if Bob chooses $a_{2k-1}$, Alice can choose small enough $a_{2k}$ to ensure non-positive definiteness. The current resulting polynomial is $a_{2k-1}x^{2k-1}+1 < 0$ as $x \to -\infty$, so pick any $y$ such that $a_{2k-1}y^{2k-1}+1 < 0$. Then Alice chooses $a_{2k}$ small enough such that $0 < a_{2k} < \frac{-a_{2k-1}y^{2k-1}-1}{y^{2k}}$ so that $a_{2k}y^{2k}+a_{2k-1}y^{2k-1}+1 < 0$

So once the invariant is established after the first round, then Bob has no choice but to keep choosing even coefficients. If Bob chooses an odd coefficient, then whichever value of $x$ caused $P(x)$ to be negative at the end of last round will continue to be (even more) negative, so Alice simply chooses a very small value of the corresponding even coefficient as described above. But even if Bob chooses an even coefficient, Alice can counter by choosing a large enough odd coefficient. Therefore she maintains the invariant of $P$ being non-positive definite until the end of the game.

Questions in an exam

A test is taken by 2019 students. The test consists of $n$ questions (where $n > 0$ is even), where each question is a true/false problem worth 1 point. It is known that:

1. Each student answered exactly half of the questions correctly.

2. Given two students, their answers agreed on exactly half of the questions.

Find the smallest $n$ such that this situation is possible.

Solution

If $n = 2^k m$ where $m$ is odd, then there are at most $2^k - 1$ students. Therefore, with 2019 students, we need $2048$ questions for this situation to be possible. Proof:

Suppose $m=1$, we will give a configuration of $2^k-1$ students that satisfy both conditions. First of all, given a number $b$, let $f(b)$ denote the number of 1s in its binary representation, modulo 2. That is $f(b)=0$ if $b$ contains an even number of 1s in its binary representation, and $f(b) = 1$ otherwise.

Label the students $1$ to $2^k-1$ and consider their binary representation (from $0...01$ to $1...1$, all having exactly $k$ digits). Also label the problems $0$ to $2^k-1$ and consider their binary representation (from $0...0$ to $1...1$, all having exactly $k$ digits). We set student $s$ answered problem $p$ correctly if $f(p \wedge s) = f(s)$, where $\wedge$ denotes bitwise AND operation between $p$'s binary representation and $s$' binary representation. In other words, if the number of digits where $p$ and $s$ are both 1 in their binary representation is the same parity as the number of 1s in $s$' representation, then student $s$ answered problem $p$ correctly.

For example, student $5=0...101$ answered question $2=0...010$ correctly because $f(5 \wedge 2) = f(0...000) = 0 = f(5)$. But student $7 = 0...111$ answered question $3 = 0...011$ incorrectly because $f(7 \wedge 3) = f(111 \wedge 011) = f(011) = 0 \neq 1 = f(7)$.

From there, it's easy to see that condition 1 is satisfied. A student's correct answers depends only on the digits of $s$ that are 1, and there are $2^{f(s)}$ possible combinations of those digits. Out of those, there will be half that has even number of 1s and half that has odd number of 1s, so that student answers half the questions correctly.

To prove condition 2, consider student $s$ and $t$. Consider $r = s \oplus t$ where $\oplus$ denotes the bitwise XOR operation. In other words, $r$ is a number whose binary representation is 1 at the digits where $s$ and $t$ are different, and 0 at the digits where $s$ and $t$ are the same. The problems where $s$ and $t$'s answers agree are exactly the problems where student $r$ answered correctly. To prove that assertion, note that $f$ is distributive with respect to $\oplus$. That is $f(a \oplus b) = f(a) \oplus f(b)$. This is because if $a$ has $d_a$ number of 1s and $b$ has $d_b$ number of 1s then $a \oplus b$ has $d_a + d_b \mod 2$ number of 1s, because the digits that were both 1s and turned into zero always come in pairs.

So suppose both $s$ and $t$ get problem $p$ right, then $p \wedge r = p \wedge (s \oplus t) = (p \wedge s) \oplus (p \wedge t)$ so $f(p \wedge r) = f(p \wedge s) \oplus f(p \wedge t) = f(s) \oplus f(t) = f(s \oplus t) = f(r)$ and similarly if they both get the problem wrong. We can show that if $s$ gets problem $p$ right and $t$ gets it wrong, then $r$ gets problem $p$ wrong as well. That way, we showed that student $s$ and $t$'s answers agree exactly on the problems that student $r$ gets right, and by condition 1, this is exactly half of all the problems. So condition 2 is proven.

Now for $m > 1$, let $l = 2^k$ so $n = lm$, we simply assign student $s$ answering problem $p$ correctly if and only if student $s$ answers problem $(p \mod l)$ correctly. In essence, we are duplicating problems $0,\dots, l-1$'s answers (which were constructed above) $m$ times. Condition 1 and 2 are still satisfied.

The second part of the proof is to show that this arrangement is optimal. That is, with $n = 2^km$ there is at most $2^k-1$ students.

For $n$ to be even then $k \geq 1$. For $k = 1$ we show that there is at most 1 student. That is, condition 1 can be fulfilled easily, but condition 2 cannot be fulfilled. Indeed, WLOG we may assume that student $A$ answered questions $1,\dots,m$ correctly and $m+1,\dots,2m=n$ incorrectly. If there is a second student $B$, then suppose above questions $1,\dots,m$ he answered $t$ questions correctly, then he must answer $m-t$ questions among the second half correctly. However, that means the number of questions that $A$ and $B$ agreed on is $t + (m- (m-t)) = 2t \neq m$, contradiction. So there is at most $2^1 - 1 = 1$ student for $k = 1$.

Now we use induction on $k$. Suppose that $k > 1$ and let $h = n/2 = 2^{k-1}m$. Take student $A$, and WLOG assume that he answered questions $1, \dots, h$ correctly (i.e. the first half). For any other student $B$, suppose he answers $t$ questions correctly on the first half, so $h-t$ questions correctly from the second half. The number of questions that $A$ and $B$ agreed on is $t + (h-(h-t)) = 2t = h$, so student $B$ answered $h/2$ questions correctly on the first half. This means all students other than $A$ must answer $h/2$ questions correctly on the first half.

Also note that if we replace $B$ with $B'$ whose answers are completely opposite of $B$, then condition 1 and 2 are both still preserved. $B'$ still answered half the questions, and the questions that $B$ agreed with other students are just "flipped." However, $B$ and $B'$ cannot both coexist because obviously condition 2 would be violated.

So now suppose that there are two students $B,C$ distinct from $A$. It's possible that $B$ and $C$ agree completely on the first half (and disagree completely on the second half). We see this a lot in the construction above. In that case, we call $B$ and $C$ "friends", and we put them under one "group." Also, if $B$ and $C'$ would have been friends, we still call $B$ and $C$ friends (as in, if $B$ and $C$ disagree completely on the first half but agree completely on the second half, we still call $B,C$ friends). Note that because $C$ and $C'$ cannot both coexist, we are not claiming that $B$ can be friends with two existing students. Indeed we shall show that $B$ is friends with at most one other person.

If $B$ and $C$ are friends, and $B$ and $D$ are friends. WLOG we may assume that $B,C,D$ agree completely on the first half (otherwise replace $C$ by $C'$ or $D$ by $D'$ or both). Suppose :
1. $X$ is the set of problems that $A$ got right, $B$ got right
2. $Y$ the set of problems $A$ got right, $B$ got wrong
3. $Z$ the set of problems $A$ got wrong, $B$ got right
4. $W$ the set of problems $A$ got wrong, $B$ got wrong

So $X \cup Y$ is the first half, and $Z \cup W$ is the second half. Because $C$ agree with $B$ on the first half, he must disagree completely on the second half. That means $C$ got $X \cup W$ completely right, and $Y \cup Z$ completely wrong. But we my apply the same argument to $D$, therefore $D$ got $X \cup W$ completely right and $Y \cup Z$ completely wrong. This violates condition 2 because now $C,D$ agree everywhere. Contradiction. Therefore, each group of friendship contains at most 2 students. (Some students may not have friends, so they are in a group each by himself).

Next, suppose $B$ and $C$ are not friends. Consider the answers of $C$ in $X,Y,Z,W$ that agree with $B$. Suppose there are $t_X, t_Y, t_Z, t_W$ answers that agree with $B$ respectively. Now by condition 2, the total number of agreement between $B$ and $C$ must be $h$, so: $$t_X + t_Y + t_Z + t_W = h$$ By condition 1, the total number of answers that $C$ got right must be $h$, so: $$t_X + (|Y| - t_Y) + t_Z + (|W| - t_W) = h$$ And note that $|Y| + |W|=h$ because those are the questions that $B$ got wrong. So the second equation can be written as: $$t_X + t_Z = t_Y + t_W$$ That means $t_X + t_Z = t_Y + t_W = h/2$. But also, $C$ must agree with $A$ for $h$ questions, so: $$t_X + |Y| - t_Y + |Z| - t_Z + t_W = h/2$$ But $|Y| + |Z| = h/2$ because those are the questions that $B$ disagreed with $A$, so $t_X + t_W = t_Y + t_Z = h/2$ Solving the two equations, we have $t_X = t_Y$. Next, because $C$ must answer $h/2$ questions correctly on the first half, then $t_X + |Y|-t_Y = h/2$, so $|Y| = h/2$, which means $|X| = |Y| = |Z| = |W| = h/2$. we get $t_X = t_W = t_Z = t_Y = h/4$. Because $k>1$ and $h = 2^{k-1}m$ then $h/4$ is still an integer. Therefore $t_X + t_Y = h/2$. So the conclusion here is that if $B$ and $C$ are not friends, then $C$ agreed with $B$ on exactly $h/2$ on the first half, and $h/4$ on the second half.

Suppose there are $2^k$ students, and because $A$ is one of them, then there are $2^k-1$ "non-A" students. Because each group contains at most 2 students, then there are at least $\lceil (2^k-1)/2 \rceil = 2^{k-1}$ groups. Take any student from each group to be the "representative" of that group. Now, consider their answers only on the first half of the exam. These answers satisfy the condition for the exams with $n/2 = h$ questions. Indeed, condition 1 is satisfied because all students other than $A$ must answer $h/2$ questions correctly. Condition 2 is also satisfied because every two students who are not friends must agree exactly $h/2$ on the first half. Therefore, now we have at least $2^{k-1}$ students (excluding student $A$) with $h = 2^{k-1}m$ problems that satisfy conditions 1 and 2, violating our induction hypothesis. Contradiction. So there must be at most $2^k-1$ students in an exam with $2^km$ problems.

Finally, because $2^{10} < 2019 < 2^{11}$, then in order for this situation to happen with 2019 students, $k \geq 11$. That means the least number of problems is $2^{11}.1 = 2048$.

Finite difference

Define sequences $x_i,y_i,i=1,2,\dots$ as follows: $$x_{n+1} = x_n^2 - 20$$ $$y_{n+1} = y_n^2 - 30$$ And define $d_i = x_i - y_i$. Find all possible starting pairs $(x_1,y_1)$ such that the set $\{d_1, d_2, \dots \}$ contains only a finite number of elements. Solution Just the outlines. If $x_1 = \pm 4 , \pm 5$ then $x_n$ is bounded, likewise if $y_1 = \pm 5, \pm 6$ it is bounded. It's easy to show that for other possibilities $x_n,y_n$ are both unbounded, and will be positive except for the first few terms.

If $x_n,y_n$ are bounded then they assume a finite number of values, therefore $d_i$ also assume a finite number of values, at most the combinatorial pairs of their images, but most likely much less. However, if one of them is unbounded, then say $x_n$ is unbounded, EVEN IF $y_n$ is bounded, then $x_n+y_n$ is unbounded. At this point it's easy to show that $x_n+y_n$ is monotonically increasing and unbounded (excxept for the first few terms) because once $x_n$ gets large enough, $y_n$'s fluctuation is not enough to make the sum decrease.

Now, if $x_n-y_n$ is unbounded, then $x_n^2 - y_n^2$ is unbounded. If $x_n - y_n$ is bounded then $x_n^2 - y_n^2$ is unbounded, EXCEPT if $x_n = y_n$ identically. But because they have different recursion formula, they can't always be identical. Meaning they're identical at most every other term. On the terms that they are not identical, $x_n-y_n$ is non-zero, and because $x_n+y_n$ is monotonically increasing and unbounded, then $x_n^2 - y_n^2$ is also unbounded. Therefore $d_n +10$ is also unbounded, so it assumes an infinite nunmber of values

Triangular equations

A triangular series of equations is a system of $k$ equations where the $k$-th row consists of $k+1$ terms on the LHS and $k$ terms on the RHS. For example: $$a + b = c$$ $$d + e + f = g + h$$ $$i + j + k + l + m = n + o + p$$ $$...$$ Given the numbers $1, 2, \dots, n^2$ and one number with the same parity as $n$ is removed, prove that the rest of the numbers can be arranged into a triangular series of equations.

For example, out of $1,2,\dots,9$, 3 is removed, so the rest can be written as: $$ 1+4 = 5$$ $$2 + 6 + 8 = 7 + 9$$ Another example, out of $1,2,\dots, 16$, 10 is removed, so the rest can be written as: $$1+3 = 4$$ $$2 + 5 + 8 = 6 + 9$$ $$7 + 11 + 12 + 14 = 13 + 15 + 16 $$

Solution (In Progress)

Suppose we color all the numbers with the same parity as $n$ with red, and color all the numbers with the opposite parity with black. Also, call the number that was removed, the missing number, $x$. A number is called "good" if, when missing, the rest of the numbers can be written as triangular system.

Note the triangular system below: $$1+2 = 3$$ $$4+5+6 = 7+8$$ $$9+10+11+12 = 13+14+15$$ $$...$$ $$k^2 + \dots + (k^2+k) = (k^2+k+1) + \dots + (k^2+2k)$$ $$...$$ $$(n-1)^2 + \dots + ((n-1)^2+n-1) = ((n-1)^2+(n-1)+1) + \dots + (n^2-1)$$ We call this system A. This system is missing $n^2$, and the system is triangular and correct. (The correctness of said system can be verified by simple arithmetic series on the $k$-th row).

So we know that $n^2$ is good. Furthermore, note that each row has the same number of odd numbers (that is, $k$-th row has $k$ odd numbers if $k$ is odd and $k-1$ odd numbers if $k$ is even). So if we increase each odd number by two, we'll still get a correct triangular system: $$3+2 = 5$$ $$4+7+6 = 9+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ So if $n$ is odd, 1 is good. Call this system B.

Similarly, the $k$-th row has $k$ even numbers in the LHS and $k-1$ even numbers in the RHS. We can increase the even numbers by two, but then the equation will be incorrect. Call the "weight" of an equation to be its RHS - LHS. Obviously, an equation is correct only if it has weight zero. If we increase all the even numbers by two, then the weight of the new equation is -2, for example: $$6+5+8 > 7+10,w=-2$$ But note that now $(k^2+k+2)$ is in the LHS while $k^2+k+1$ is still in the RHS. In other words, the largest number in the LHS is exactly one more than the smallest number in the RHS, so if we switch those two, we restore the weight back to zero: $$6+5+7 = 8+10$$ So we can form a new system this way: $$1+3=4$$ $$6+5+7 = 8+10$$ $$9+12+11+13 = 14+16+15$$ $$...$$ Next, note that out of the $n$ rows in the equation, we can take the first $k$ rows from system A, and the $n-k$ last rows from system B or C. For example: $$1+2 = 3$$ $$4+5+6 = 7+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ Now we are ready to prove the main assertion by induction. We will show the base cases later. For now, suppose it holds for $n=2,3$. Then, if $x \leq (n-2)^2$, there is a way to arrange $\{1, 2, \dots, (n-2)^2\} \ \{x\}$ in triangular form by induction hypothesis, and the last two rows can be taken from the last two rows of system B (if $n$ is even) or system C (if $n$ is odd). So then we consider cases where the missing number is $x > (n-2)^2$. In system A above, it would be in the last two rows. We will divide into cases depending on the position of $x$ in system A. Note that the missing number is always red.

Suppose $x$ is red on the last row RHS (meaning the missing number is in the interval $x \ in [(n-1)^2+(n-1)+1, n^2-2]$). Take out that number and replace it with $n^2$. Then now the last row has weight a positive even number in the interval $[2, n-1]$. We can switch a number $k$ from LHS and $l$ from the RHS, and the weight would decrease by $2(l-k)$. But the difference of the numbers in RHS and LHS ranges from 1 to $2n-2 > n-2$, and each side has consecutive numbers. So we know there are numbers that we can pick to switch so that the weight is reduced back to zero.

Suppose the missing number is red on the last row LHS, meaning the missing number is in the interval $x \in [(n-1)^2+1, (n-1)^2+(n-1)]$. Take out that number and replace it with $n^2$. Then the last row has weight a negative even number in the interval $[-2n+2, -n]$. Now, there exists a number in RHS $y$ such that $y-n^2$ is exactly half the weight of the last row, because the numbers in RHS is in the range $[(n-1)^2+(n-1)+1,n^2-1]$ so those numbers subtracted by $n^2$ is in the range $[-n+1, -1]$ which encompasses $\frac{1}{2} [-2n+2, -n]$. If we switch this number $y$ and $n^2$, the weight of the last row is restored.

Suppose the missing number is red on the second-to-last (STL) row LHS, meaning the missing number is in the interval $x \in [(n-2)^2, (n-2)^2+(n-2)]$. Take out that number and replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where $(n-1)^2+1$ used to be. The STL row now has weight negative even number in the interval $[-2n+2,-n]$, whereas last row has some other even number weight. The last row could be fixed with the procedure described above (as if $(n-1)^2+1$ was the missing number). However the STL row can be fixed by switching $(n-1)^2+1$ with an appropriate number in the STL RHS, because the numbers in STL RHS ranges from $[n^2-3n+3,n^2-2n]$ so the difference ranges from $[-n+1, -2]$ which encompasses $\frac{1}{2}[-2n+2,-n]$

Suppose the missing number is red on the STL row RHS. Same as before, take out that number, replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where it used to be. Same as above, the last row can be fixed using the previous strategy, whereas the STL row can be fixed by switching two numbers in the STL (similar to if the missing number is from RHS last row).

Now all that remains is to prove the base cases. For $n=2$, we have either $1+3=4$ or $1+2=3$. For $n=3$, the missing numbers could be $x=1,3,5,7,9$, but $x=9$ is already covered by system A above, $x=1$ covered by system B, and $x=3$ is shown in the example. For $x=5$: $$1+2=3$$ $$4+7+6 = 9+8$$ For $x=7$: $$1+3=4$$ $$2+5+8 = 6+9$$ (Really we're just applying the algorithm described above but we're including here for the sake of proof completeness).

Shifting matrix

An $n \times n$ matrix is filled with numbers, where there are $k$ number ones and the rest zero. The operation that is allowed on the matrix is to shift a single column down by one (so that each number in that column moves down by one, and the bottom most number goes to the top), or to shift a single row to the left by one.

Determine all $k$ such that, no matter how the initial condition is, through a series of operations, we can make it so that each column and each row has an even sum.

Tricolored polygon

Given a regular $(3n+2)$-gon, the vertices are colored with red, blue, or green such that there are $n+1$ green points, $n+1$ blue points, and $n$ red points. Prove that there exists a line going through a blue point and a green point, such that on one side of the line there are $k$ points of each color, and on the other side there are $(n-k)$ of each color (with $k \geq 0$).

Solution

First we claim that there is a way to pair each blue point with a green point such that the segments formed by each pair is non-intersecting. Proof:

Delete all the red points for now, so we are left with polygon with $(n+1)$ blue and green points each. Take any adjacent pair of a blue point and a green point, pair them, and then delete them. Now we are left with $n$ blue and green points each. Recursively apply this procedure until we are done. It's easy to see that the resulting segments are non-intersecting.

Now that we have $n+1$ such segments, label the points $(b_1, \dots, b_{n+1}, g_1, \dots, g_{n+1})$ where $b_i$ is a blue point that is paired with $g_i$. Let $S_i$ denote the segment formed by $b_ih_i$. Pick an arbitrary red point $R$. We define the following terminology: each segment divides the polygon into two. The "good" side of the segment is the side that contains $R$.

Since no two segments can intersect, then for two different segments $S_i,S_j$, one is fully on the good side of the other. If $S_i$ is fully contained in the good side of $S_j$ then we say that $S_j$ "covers" $S_i$. Note that for any two segments, if $S_i$ covers $S_j$ then $S_j$ does not cover $S_i$, and one necessarily covers the other.

Note the following properties. If $S_a$ covers $S_b$ and $S_b$ covers $S_c$ then $S_a$ covers $S_c$. Conversely, if $S_a$ and $S_b$ both cover $S_c$ then either $S_a$ covers $S_b$ or $S_b$ covers $S_a$. So we may define the relationship called "immediate covering." We say $S_a$ immediately covers $S_b$ if $S_a$ covers $S_b$ and there's no other $S_c$ such that $S_a$ covers $S_c$ and $S_c$ covers $S_b$.

Consider the graph with $n+1$ vertices $1,2,\dots,n+1$ and the edges where $i \to j$ if $S_i$ immediately covers $S_j$. Each segment can only be immediately covered by at most one other segment, so this graph is a tree. It cannot be a forest because for each root of each tree, one necessarily covers the other so there can only be one true root. Define the "height" of each node to be the distance between node $i$ to it's farthest leaf. So every leaf has height zero. If $i$ is a leaf and $S_j$ immediately covers $S_i$ (and only $S_i$), then $j$ has height 1, and so on. If a node has several children of differing heights, then the height of the node is 1 plus the maximum of its children's height.

Now also for each $i$, define $A_i$ to be the number of red points that are located on the good side of $S_i$. Define $B_i$ to be the number of descendants of $i$ in the above-mentioned graph. So, our aim is to show that there exists an $i$ such that $A_i = B_i$, because this would mean that on the good side of $S_i$, there are precisely $A_i$ red points, and $B_i$ segments, each of which contains $B_i$ blue points and $B_i$ green points. Now suppose, in our configuration, there is no $i$ such that $A_i = B_i$.

Our claim now is that for each $i$, $A_i > B_i$. We prove this by induction on the height of the nodes.

We start by looking at the leaves. If there's any leaf $i$ with $A_i = 0$ then there is a contradiction, because $B_i = 0$. So for each leaf $i$, $A_i \geq 1 > 0 = B_i$.

Now suppose that $A_i > B_i$ (which means $A_i \geq B_i + 1$) for each node of height $0, 1, \dots, k$, then let $S_a$ be a node of height $k+1$, and let its children be $S_{b_1}, \dots, S_{b_m}$. Its children has height at most $k$, so for each $i$, $A_{b_i} \geq B_{b_i}$ holds. Now, each red point on the good side of $S_{b_i}$ is also on the good side of $S_a$, therefore $$A_a \geq A_{b_1} + \dots + A_{b_m} \geq (B_{b_1} + 1) + \dots + (B_{b_m}+1) = m + \sum B_{b_i} = B_a$$ The first inequality is due to the fact that each red point in $A_{b_i}$ must be contained in $A_a$ as well (although there may be more red points in $A_a$. The second inequality is from induction hypothesis. The third inequality is by construction of the graph and definition of $B_a$, because the number of descendants of $S_a$ can be counted by summing the number of descendant of children, plus each of the children themselves.

So we established that $A_a \geq B_a$, but because we assumed that there is not $A_i = B_i$, then $A_a > B_a$. Thus, by induction on the height of each node, we can claim that $A_i > B_i$ for each $i$ in the whole graph.

Now consider the root node $r$. We concluded that $A_r > B_r$. But $A_r$ is the number of red points on the good side of $S_r$, which is at most $n$. $B_r$ is the number of descendants of $S_r$, which is $n$. Contradiction.

Thus there must be an $i$ such that $A_i = B_i$ and that is our desired segment.

Moving coins across the board

On a $1 \times 2018$ chess-board, the $n (n < 2018)$ left-most squares contain 1 coin each. Alice and Bob are playing a game, where on each turn the player may choose a coin and move it to the right one or two units. The only condition is that each square may only contain one coin at a time (no "stacking"), except the last square (right-most square). Alice goes first. The player who cannot make a legal move loses. Determine all $n$ such that Alice has a winning strategy.

Solution

Label each square by its distance from the right-most square. So the right-most square is called square zero, and the left-most square is called square 2017. Suppose $(a_1, a_2, \dots, a_k)$ denotes the condition that there is a coin on each of the cells $a_1, \dots, a_k$ and the rest of the coins are in the square zero. WLOG, we may assume $a_1 < a_2 < \dots < a_k$.

Claim:

We claim that $(a_1, \dots, a_k)$ is a losing position if and only if $a_1 + \dots + a_k$ is divisible by 3.

First note that the game ends only when there's no more legal move left, and that's when all the coins are on square zero. So as long as the sum of the coin numbers are greater than zero, there is always a legal move available. At the very least, the coin with the lowest number can be moved to the right 1 or 2 steps (possibly reaching zero in the process).

Lemma:

If the sum of the numbers are not divisible by 3, there is always a legal move to make it divisible by 3 within one turn.

Note that our claim is a corollary of the lemma. If the sum of the numbers is divisible by 3, then no matter what move you do, you can only reduce it by 1 or 2. Based on the lemma, the opponent can always counter it by bringing down to the next multiple of 3. Therefore, your opponent will never face the situation without any legal move. Conversely, if it's not divisible by 3, you can always bring it to a multiple of 3 within one turn so that your opponent is facing a losing position next. And your winning strategy is always to keep the sum of the numbers divisible by 3.

Proof of lemma:

If the the sum of the numbers is $3m+1$, then you only need to move the lowest-numbered coin down by 1. This is always possible because it is at least 1. If the sum of the numbers is $3m+2$, then you need to move ANY coin down by 2. Suppose that this is not possible, either due to prospect of collision or running against the end of the board. That means the following:

1. There are no two consecutive empty cells. If there are two or more consecutive empty cells, then the coin to the left of that block can be moved down by two. This means that $a_i - a_{i-1} = 1,2$ for each $i$.

2. There is nothing on cell 2, because otherwise we can always move it to cell 0 directly.

3. There is no "jumping over" possible. Meaning, if cell $x$ is empty but $x+1,x+2$ are both occupied, we can take $x+2$ and move it to $x$. So this configuration is not allowed: EMPTY, OCCUPIED, OCCUPIED.

This means cell 1 has a coin on it. $a_1 = 1$. Since 2 is empty, then 3 must have a coin on it ($a_2 = 3$). If 4 has a coin on it, then it violates condition 3 above, so 4 must be empty. That means 5 must be occupied (by condition 1). We can continue this pattern indefinitely, to arrive at the conclusion that current condition must be: $(1,3,5, \dots, 2k-1)$. The sum of the numbers is therefore $1 + 3 + \dots + 2k-1 = k^2$, which cannot be $3m+2$. Contradiction. Hence it's always possible to choose a coin to move down by 2. This completes our proof of the lemma.

Now, the initial condition is $(2018-(n-1), 2018-(n-2), \dots, 2018)$, so that the sum of the numbers is: $n(4037-n)/2$. For this to be divisible by 3, either $n$ is divisible by 3, or $n \equiv 2 \mod 3$. These are the losing positions. So in order for Alice to have winning strategy, $n \equiv 1 \mod 3$.

Marbles in 3 buckets

Given 3 buckets, each containing $n$ marbles. Alice and Bob are playing a game, where on each turn, the player may remove 1, 2, or 3 marbles from a single bucket. Alice goes first. The player who removes the last marble wins. Determine all $n$ such that Alice has a winning strategy.

Solution

If $n$ is divisible by 4 then Bob has a winning strategy, and if $n$ is not divisible by 4 then Alice has a winning strategy.

First note that $(4m,k,k)$ is a losing position for any $k \geq 0,m > 0$. Because if you remove $p$ marbles from the first bucket, your opponent may remove $4-p$ marbles to go back to $(4(m-1), k k)$. And if you remove from any of the second or third pile, your opponent may mirror that to go back to $(4m, k-p, k-p)$. Thus, no matter what you do, your opponent always has a legal move to make.

Therefore if $n$ is divisible by 4, assuming Bob plays optimally, Alice loses the game.

But if $n$ is not divisible by 4, say $n = 4m+a, a=1,2,3$. Then Alice may remove $a$ from the first bucket, to arrive at $(4m,n,n)$ which is a losing position for Bob.

Generalization

If there are $n$ buckets of $n$ marbles, we can employ the same strategy. The goal is to force your opponent into a "symmetric" situation where no matter what he/she does, you can always mirror it.

If $n$ is divisible by 4, then $(n,n,\dots,n)$ is a losing position because no matter what you do, your opponent can always mirror it. In general, the situation where there are an even number of buckets left and each pair of buckets contains the same number of marbles is a losing position.

If $n=4m+1,4m+3$, then you can employ the same strategy as above. Alice transforms the configuration into $(4m, a,a, b,b, \dots, z,z)$ and from there no matter what Bob does, Alice can always mirror it.

Variation

Now, suppose there's only $n$ marbles total and it is to be distributed among all 3 buckets, with each bucket containing at least one marble. Alice determines the distribution, and Bob makes the first "regular" turn. Determine all numbers $n$ such that there exists a way for Alice to distribute in such a way that Bob always loses.

Solution

At this point, we have to characterize the conditions in which configuration $(a,b,c)$ is a losing position. It's clear to see that $(a,0,0)$ is a losing position if and only if $a \equiv 0 \mod 4$.

Now consider the configuration $(a,b,0)$. If $a \equiv b \mod 4$ then this is a losing position, because the opponent can always mirror you move to keep the condition true. Therefore, if $a \neq b \mod 4$, it is a winning position because we can turn it into the above-mentioned losing position for our opponent.

Now consider the configuration where there are three non-zero buckets left. As we saw above, $(4a,b,b)$ is a losing position because your opponent can always mirror your steps, and restoring to original configuration, and consequently, $(a,b,b)$ is a winning position if $a \neq 0 \mod 4$ because you can turn it into the form $(4a,b,b)$.

We can take this reasoning one step further by claiming, the configuration $(a,b,c)$ where $b \equiv c \mod 4$ is a losing position if and only if $a \equiv 0 mod 4$. Indeed, if $a$ is divisible by 4, then any move you make in the first bucket will be countered in the first bucket, and any move you make in the second or third buckets will also be countered to keep $b \equiv c \mod 4$. Thus either you will bring $a$ below 4 and your opponent can empty the first bucket, leaving you to $(0,b,c)$ which is a losing position, or you will empty one of the second or third buckets first. In the latter case, then your opponent can still mirror it to arrive at $(a,0,c)$ where both $a,c$ are divisible by 4, which is a losing position. Conversely, if $a$ is not divisible by 4, you can make it divisible by 4 to be a losing position for your opponent.

Finally we prove that $(a,b,c) \equiv (1,2,3) \mod 4$ is a losing position, because any move that is made from here will result in a winning position. If we take from first bucket, we now get $(2/3/0, 2,3) \mod 4$ all of which are winning positions. If you take from second bucket, we get $(1, 3/0/1, 3)$ also winning positions, similarly if we do from third bucket. The point is that there is no way to avoid $(a,a,b)$ form where $b $ is not divisible by 4, or $(0,a,b)$ form.

Thus, if $n > 4$ is even, Alice has a winning strategy as follows. If $n = 4m$ then Alice distributes the marbles as $(4(m-1),2,2)$. If $n=4m+2$ she distributes it as $(4m,1,1)$. Both are losing positions Bob. But if $n=4$, then Bob has a winning strategy. Alice has no choice but to distribute the marbles as $(1,1,2)$ initially, and Bob can turn it into $(1,1,0)$ which is a losing position for Alice.

If $n$ is odd, Bob has a winning strategy no matter how Alice distributes the marbles. If all the three buckets contain odd number of marbles, then two of them will be congruent modulo 4, and the third one will not be divisible by 4, and that is a winning position for Bob. If two buckets contain even numbers and the third one odd, we have two choices. Either the two even buckets are both $\equiv 2 mod 4$, which means it's still a winning position for Bob, or at least one of them is divisible by 4, which is also a winning position for Bob.

Bottom line, Alice has a way to distribute the marbles into a losing position for Bob if and only if $n$ is even and $n > 4$.

Marking number game

Let $n > 2$ be an even number. On the board, there are numbers $1, 2, \dots, n$, and initially the number 1 is marked, and no other numbers are marked. Alice and Bob are playing a game, with Alice moving first. On each turn, they may choose a number $k$ that is currently unmarked, and mark it, provided: $k+1$ was previously marked, OR $k$ is even and $k/2$ was previously marked. The player who gets to mark the number $n$ wins the game.

Determine all $n$ such that Alice has a winning strategy.

Solution

As soon as one player marks $n/2$, then he/she loses, because the opponent can mark $n$ directly after that. Also, the number $n$ can be marked ONLY after $n/2$ is marked (by virtue of $n/2$ being marked, since there is no number $n+1$ on the board). Therefore, the crux of the game is to avoid the number $n/2$ at all costs.

Suppose $n = 2m$. Define the numbers in set $\{ 2,3,\dots, n-1 \}$ to be "accessible" if it can be marked without ever marking $m$. Obviously $m$ is not accessible. Let $A$ be the set of accessible numbers. For example, for $n=12$ the accessible numbers are: $A = \{ 2, 3, 4, 7, 8 \}$. Note that 6 is not accessible by definition. 5 is not accessible because in order to mark 5, we'd have to go through 6. 11 is not accessible because it can't be reached without marking 12, which has to go through 6. 10 is also not accessible because it can only be reached through 11 or 5, both of which are not accessible. Therefore 9 is also not accessible.

Now, as long as there's an unmarked number in $A$, then the current player can always choose a legal move to play. Not all unmarked numbers in $A$ will be eligible to be marked, but by the construction of $A$, we can reach that number through other numbers that have been marked (and therefore also in $A$), so as long as there exists an unmarked number in $A$, there is a legal move to be played.

As soon as all numbers in $A$ are marked, then the next person has to mark $m$, and the other player can win immediately. In the case of $n=12$ above, 10 will not ever be marked because as soon as 6 is marked, the next person marks 12. Therefore the winner of the game (assuming both sides play optimally) depends on the parity of $|A|$. Alice has a winning strategy if and only if $|A|$ is odd.

Generally all the numbers from $\{2, 3, \dots, 2m-2 \}$ are accessible, with a handful of exception. $m$ is by definition inaccessible, and $2m-1$ is also inaccessible. So we want to list all the numbers that are not accessible. We divide into two cases.

If $m$ is odd:

Consider the sequence: $1,2,4,3,6,5,8,7, \dots, 2k, 2k-1, 2k+2, 2k+1, \dots, 2m-2, 2m-3$. That is a legal sequence to mark numbers. Therefore, almost all numbers in the set $\{2, 3, \dots, 2m-2 \}$ are accessible except $m$, because we can simply go through the sequence, and only skipping $m$. No further interruption to the sequence will occur because the highest number in the sequence is $2m-2 < 2m$ so it's not affected by the fact that $m$ was never marked. Thus, $A = \{2, \dots, 2m-2 \} - \{ m \}$, and $|A| = 2m-4$. This means Alice does not have a winning strategy because Bob has a winning strategy.

If $m$ is even:

Same as before, we go through the sequence, but skipping $m$. This has several ramifications. First, because $m$ is even, then $m-1$ is not accessible. Thus, there are two numbers that are also "deleted" from that sequence later on: $2m-2, 2m-3$. The rest of the sequence is not affected, because $m+2, m+4,m+6,\dots, 2m-4$ can still be marked. Thus: $|A| = 2m-3 - 4 = 2m-7$. This means Alice has a winning strategy.

This reasoning breaks down when $m=2$ because then $2m-2 = 2$ so there was no other choice and Bob wins. But this is the only corner case. Therefore, Alice has a winning strategy if and only if $n > 4$ and $n$ is divisible by 4.

Collinear marbles

From OSP SMA 2018. On a 200x200 checkerboard, we place red and blue marbles, at most 1 marble per cell. Two marbles are considered "collinear" if they are on the same column or row. For each red marble, there are exactly 5 collinear blue marbles, and for each blue marble, there are exactly 5 collinear red marbles. Find the maximum number of marbles on the board.

Uniquely Reachable Numbers

Let $n > 1$ be an integer. Given set $A_n = \{ 1, 1, \dots, 1, 2, 2, \dots, 2, \dots, n-2, n-2, n-1, n \}$ where there are:

$2^{n-1}$ number $1$

$2^{n-2}$ number $2$

$\dots$

$2^2$ number $n-2$

$2$ number $n-1$

$1$ number $n$

$1$ number $n+1$

(As you can see, there are a total of $2^n$ numbers in $A_n$). A positive integer is called "reachable" if it can be expressed as a sum of $2^{n-1}$ numbers in $A_n$. A reachable number is called "uniquely reachable" if that sum is unique (not counting permutations of the summands).

For example, for $n=3$, we have $A_3 = \{1,1,1,1,2,2,3,4\}$. The number 10 is uniquely reachable because it can be expressed as $10 = 1+2+3+4$ and this representation is unique (we consider $1+2+3+4$ and $3+4+2+1$ to be the same way). However, the number $6$ is not unique because $6 = 1+1+2+2 = 1+1+1+3$.

Find all the uniquely reachable numbers.

Solution

Answer: the only uniquely reachable numbers are $2^{n-1}, 2^{n-1}+1, 3.2^{n-1}-2,3.2^{n-1}-1$.

Proof:

We prove by induction. Now first note a few things:

The sum of all numbers in $A_n$ is $2^{n+1}-1$. So the number $k$ is reachable iff the number $2^{n+1}-1-k$ is reachable. Similarly, $k$ is uniquely reachable iff the number $2^{n+1}-1-k$ is uniquely reachable. We prove this by simply taking the complement of the numbers chosen to represent $k$. There are exactly half of the numbers in the set, so the sum of the numbers that are not chosen to represent $k$ will be $2^{n+1}-1-k$.

Also, the range of reachable numbers is from $2^{n-1}$ to $3.2^{n-1}-1$ (by taking the $2^{n-1}$ smallest numbers, that is all ones, all the way to the largest numbers, that is everything but ones). So any number outside of this interval is clearly not reachable by any choice of $2^{n-1}$ numbers in $A_n$.

We shall prove the following statements in tandem:

1. All numbers in the interval $[2^{n-1}, 3.2^{n-1}-1]$ are reachable

2. The uniquely reachable numbers are $2^{n-1}, 2^{n-1}+1, 3.2^{n-1}-2,3.2^{n-1}-1$.

These statements are easy to verify for $n=2$. Now suppose they all hold for $n-1$.

Claim 1: If $k$ is (uniquely) reachable in $A_{n-1}$ (it can be expressed as sums of $2^{n-2}$ numbers in $A_{n-1}$) then $k+2^{n-2}$ is (uniquely) reachable in $A_n$.

Proof: Take $k$ and its representation of $2^{n-2}$ summands, and add $2^{n-2}$ ones to it. This new representation is valid in $A_n$ because there are at most $2^{n-2}$ ones in $A_{n-1}$, and by adding $2^{n-2}$ more ones, we are using at most $2^{n-1}$ ones. The other numbers that are represented in $A_{n-1}$ are unchanged and still available to use in $A_n$. Each distinct representation of $k$ will yield a new representation of $k + 2^{n-2}$, so the uniqueness of reachability also transfers to the new representation.

Claim 2: If $k$ is (uniquely) reachable in $A_{n-1}$ then $k + 3.2^{n-2}$ is (uniquely) reachable in $A_n$.

Proof: If $k$ is (uniquely) reachable in $A_{n-1}$ then $2^n-1-k$ is (uniquely) reachable in $A_{n-1}$, then by claim 1, $2^n-1-k+2^{n-2}$ is (uniquely) reachable in $A_n$, therefore $2^{n+1}-1-(2^n-1-k+2^{n-2}) = k + 3.2^{n-2}$ is also (uniquely) reachable in $A_n$.

From the two claims above, because all numbers in the interval $[2^{n-2}, 3.2^{n-2}-1]$ are reachable in $A_n$, now we apply claim 1 to this interval. We have the interval $[2^{n-1}, 2^n-1]$ reachable in $A_n$. Similarly, we apply claim 2 to this interval, we have $[2^n, 3.2^{n-1}-1]$ reachable in $A_n$. By combining these two intervals, we have $[2^{n-1}, 3.2^{n-1}-1]$ reachable in $A_n$. Thus we have proven statement 1 of the induction hypothesis.

Now we prove uniqueness. By induction hypothesis, the numbers in the interval $[2^{n-2}+2, 3.2^{n-2}-3]$ are reachable but not uniquely in $A_{n-1}$. By claim 1, we can the interval $[2^{n-1}+2, 2^{n}-3]$ is reachable but not uniquely. Likewise, we can claim 2 to establish that the interval $[2^n+2, 3.2^{n-1}-3]$ is reachable but not uniquely. Then now we know that all numbers in the interval $[2^{n-1}+1, 3.2^{n-1}-3]$ are reachable but not uniquely, except of the following four numbers: $2^n-2, 2^n-1, 2^n, 2^n+1$. They are reachable but not yet proven as uniquely reachable.

Claim 3: If $k$ is (uniquely) reachable in $A_{n-1}$ then $k + 2^{n-1}$ is (uniquely) reachable in $A_n$.

Proof: First note that $A_n$ can be formed by adding one to each element of $A_{n-1}$ and then adding $2^{n-1}$ to it. Now, take any representation of $k$ in $A_{n-1}$. Add 1 to each summand, and then add $2^{n-2}$ ones to it. Now we have $2^{n-1}$ summands, and only $2^{n-2}$ are ones. The rest (the higher summands) are valid in $A_n$ because they were 1 more than the summands that were valid in $A_{n-1}$. The new sum is $k + 2^{n-2} + 2^{n-2} = k+2^{n-2}$. Distinct representations in $A_{n-1}$ would also result in distinct representations in $A_n$.

Because $n \geq 4$, we have $2^{n-2}+2 \geq 2^{n-1}-2$ and $2^{n-1} \leq 3.2^{n-1}-3$, so by induction hypothesis, $2^{n-1}-2$ and $2^{n-1}$ are non-uniquely reachable in $A_{n-1}$, then $2^n-2$ and $2^n$ are non-uniquely reachable in $A_n$. Then, their complements $2^n-1$ and $2^n+1$ are also non-uniquely reachable. This completes our proof of statement 2

Non-attacking rooks

Given an $n \times n$ chess board and $2n+1$ rooks placed on it, prove that we will always be able to choose 3 rooks who can't attack each other.

Solution

Partition the board into $n$ groups in a "broken diagonal" pattern. That is, cell $(i,j)$ belongs to group $i+nj \mod n$. Two cells in the same group can't attack each other (easily shown either by diagonal argument or modular analysis).

Because there are $2n+1$ rooks, then there are 3 rooks that sit on the same group.

A tale of two cities

In an island with 257 cities, there are 2018 railroad segments such that each segment connects exactly 2 cities, and each pair of cities are connected by at most 1 segment. A group of 10 cities is called "clustered" if each pair of those 10 is connected by a segment.

Prove that there exist 2 unconnected cities that we can connect without increasing the number of clustered groups.

Solution

Proof by contradiction. Suppose we cannot connect two cities without increasing the number of clustered groups.

Let $n=257$ be the number of cities. Take all possible groups of 10 cities, ${n \choose 10 }$ of them, and count how many segments there are among them. Of course, if the group is clustered, it should have ${10 \choose 2} = 45$ segments. Let $S$ be the sum of unconnected pairs, over all possible groups of 10 cities.

Now let us count $S$ in a different way. Take 2 connected cities $A$ and $B$. The segment $AB$ contributes to $S$ only when the chosen group of 10 cities include $AB$, so this segment is counted ${n-2 \choose 8}$ times. Because there are 2018 segments, then $S$ must be:

$$S = {n-2 \choose 8}.(2018)$$

Note that $2018 < 2020 = 8n-36$, so $S < {n-2 \choose 8}.(8n-26)$. That means, on average, there are $S / {n \choose 10 }$ segments.

Non-adjacent subsets

Find the number of subsets of $n$ such that if $i$ does not belong in the subset then either $i+1$ or $i-1$ belongs to the subset. (Hint: use double recursion, use fibonacci series)

symmetric 2 variable function

Suppose $S = \{1,2,\dots,n\}$ and $f: S \times S \to R$ satisfies the following: $$f(i,j) + f(j,i) = 0 \forall i,j \in S$$ Now for any two number $i,j$, we say that $i$ is superior to $j$ if there exists a $k$ (not necessarily distinct from $i,j$) such that $f(i,k) + f(k,j) \geq 0$. Show that there exists a number $x \in S$ such that $x$ is superior to all elements of $S$.