Consider the infinite grid of lattice points in $\mathbb{Z}^3$. Little D and Big Z play a game, where Little D first loses a shoe on an unmunched point in the grid. Then, Big Z munches a shoe-free plane perpendicular to one of the coordinate axes. They continue to alternate turns in this fashion, with Little D's goal to lose a shoe on each of $n$ consecutive lattice points on a line parallel to one of the coordinate axes. Determine all $n$ for which Little D can accomplish his goal. David Yang.
Problem
Source: ELMO Shortlist 2011, C4; also ELMO #6
Tags: analytic geometry, combinatorics proposed, combinatorics
11.10.2016 08:28
Can anyone post a solution?
10.03.2018 22:07
Little D can accomplish his goal for all $n$. In what follows $n$ is fixed. We define $X=Y=Z={\mathbb Z}$ (calling each an axis) and will color the elements of these three sets in the following way: If little D loses a shoe on $(x,y,z)$, then we color the three elements $x \in X$, $y \in Y$, $z \in Z$ red. If big Z munches $yz$-plane with $x$-intercept $x$, then we color $x \in X$ blue; similarly for the other two cases. The conditions ensure that no number is ever colored over twice. A red interval is a contiguous sequence of red elements $\{a,a+1,\dots,b\}$ in one of $X$, $Y$, or $Z$; the length is the number of elements. It is alive if none of $\{a,\dots,a+n-1\}$ are blue (meaning it could be completed on the right to a red interval of length $n$). Claim: For each $\ell = 1, 2, \dots, n$, Little D can create arbitrarily many alive red intervals of length $\ell$ on the same axis. Proof. The proof is by induction on $\ell$. For $\ell = 1$, this follows by dropping shoes on $(n, n, n)$, $(2n, 2n, 2n)$ and so on. After $m$ shoes are dropped, there will be at least $2m$ alive red intervals of length $1$, since on each turn big Z can only kill at most one red interval. By pigeonhole, we can then guarantee some axis has at least $\frac23m$ alive. For the inductive step, suppose we have sufficiently many alive red intervals of length $\ell$ on an axis, say $X$. We then iteratively perform the following procedure which lasts $\ell+1$ turns. First, select a large integer $t$. Then, on each turn, little D drops a shoe on $(x,y,z)$ where $x$ is chosen to extend a red interval in $X$ by one, $y = t, t+1, \dots, t+\ell$ in that order, i.e.\ we try to build an entirely new red interval from scratch (unless the desired $y$-value is taken, in which case we do anything). This will generate $\ell+2$ red intervals of length $\ell+1$ in $\ell+1$ turns. If we repeat this procedure $M$ times we get a total production of $M(\ell+2)$ red intervals of length $\ell+1$, over $M(\ell+1)$ turns. Since Big Z can kill at most one each turn, we have at least $M$ red intervals left over at the end, hence at least $M/2$ in either $X$ or $Y$. Taking $M$ large enough completes the induction. $\blacksquare$ Suppose now that $\{a,\dots,a+n-1\}$ is an red interval of length $n$ in $X$. If $(a,y,z)$ is any point with a shoe on it, it then follows that little D can drop a shoe on each of $(a+1,y,z)$, \dots, $(a+n-1,y,z)$ and win. Remark: The problem works equally well in two dimensions.
11.06.2024 19:15
We claim Little D can get every $n$. Rename Little D to be Pikachu and Big Z to be Charizard. Define a $3$-tac-toe game as a game on $3$ occurences of ${\mathbb Z}$ coloring cells in ${\mathbb Z}$ between Pikachu and Charizard. Each turn, Pikachu colors up to one cell in each occurence of ${\mathbb Z}$ red and Charizard colors one cell blue. Then if Pikachu gets a consecutive $n$-run in one of the copies of ${\mathbb Z}$, then Pikachu wins. Claim: Pikachu can win for $n$ iff they can win at $3$-tac-toe. Proof. If we consider the $3$ occurences of ${\mathbb Z}$ as an axes for ${\mathbb Z}^3$ and Charizard's move as blocking off a plane, then Pikachu's move corresponds to putting a shoe down. Then an $n$-run corresponds to $n$ adjacent planes perpendicular to the same normal vector. Then put $n$ shoes, one in each plane parallel to the normal vector to finish. Likewise, $n$ consecutive shoes corresponds to an $n$-run. $\blacksquare$ We now further reduce the $3$-tac-toe game as follows. Divide all three copies of ${\mathbb Z}$ into $n$-intervals. Pikachu stops colors in an interval once Charizard colors in that interval. Then we can replace each integer with a basket. Pikachu can place up to one marble in a basket in each copy of ${\mathbb Z}$ on their turn and Charizard can place a lid on of the baskets. Pikachu wins if they can get $n$ marbles in one basket. We then further buff Charizard by allowing them to place three lids at once, but only at the same index in each row. By considering the three baskets as one big basket, it's equivalent to get at least $3n$ marbles in the big basket. As such, we can consider the case of infinite baskets where Pikachu can place up to $3$ marbles arbitrarily on their turn and Charizard places one lid each turn. Pikachu wants to get at least $3n$ marbles in some basket. It's equivalent to solve getting $n$ marbles in some basket. Claim: Pikachu can get arbitrarily many baskets with $k$ marbles. Proof. The base case of $k=1$ follows by Pikachu spamming marbles in three new baskets each turn, of which Charizard can cover at most $1$. Then induction follows by doing this to get arbitrarily baskets with $k-1$ marbles, and then for each turn putting three marbles in each of these baskets, of which Charizard can cover at most $1$. $\blacksquare$ Remark: This still holds true even if Charizard can delete two entire shoe-free planes each turn.