Lesson 3

Optional Problems.

1. (20 points) Two players are playing the following game. On the board, there are integers from \(1\) to \(n\). In each move, a player is allowed to cross out a number and all of its divisors. The player who cannot make a move loses. Who wins with optimal play?
   Hint:

   Think how the first player can steal the strategy of the second player.
2. (20 points) In the game “Chomp”, players take turns breaking off pieces from a rectangular chocolate bar of size \(n \times m\). On each turn, a player is allowed to choose any piece and break it off, as well as everything above and to the right of it (in other words, on a turn, you can choose a piece \((x, y)\) and break off all the pieces \((x', y')\) where \(x' \geq x\) and \(y' \geq y\)). The player who eats the bottom-left piece loses. Who wins when playing optimally?
   Hint:

   Think how the first player can use the strategy of the second player to win.
3. (20 points) Compute, up to a polynomial factor, the minimum number of balls of radius \(n/4\) needed to cover \(\{ 0, 1 \}^{n}\).
   Hint:

   For the upper bound, calculate how many random balls are sufficient.
4. (20 points) Suppose \(C_{1}\) is a \((n, k_{1}, d_{1})\) code and \(C_{2}\) is a \((n, k_{2}, d_{2})\) code over \(\mathbb{F}_{2}\). Let \[C_{3} = \{ x \circ (x + y) \colon x \in C_{1},\ y \in C_{2} \}.\] Prove that \(C_{3}\) is a \((2n, k_{1} + k_{2}, \min \{ 2 d_{1}, d_{2} \})\) code. Also, prove that if \(C_{1}, C_{2}\) are linear and over \(\mathbb{F}_{q}\), then \(C_{3}\) is also linear.
5. (30 points) Let \(C\) be a \((2d, \log m, d)\) code over \(\mathbb{F}_{2}\). Prove that \(m \le 2d\).
   Hint:

   Place the vectors in \(\mathbb{R}^{n}\) such that any two vectors \(c_{i}\) and \(c_{j}\), for \(i \neq j\), form a large angle between them.