Let $m$ and $n$ be fixed positive integers. Tsvety and Freyja play a game on an infinite grid of unit square cells. Tsvety has secretly written a real number inside of each cell so that the sum of the numbers within every rectangle of size either $m$ by $n$ or $n$ by $m$ is zero. Freyja wants to learn all of these numbers. One by one, Freyja asks Tsvety about some cell in the grid, and Tsvety truthfully reveals what number is written in it. Freyja wins if, at any point, Freyja can simultaneously deduce the number written in every cell of the entire infinite grid (If this never occurs, Freyja has lost the game and Tsvety wins). In terms of $m$ and $n$, find the smallest number of questions that Freyja must ask to win, or show that no finite number of questions suffice. Nikolai Beluhov
Problem
Source: USA Team Selection Test for IMO 2023, Problem 2
Tags: combinatorics, USA TST, USA TST 2023, game, ilostthegame
16.01.2023 20:06
The answer is $\boxed{(m-1)^2+(n-1)^2}$ if $\gcd(m,n) = 1,$ otherwise $\boxed{\infty}$. If $\gcd(m,n) = k > 1,$ then all chosen squares can be $0$ and there could be a column far away going $k-1,$ followed by $k-1$ negative ones, then $k-1$ again, and so on. Call a solution $S$ for $m,n$ a way of placing a value to each square in the infinite grid so the conditions for $m \times n, n \times m$ are satisfied. With solutions $S_1,S_2$ define the sum of $S_1$ and $S_2$ as placing in each square the sum of the values it had in $S_1$ and $S_2$. Given an arbitrary $(n-1) \times (n-1)$ subgrid $G$, every entry of a solution $S_n$ for $1, n$ is a linear combination of the entries of $G$. So it is necessary and sufficient to solve for $(n-1)^2$ variables, and each constraint fixes a linear combination of the variables. We need $(n-1)^2$ constraints exactly or the configuration is impossible to determine. But fixing all entries of $G$ directly obviously works. Claim: Any solution $S$ for given relatively prime $a,b>1$ is uniquely expressed as the sum of a solution $S_a$ for $1,a$ and a solution $S_b$ for $1,b$. It suffices to prove there is exactly one $S_a$ that works. It is necessary and sufficient that all $1 \times b$ (horizontal beams) or $b\times 1$ subgrids (vertical beams) of $S_a$ sum to the value of the corresponding subgrids in $S$. Take any $(a-1) \times (a-1)$ subgrid $G$. Take the set $B$ of $1 \times b$ subgrids with their leftmost square in $G$. For each $S,$ we claim that the sums of the subgrids in $B$ will fix the values in all other $1 \times b$ or $b \times 1$ subgrids. 1) Fix every $1 \times b$ subgrid in the same column as one of the subgrids in $B,$ using that every $a \times b$ subgrid sums to $0$. 2) Fix every $b \times 1$ subgrid. The $b \times 1$ subgrids in a particular row have sums periodic every $a$ subgrids (since every $b \times a$ subgrid sums to $0$), and also every $a$ consecutive $b \times 1$ subgrids in the row sum to $0.$ In that row, we can get the sum of $a-1$ consecutive $b \times b$ subgrids. Note that $\gcd(a,b) = 1$ so we can solve the system of $a$ equations uniquely for our $a$ variables. 3) Similarly, fix the rest of the $1 \times b$ subgrids. It's also easy to see that in each $S_a,$ the sums of the subgrids in $B$ fix the entries of $G$ and thus $S_a.$ So we're done. $\square$ So to find a solution $S$ for $a,b>1$, it is necessary and sufficient to find a solution $S_a$ for $1,a$ and a solution $S_b$ for $1,b$ summing to $S$. So it is necessary and sufficient to solve for $(a-1)^2+(b-1)^2$ variables and each constraint fixes a linear combination of the variables. We need $(a-1)^2+(b-1)^2$ constraints exactly or the configuration is impossible to determine with any number of constraints. When a large subgrid is fixed, we can find one square at a time exploiting the fact that there exist $c,d \in \mathbb{N}$ where $ca-db = 1$. So we're done. $\blacksquare$
16.01.2023 20:08
What the heck. The answer is $(m-1)^2+(n-1)^2$ for $\gcd(m, n) = 1$, and it is impossible otherwise. Impose a coordinate system on the cells. We call a way to fill up the grid such that the sum of the entries in each $m \times n$ or $n \times m$ rectangle is $0$ a board. Note that making the entries of boards complex does not change the answer. Furthermore, the set of all boards is a $\mathbb C$-vector space. It's not hard to see that we simply wish to find its dimension. The rest of the solution is split into three parts: Part 1: If $\gcd(m, n) = g > 1$, then the vector space is infinite dimensional. Proof: Let $\omega$ be a primitive $g$th root of unity. Then, for any $k$, putting $\omega^y$ in the cell $(k, y)$ for all $y \in \mathbb Z$ and $0$ in the cell $(x, y)$ for all $x \ne k$ is a board. Furthermore, all such boards are linearly independent, so the conclusion follows. $\square$ Part 2: If $\gcd(m, n) = 1$, then knowing the values in $(m-1)^2+(n-1)^2$ cells is enough to determine the whole grid. In other words, the dimension of the vector space is at most $(m-1)^2+(n-1)^2$. Proof: We claim that knowing the values in the cells \[([1, m-1] \times [1, m-1] \sqcup [m, m + n - 2] \times [1, n - 1]) \cap \mathbb Z^2,\]is enough.
First, we can use $m \times n$ rectangles to find the values in the rectangle $([1, m+n-2] \times [m-1]) \cap \mathbb Z^2$. Next, note that the sum conditions imply that in the strip $([1, m+n-2] \times [m]) \cap \mathbb Z^2$, we know the value of $m$ or $n$ consecutive cells. But these are $m+n-2$ linear equations, and we have $m+n-2$ values in the cells, so showing that we can find the values in the cells is equivalent to showing that the linear equations are linearly independent. It suffices to prove the following lemma: Lemma: Suppose $m, n$ are relatively prime positive integers and $a_1, a_2, \dots, a_{m+n-2}$ are complex numbers. If the sum of any $m$ or $n$ consecutive $a_i$ is equal to $0$, then the $a_i$ are all zero.
To finish, we simply apply the lemma a bunch of times vertically upwards and downwards to get the whole of $([1, m + n - 2] \times \mathbb Z) \cap \mathbb Z^2$. Then, apply the lemma right and left to get the entirety of $\mathbb Z^2$. We are done. $\square$ Part 3: If $\gcd(m, n) = 1$, then there exist $(m-1)^2 + (n-1)^2$ linearly independent boards. In other words, the dimension of the vector space is at least $(m-1)^2+(n-1)^2$. Proof: We use the notation $(x, y) \mapsto f(x, y)$ to mean the board that has $f(x, y)$ at $(x, y)$ for each $(x, y) \in \mathbb Z^2$. Let $\omega$ be a primitive $m$th root of unity. First, we claim that \[ V_m = \{ (x, y) \mapsto \omega^{ax + by} \mid 1 \le a, b \le m - 1, \, (a, b) \in \mathbb Z^2 \},\]is a linearly independent set of boards. These are indeed boards since the sum of any $m$ "equally spaced" $m$th roots of unity is $0$. Additionally, mote that by restricting each board to $([0, m-1] \times [0, m-1]) \cap \mathbb Z^2$, we can can represent them as vectors in $\mathbb C^{\oplus m^2}$. We claim that under the standard complex inner product, $\frac1m V_m$ is an orthonormal set. This is not too hard to check. In particular, for any integers $a, b$ such that $1 \le a, b \le m - 1$, \[ \left\| (x, y) \mapsto \omega^{ax + by} \right\|^2 = \sum_{0 \le x, y \le m - 1} 1 = m^2,\]and for any two pairs of integers $(a, b) \ne (c, d)$ such that $1 \le a, b, c, d \le m - 1$, \[ \left\langle (x, y) \mapsto \omega^{ax + by}, (x, y) \mapsto \omega^{cx + dy} \right\rangle = \sum_{0 \le x, y \le m - 1} \omega^{(a-c) x + (b-d) y} = 0.\]It follows that $V_m$ is indeed linearly independent. Finally, define $V_n$ similarly (with a primitive $n$th root of unity). Note that linear combination of $V_m$ is periodic with period $m$ in any row of cells, while any linear combination of $V_n$ is periodic with periodic $n$ in the same row. It follows that if some linear combination of $V_m$ is equal to some linear combination of $V_n$, then every row is equal since $\gcd(m, n) = 1$. Similarly, every column is equal, so the whole grid is equal, i.e. it is all zero. It follows that $V_m \sqcup V_n$ is a set of $(m-1)^2 + (n-1)^2$ linearly independent boards. $\square$ All three parts are complete, so we are done. $\blacksquare$
16.01.2023 20:09
We claim the answer is $(m-1)^2+(n-1)^2$ (or if you're in contest, possibly $(\max(m,n)-1)(m+n-2)-|m-n|(\min(m,n)-1)$) if $\gcd(m,n)=1$, and impossible for Freyja to win otherwise. First, assume $\gcd(m,n)=k>1$. We show that after a finite number of guesses, T can still manipulate a row so that the conditions hold in the grid and Freyja's guesses are unaffected. Suppose all of Freyja's information lies below row $\mathcal R$, and look at the row above that. We increase every $k$th number by $1$ and its cell on the right by $-1$. Note that this clearly doesn't affect any of Freyja's guesses, so we only need to make sure that any $m\times n$ rectangle has a sum of 0. However, this is clear, as if it doesn't contain the modified row, the sum is the same. And if it does, as $k\mid m,n$, there is an equal number of $+1$ and $-1$ operations, so the sum is the same. Thus, since Freyja can never know any information outside of the rectangle surrounding her boxes, she can't win. Now, assume $\gcd(m,n)=1$, and without loss of generality $m>n$ (if $m=n=1$ the answer is clearly $0$). We show the following crucial claim: Claim. The grid is periodic modulo $mn$. Proof. Consider the following configuration of rectangles: [asy][asy] filldraw((0,0)--(5,0)--(5,1)--(0,1)--cycle,0.1*blue+white); filldraw((0,9)--(5,9)--(5,10)--(0,10)--cycle,0.1*red+white); draw((0,0)--(5,0)--(5,10)--(0,10)--cycle); draw((0,1)--(5,1),blue); draw((0,9)--(5,9),red); label("$n$",(2.5,0),S); label("$m-1$",(-2,5)); label("$1$",(-2,0.5)); label("$1$",(-2,9.5)); [/asy][/asy] The red and blue parts are equal in sum, which means the sum of any $m$ cells repeats every $n$ rows. By symmetry, this means the sum of any $m$ consecutive cells is the same every $mn$ rows, or any $n$ consecutive cells. Thus, if we arbitrarily label cells $x_1,x_2,\ldots$ and the ones $mn$ rows above it $y_1,y_2,\ldots$, we have \[x_a+\cdots+x_{a+m-1}=y_a+\cdots+y_{a+m-1}\]\[x_a+\cdots+x_{a+n-1}=y_a+\cdots+y_{a+n-1}\]By Bezout's Lemma, there exists positive $a,b$ such that $am-bn=1$. Thus, \[\begin{aligned}x_1&=(x_1+x_2+\cdots+x_{am})-(x_2+\cdots+x_{bn+1})\\ &=(y_1+y_2+\cdots+y_{am})-(y_2+\cdots+y_{bn+1})\\&=y_1\end{aligned}\]so the tiling is periodic modulo $mn$. Thus, Freyja only has to solve it within a finite grid of $mn\times mn$. Consider the vector space $V$ generated by the equations and variables given in the problem. Note that for some fixed $x_1,\ldots,x_n$, if $n<\dim V$, there are infinitely many ways (or zero) to fill in the rest. Meanwhile, if $n>\dim V$, there exists some $x_1,\ldots,x_n$ such that there is no way to fill in the rest of the variables. Thus, if we can find a construction where for any values put into those cells, we can construct the rest of the grid uniquely, we are done. We claim that knowing an $(m-1)\times (m+n-2)$ rectangle is enough. Note that it suffices to show we can add a row to make it an $m\times (m+n-2)$ rectangle. Note that we have $m+n-2$ new variables, and $m+n-2$ new equations (to add the top row). The equations follows because we have $n-1$ $m\times n$ rectangles and $m-1$ $n\times m$ rectangles that include the top row. It suffices to show that these equations are all linearly independent. However, this is simple. If we have $x$ $m\times n$ rectangles and $y$ $n\times m$ rectangles, we have at least $|mx-ny|$ variables, so if this is $0$, $x=y=0$. Now, the answer is just the number of ways to tile an $(m-1)\times (m+n-2)$ rectangle knowing that any $m\times n$ rectangle sums to $0$. Fortunately, we only have "wide" $n\times m$ rectangles, which are clearly all linearly independent. Thus, we have $(m-n)(n-1)$ equations, so we have \[(m-1)(m+n-2)-(m-n)(n-1)=(m-1)^2+(n-1)^2\]free variables, which as mentioned before is the dimension of the vector space. Thus it is the least guesses Freyja needs.
17.01.2023 05:50
Algebra that is carefully disguised as combinatorics... you can't lie to me. Answer is $(m-1)^2+(n-1)^2$ for coprime $m, n$ and death otherwise. Define $f_a = \begin{cases}1 & x \equiv y \equiv 0 \pmod a \\ 1 & x \equiv y \equiv 1 \pmod a \\ -1 & x \equiv 1 - y \equiv 0 \pmod a \\ -1 & x \equiv 1 - y \equiv 1 \pmod a \\ 0 & \text{else} \end{cases}$ First, proof of death: Simply pick a vertical line sufficiently far to the right and add $f_{gcd(m, n)}$ for all elements to the right of the line to obtain a solution with identical answers for Freyja. Necessity: Notice the solution set is a vector space. Note $f_a$ forms an $a$-periodic solution whose support on $(\mathbb{Z}/a\mathbb{Z})^2$ is a 2 by 2 square. Represent this space as an $a \times a$ square. Now draw that space and select only solutions formed by shifts of $f_a$ whose squares do not wrap around the edge of the square. Notice all these $(a-1)^2$ solutions are thus linearly independent since the only solution that has support in the bottom left square in the support of a vanishing linear combination must have coefficient $0$. Replicating this process for both $m, n$ gives $(m-1)^2+(n-1)^2$ linearly independent solutions, and furthermore you cannot have a linear combination of both $m$-periodic functions and $n$-periodic function equalling $0$ since the only solution which is both $m$-periodic and $n$-periodic is $0$ by coprimality but this violates the observation in the previous paragraph. Thus the dimension of the solution space is at least $(m-1)^2+(n-1)^2$ so Freyja must ask at least that many questions so determine the exact coloring. Sufficiency: Draw a $m-1 \times m - 1$ square aside a $n-1 \times n-1$ square such that one edge overlaps and another pair of edges lie on the same line when extended. It is trivial to observe we can solve a $m-1 \times m+n - 2$ rectangle, with WLOG $m > n$. We simply need to prove we can solve the extended $m \times m + n - 2$ rectangle, since this would allow us to shift and induct to a $m+n - 2 \times m + n - 2$ square, and induction from here to the entire grid is trivial. To prove this, notice we know the sum of every $m$ adjacent and $n$ adjacent elements in the newest row containing $m + n - 2$ elements from drawing all possible boxes that lie in the new row. It suffices to show that following claim: Claim: Given a row of $m + n - 2$ elements such that you know the sum of every set of $m$ adjacent elements and the sum of every set of $n$ adjacent elements and $gcd(m, n) = 1$ and there is at least one solution to the $m + n - 2$ elements, the values of the elements are all uniquely determined. Proof: Strong induction. Interestingly, it's sharp. So we are done.
13.04.2023 03:37
This is an amazing linear algebra problem. The answer is infinity if $\gcd(m,n)>1$ and $(m-1)^2+(n-1)^2$ otherwise. When $\gcd(m,n)>1$, after Freyja asks finitely many questions, Tsvety can focus on the set of rows below the lowest row in which there is a square Freyja asked about, and label $(x,y)$ to be the square on the $x$th row and $y$th column. Observe if Tsvety increases 1 to all squares $(x,y)$ with $\gcd(m,n)\mid x+y$ and decreases 1 to all squares $(x,y)$ where $\gcd(m,n)\mid x+y+1$, the grid follows all rules and remains consistent with Freyja's questions. (In other words, the set of possible grids form an infinite-dimensional vector space) When $\gcd(m,n)=1$ our proof proceeds in two steps. First, we prove that the dimension of the set of possible grids is $(m-1)^2+(n-1)^2$. Then we will exhibit why the answer is equal to that. Let $f\colon \mathbb{Z}^2\to \mathbb{R}$ such that $f(x,y)$ is the number on the $x$th row and $y$th column. Claim 1: $f(x,y) = f(x,y+mn) = f(x+mn,y)$ Proof: Note the for any integers $x,y$ we have $f(x,y) + f(x+1,y) + \cdots + f(x+n-1,y) = -\sum_{j=1}^{m-1} \sum_{k=x}^{x+n-1} f(k,y+j) = f(x,y+m) + f(x+1,y+m) + \cdots + f(x+n-1,y+m) = f(x,y+mn) + f(x+1,y+mn) + \cdots + f(x+n-1,y+mn) $ Similarly, $f(x,y) + f(x+1,y) + \cdots + f(x+m-1,y) = f(x,y+mn) + f(x+1,y+mn) + \cdots + f(x+m-1,y+mn) $ Now, let $a,b$ be positive integers such that $am=bn+1$. Then $$f(x,y) = \sum_{j=x}^{x+am-1} f(j,y) - \sum_{j=x+1}^{x+am-1} f(j,y) = \sum_{j=x}^{x+am-1} f(j,y+mn) - \sum_{j=x+1}^{x+am-1} f(j,y+mn) = f(x,y+mn)$$since $m\mid am$ and $n\mid am-1$. Thus, we change the domain of $f$ so that $f\colon (\mathbb{Z}/mn\mathbb{Z})^2 \to \mathbb{R}$. We divide $(\mathbb{Z}/mn\mathbb{Z})^2$ into $m^2$ squares of side length $n$. Say the sums of the $n\times n$ squares are $S_{j,k}$ where $j,k \in \mathbb{Z}/m\mathbb{Z}$ (where say $S_{j,k} = \sum_{1\le t,l\le m} f(jn+t, kn+l) $) . We know that $\sum_{j=1}^m S_{j,k} = \sum_{k=1}^m S_{j,k}=0$ for all $j,k\in \mathbb{Z}/m\mathbb{Z}$, so the kernel of $(S_{j,k})$ is the vectors $\sum_{j=1}^m S_{j,k} = \sum_{k=1}^m S_{j,k}$, which has dimension $2m-1$ (because the sum of each "row" vector and the sum of "all" column vector is the whole $(\mathbb{Z}/mn\mathbb{Z})^2$ board and there are no other dependencies). Hence the dimension of $(S_{j,k})$ is $m^2 - (2m-1) = (m-1)^2$ Similarly, when we divide $(\mathbb{Z}/mn\mathbb{Z})^2$ into $n^2$ squares of side length $m$ and call the sums $T_{j,k} = \sum_{1\le t,l\le n} f(jm+t, km+l) $, then we can see the dimension of $(T_{j,k})$ is $(n-1)^2$. We now need to show that $(S_{j,k}) \sqcup (T_{j,k})$ is spanning and surjective (or linearly independent) First we show spanning i.e. we can find all entries of the grid knowing $S_{j,k}$ and $T_{j,k}$. First, with the $S_{j,k}$'s, for convenience, we define $G(x,y) = \sum_{j=y}^{y+n-1} f(x,j), H(x,y) = \sum_{j=x}^{x+n-1} f(j,x)$ We first find $G(kn+1,y)$ by noting that $G(kn+1,y)=G(kn+1,y+m)$ and from $\gcd(m,n)=1$, it suffices to find $G(kn+1,ln)$. Recall $am-bn=1$. Note $G(kn+1,ln) = \sum_{j=ln}^{(l+b)n} G(kn+1,j) - \sum_{j=ln+1}^{(l+b)n} G(kn+1,j) = 0 - S_{k,l} - S_{k,l+1} - \cdots - S_{k,l+b-1}$ Similarly, we can also find each $H(x, kn+1)$. From this we can see that we now know the sum of all $n\times n$ squares that are shifted one down from the original $n\times n$ squares, which allows us to find $G(kn+2,y)$ and similarly we can find $H(x,kn+2)$ and we can therefore find all $G(x,y)$ and $H(x,y)$'s. Similarly we can find the sum of any $1\times m$ or $m\times 1$ stick in the square using $T_{j,k}$'s. Combining the sums of $1\times n$ and $n\times 1$ sticks (namely $G(x,y)$ and $H(x,y)$) we can get any cell in the grid. This proves these vectors are spanning. To prove these vectors are linearly independent, it is actually easier to show that these vectors are surjective. Indeed, with any possible starting values, it is possible to fill the whole grid, and two different starting values obviously lead to two different grids. Thus the vector space of solutions has dimension $(m-1)^2 + (n-1)^2$. Let $V$ be our vector space. We can write $V \sim \mathbb{R}^{(mn)^2} / U$ where $U$ is the span of the vector space of all $m\times n$ or $n\times m$ cells. Note $\dim U = (mn)^2 - (m-1)^2 - (n-1)^2$ by rank-nullity. Now, suppose that Freyja asks fewer than $(m-1)^2 + (n-1)^2$ questions, say she asked squares $c_1,\cdots,c_t$. Then Freyja knows that all the cells of the grid is in an affine subspace of the form $v_1 + \mathbb{R}^{(mn)^2} / (span(c_1,\cdots,c_t) + U)$, which is not an affine subspace with one point because its dimension is $\ge (mn)^2 - \dim U - t \ge 1$. Hence Freyja does not know all the cells of the grid. Now suppose no matter how Freyja asks $(m-1)^2+(n-1)^2$ questions, she cannot find all cells of the grid. This implies that any set of $(m-1)^2+(n-1)^2$ cell vectors is linearly dependent with $U$. We can induct to show that $span (c_1, \cdots, c_K) + U$ is a vector space of dimension at most $(mn)^2-1$ for any $K\ge (m-1)^2+(n-1)^2$. This is a contradiction when $K=(mn)^2$ since the $(mn)^2$ cells are obviously linearly independent.
30.07.2023 06:39
If \(\gcd(m,n)\ne1\), Freyja cannot win. If \(\gcd(m,n)=1\), Freyja can win in \((m-1)^2+(n-1)^2\) queries. Proof of impossibility: Assume \(d=\gcd(m,n)>1\). We show Freyja must query a cell from each row. It follows that Freyja cannot win in finite moves since there are infinitely many rows. Suppose Freyja has not queried row \(r\), and is somehow able to uniquely determine the grid. If this unique solution has \(x_{ij}\) in row \(i\) and column \(j\), consider the grid \((y_{ij})\) in which \[y_{ij}= \begin{cases} x_{ij}+1\quad\text{if }i=r\text{ and }j\equiv 0\pmod d\\ x_{ij}-1\quad\text{if }i=r\text{ and }j\equiv 1\pmod d\\ x_{ij}\quad\text{else.} \end{cases}\]Since each \(d\times d\) square in \((y_{ij})\) either does not intersect row \(i\) or intersects it at \(d\) contiguous \(j\)-coordinates, the sum of the cells in each \(d\times d\) square of \((y_{ij})\) equals the sum of the cells in the corresponding \(d\times d\) square in \((x_{ij})\). Since each \(m\times n\) rectangle is tiled by \(d\times d\) squares, this implies \((x_{ij})\) and \((y_{ij})\) are not distinguishable. Henceforth \(\gcd(m,n)=1\). We prove \((m-1)^2+(n-1)^2\) is optimal. Proof of necessity: Let \(V\) denote the vector space of grids satisfying the condition that each \(m\times n\) and \(n\times n\) rectangle sums to 0. (Addition in \(V\) is cell-wise.) Consider the \((m-1)^2\) grids \(M_{uv}\) for \(1\le u,v\le m-1\) where the entry in cell \((i,j)\) of \(M_{uv}\) is \[(M_{uv})_{ij}= \begin{cases} -1&\text{if }(i,j)\equiv(u,v)\pmod m\\ +1&\text{if }(i,j)\equiv(u+1,v)\pmod m\\ +1&\text{if }(i,j)\equiv(u,v+1)\pmod m\\ -1&\text{if }(i,j)\equiv(u+1,v+1)\pmod m. \end{cases}\]By definition, \(M_{uv}\) is periodic mod \(m\) (meaning \((M_{uv})_{ij}=(M_{uv})_{i+m,j}=(M_{uv})_{i,j+m}\) for all \((i,j)\).) Moreover, every \(1\times m\) rectangle of \(M_{uv}\) has sum 0, so every \(m\times n\) rectangle has sum 0. Analogously each \(n\times m\) rectangle has sum 0, so \(M_{uv}\in V\). Similarly define the \((n-1)^2\) grids \(N_{uv}\in V\) for \(1\le u,v\le n-1\), which are periodic modulo \(n\). Claim: \(\{M_{uv}\}\) are linearly independent. Proof. Let \(\sum c_{ij}M_{ij}=0\). We show by strong induction on \((i,j)\), \(1\le i,j\le m-1\), that \(c_{ij}=0\). The base case is null. If \(c_{ij}=0\) for all \(i'\le i\) and \(j'\le j\) yet \((i',j')\ne(i,j)\), we observe that the cell \((i,j)\) is affected only by \(M_{i-1,j-1}\), \(M_{i-1,j}\), \(M_{i,j-1}\), \(M_{ij}\) (if they exist). By the inductive hypothesis, \(c_{i-1,j-1}\), \(c_{i-1,j}\), \(c_{i,j-1}\) are all zero (or don't exist), so \(c_{ij}\) must be zero. \(\blacksquare\) Similarly \(\{N_{uv}\}\) are linearly independent. Claim: The \((m-1)^2+(n-1)^2\) grids \(\{M_{uv}\}\sqcup\{N_{uv}\}\) are linearly independent. Proof. Let \(\overline M=\sum c_{ij}M_{ij}\) and \(\overline N=\sum d_{ij}N_{ij}\) with \(\overline M+\overline N=0\). It suffices to show \(\overline M=\overline N=0\). Since \(\{M_{uv}\}\) are all periodic modulo \(m\), so is \(\overline M\); simliarly \(\overline N\) is periodic modulo \(n\). Thenfor all \(0\le i_1,j_1\le m-1\) and \(0\le i_2,j_2\le n-1\), since \(\gcd(m,n)=1\) there exist \(\overline i\) and \(\overline j\) by Chinese remainder theorem with \begin{align*} (\overline i,\overline j)&=(i_1,j_1)\pmod m\\ (\overline i,\overline j)&=(i_2,j_2)\pmod n, \end{align*}so cell \((\overline i,\overline j)\) of \(\overline M+\overline N=0\) is \(\overline M_{i_1,j_1}+\overline N_{i_2,j_2}\). Thus \(\overline M_{i_1,j_1}+\overline N_{i_2,j_2}=0\) for all \(i_1\), \(j_1\), \(i_2\), \(j_2\), so the cells of \(\overline M\) are all equal (say, to \(-\overline N_{0,0}\)) and the cells of \(\overline N\) are all equal. Howver, for all \(u\), \(v\), \[\sum_{i=1}^m\sum_{j=1}^m(M_{uv})_{ij}=0,\]implying \[\sum_{i=1}^m\sum_{j=1}^m\overline M_{ij}=0,\]so \(\overline M=0\), and analogously \(\overline N=0\). \(\blacksquare\) Now suppose Freyja picks fewer than \((m-1)^2+(n-1)^2\) cells \(x_1\), \(\ldots\), \(x_r\) to query, and suppose Tsvety says they are all 0. Since \(r<(m-1)^2+(n-1)^2\), there is a nontrivial solution to the linear system \[\sum c_{ij}M_{ij}+\sum d_{ij}N_{ij}=G,\]where cell \(x_k\) of \(G\) is zero for all \(k=1,\ldots,r\). Since \(\{M_{ij}\}\sqcup\{N_{ij}\}\) is linearly independent, \(G\ne0\), and Freyja cannot distinguish 0 and \(G\). Proof of sufficiency: Without loss of generality \(m>n\). We show Freyja can query the following cells and determine the grid: [asy][asy] size(6cm); defaultpen(fontsize(10pt)); real m=3,n=2; draw( (0,0)--(m,0)--(m,m)--(0,m)--cycle); draw( (m,0)--(m+n,0)--(m+n,n)--(m,n)--cycle); label("\(m-1\)",(0,0)--(0,m),W); label("\(m-1\)",(0,0)--(m,0),S); label("\(n-1\)",(m,0)--(m+n,0),S); label("\(n-1\)",(m+n,0)--(m+n,n),E); [/asy][/asy] By picking \(m\times n\) rectangles with the desired cell as the top-right corner (in the order bottom-left to top-right), Freyja may compute all the cells in the top-right corner of the above diagram, thus determining all the cells in a rectangle of size \((m-1)\times(m+n-2)\). Claim: If \(\gcd(m,n)=1\) and \(u\ge m+n-2\), there is at most one solution to the system \begin{align*} x_1+\cdots+x_m&=a_1\\ x_2+\cdots+x_{m+1}&=a_2\\ &\;\vdots\\ x_{u-m+1}+\cdots+x_u&=a_{u-m+1}\\ x_1+\cdots+x_n&=b_1\\ &\;\vdots\\ x_{u-n+1}+\cdots+x_u&=b_{u-n+1}. \end{align*} Proof. If there are two solutions, their difference satisfies \begin{align*} x_1+\cdots+x_m&=0\\ x_2+\cdots+x_{m+1}&=0\\ &\;\vdots\\ x_{u-m+1}+\cdots+x_u&=0\\ x_1+\cdots+x_n&=0\\ &\;\vdots\\ x_{u-n+1}+\cdots+x_u&=0. \end{align*}We show all \(x_i=0\) by strong induction on \(m+n\), with base case \(1\in\{m,n\}\) (by Euclidean algorithm) obvious. Without loss of generality \(m>n\). Then for eaceh \(i=0,\ldots,u-m\), \begin{align*} x_{i+1}+\cdots+x_{i+(m-n)} &=(x_{i+1}+\cdots+x_{i+m})-(x_{i+m-n+1}+\cdots+x_{i+m})\\ &=0. \end{align*}By the inductive hypothesis on \((n,m-n)\) (and \(u\mapsto u-n\ge n+(m-n)-2\)), we have \(x_i=0\) for \(i\le u-n\), and the quations \(_{u-2n+2}+\cdots+x_{u-n+1}=0\), etc., give \(x_i=0\) for all \(i\). \(\blacksquare\) Claim: Suppose Freyja knows all the cells in a \(u\times v\) rectangle with \(u\ge m+n-2\) and \(v\ge m-1\). Then she may determine all the cells in the \(u\times 1\) rectangle directly on top of the \(u\times v\) rectangle. [asy][asy] size(4cm); defaultpen(fontsize(10pt)); real u=10,v=5; draw( (0,0)--(u,0)--(u,v)--(0,v)--cycle); draw( (0,v)--(0,v+1)--(u,v+1)--(u,v)); label("\(v\)",(0,0)--(0,v),W); label("\(1\)",(0,v)--(0,v+1),W); label("\(u\)",(0,v+1)--(u,v+1),N); [/asy][/asy] Proof. Let the numbers in the top row be \(x_1\), \(\ldots\), \(x_u\). By examining \(m\times n\) and \(n\times m\) rectangles with \(x_i\) in the top row, we may evaluate \begin{align*} x_1+\cdots+x_m,&\\ \vdots&\\ x_{u-m+1}+\cdots+x_u,&\\ x_1+\cdots+x_n&,\\ \vdots&\\ x_{u-n+1}+\cdots+x_u.& \end{align*}By the lemma, we may uniquely determine \(x_1\), \(\ldots\), \(x_u\) from here. \(\blacksquare\) Hence, Freyja may expand her \((m+n-2)\times(m-1)\) rectangle to a \((m-n+2)\times(m-n+2)\) square, and from there, expand it arbitrarily to determine each cell in the grid. This completes the proof.
25.08.2023 02:45
I can't spell Tsvety correctly. Concerning solution that has a USAMO 2021/3-esque component. Note that valid assigning of cells form a vector space. Claim: If $\gcd(m, n) > 1$, then it is impossible for Freyja to win. Proof. Note that this can be strengthened to $m = n$. We now show that after a finite number of reveals, it's impossible for Freyja to determine the entire grid. Take the bounding box of all revealed squares such that it has dimensions at least $n \times n$, and fill it all with $0$. Now only consider the equations that concern the squares directly above the current box. We can assign numbers to the above boxes in a nonzero manner due to having less equations then unknowns. By transfinite inducting on all side lengths, we end up with an infinite non-trivial coloring that is $0$ on all $n \times n$ square. Thus, Freyja can't be sure if the remaining cells are all $0$ or this nontrivial coloring. $\blacksquare$ Claim: If $\gcd(m, n) = 1$, then Freyja can win in $(m-1)^2 + (n-1)^2$ moves. Proof. WLOG assume that $m > n$. Take a $(m + n - 2) \times (m + n - 2)$ grid, with a $(m - 1) \times (m - 1)$ and $(n - 1) \times (n - 1)$ square revealed. There are both $2(m-1)(n-1)$ unknowns and equations. It remains to show that the $m \times n$ and $n \times m$ equations are linearly independent. This is equivalent to showing that there are no polynomial solutions to \[ P(x, y) (1 + x + \dots + x^{n-1})(1 + y + \dots + y^{m-1}) = Q(x, y) (1 + x + \dots + x^{m-1})(1 + y + \dots + y^{n-1}) \]where $\deg P, \deg Q < n + m - 4$ which follows since $\gcd(n, m) = 1$. $\blacksquare$ Claim: The dimension of the valid cell vector space for $\gcd(m, n) = 1$ is at least $(m-1)^2 + (n-1)^2$. Proof. Take coordinates. Consider the $(m-1)^2$ placements of the matrix \[ \begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix} \]in a $m \times m$ square which is then duplicated $\pmod{m}$. Note that each of these assignings satisfy the propety of summing to $0$ on rectangles. Furthermore, they are invariant under translating $m$. Do the same for $n$. Now consider a linear combination of these $(m-1)^2 + (n-1)^2$ colorings. We claim that we can recover the coefficients from the linear combination. Let $M + N$ be a coloring where $M$ refers to the $(m-1)^2$ valid assignments and similarily. By considering the $n^2$ values at $(im, jm)$ for $1 \le i, j \le n$, on which $N$ is invariant, we can fully recover the differences between $N$, and thus recover $N$. Then, using the bottom left corner, we can repeatedly derive coefficients until all of the coefficients in $N$ are known. The same can be done for $M$. $\blacksquare$
29.11.2023 18:17
Nice exercise in infinite-dimensional linear algebra and classical algebraic geometry. We claim the answer is $(m-1)^2+(n-1)^2$ if $\gcd(m,n)=1$ and impossible otherwise. First, observe that if $\gcd(m,n)\ne 1$ and we only know a finite number of cells, if $d>1$ is a common divisor of $m$ and $n$, then we can add to a row with no cells known the row that has $[1,0,\dots,0,-1]$ repeated (where there are $d$ numbers in this repeated bit) and the sum conditions are still satisfied, so we cannot know this row exactly and therefore Freyja cannot win. Otherwise, let $\gcd(m,n)=1$. Now, observe that the set of grid numberings forms a vector space. Consider the vector space of (finite) weighted sums (meaning linear combinations) with complex coefficients of components of the solution Tsvety has in mind (we will represent these as the numberings corresponding to their coefficients). Observe that at any time, the set of these sums for which Freyja knows the value forms a vector subspace. Now, this subspace starts as that generated by $m$ by $n$ and $n$ by $m$ rectangles of $1$'s (with $0$'s in the rest of the grid outside of the rectangle). Each question adds to this vector space a vector of the form a $1$ in the asked square and a $0$ everywhere else.* Now, we quotient out be the original vector space of sums that Freyja knows the value of, call the resulting vector space $V$ and observe then that each question adds at most one dimension to the subspace of $V$ of sums for which Freyja knows the value, and we can insist that it strictly increase the subspace (and thus add exactly one dimension to it) by having Freyja ask about a square that would give Freyja new information (if this were not possible then Freyja would know all squares and would have already won), so the number of questions Freyja needs is equal to the dimension of $V$. Now for any positive integer $a$, let $f_{a}(x)=1+x+\cdots+x^{a-1}$. Observe that $f_a(x)$ has roots at each $a$th root of unity besides $1$, for $a-1$ roots total. In particular, $f_m(x)$ and $f_n(x)$ share no roots as $\gcd(m,n)=1$. To each cell $(a,b)$, assign the monomial $x^ay^b$. Now, we represent each weighted sum by their generating function where the coefficients on $(a,b)$ become coefficients on $x^ay^b$. Let the ring of these polynomials, that is $\mathbb C[x,y,\frac1x,\frac1y]$ be denoted as $R$. Observe that what we are quotienting out by is actually the ideal $(f_a(x)f_b(y))+(f_b(x)f_a(y))$. Let the first term be the ideal $I$ and the second be $J$. We want to find the dimension of $R/(I+J)$. We claim that if we consider the subring of $R$, call it $R'$, that is $\mathbb C[x,y]$, then $R'/(R'\cup(I+J))$ is the same ring as $R/(I+J)$, where we consider the former a subring of the latter by mapping $R'$ to $R$ through the inclusion map and then to $R/(I+J)$ through the quotient map, and note the kernel of this map is $R'\cup(I+J)$ so we get the desired inclusion map. This is because the latter ring is the former ring adjoin $\frac{1}{x}$ and $\frac1{y}$, but these already exist in the former ring assuming it is finite dimensional of $\mathbb R$, so if we prove that $R'/(R'\cup(I+J))$ has the desired finite dimension then we will be done. Let $I'$ and $J'$ be defined to be the intersections of $I$ and $J$ respectively with $R'$. Consider $R'$ as the coordinate ring of $\mathbf A^2$. Now observe that by strong Nullstellensatz $\sqrt{I'+J'}$ is the ideal corresponding to $Z(I')\cap Z(J')$. Now observe $I'$ and $J'$ are $(f_a(x)f_b(y))$ and $(f_b(x)f_a(y))$ respectively; these are both radical ideals and hence the ideals corresponding to their respective zero sets, which are each unions of perpendicular and horizontal lines. Now observe that the intersection of those two zero sets is a finite set of points, none of which have multiplicity more than $1$ as locally all intersections look like the intersection of two perpendicular lines. Hence $\sqrt{I'+J'}=I'+J'$ is in fact the corresponding ideal to the intersection, and to find the dimension of $R$ quotiented by this ideal, we just need to count the points of intersection of the two zero sets. Observe that $Z(I)$ is union of horizontal lines with vertical coordinates at the roots of $f_b(t)=0$ (of which there are $b-1$) and vertical lines with horizontal coordinates at the roots of $f_a(t)=0$ (of which there are $(a-1)$), and $Z(J)$ is almost the same except the coordinate sets are flipped. Now, each point in the intersection must be in a horizontal line of one set and a vertical line of the other. If the horizontal line comes from $Z(J)$ and the vertical from $Z(I)$, there are $a-1$ choices for each line for a total of $(a-1)^2$ points, and similarly we get $(b-1)^2$ points in the other case for a total of $(a-1)^2+(b-1)^2$ points in the intersection, as desired. *This actually requires some explanation and justification: by "adds the vector to the vector space" I mean take the vector space generated by the previous vector space and the "added" vector. Now, to prove this also is nontrivial: obviously the vector space must be at least this but we have to prove that Freyja doesn't somehow gain unexpected information that could not be obtained by simple deductions in the form of vector operations. To see this, observe that it suffices to prove that if the claimed new vector space is known to Freyja, this does not imply any other extra sums must be known (because knowing all sums in this vector space is necessary and sufficient to conclude all of the knowledge that Freyja has). Then to prove that, fix a sum outside of the vector space, shift all numberings of the plane so that the secret numbering is $0$, observe that now the possible secret numberings based on Freyja's current information form a vector space, and we want to prove that not all vectors are in the kernel of our fixed sum. We change the basis of the sums from the canonical basis to a basis in which a set of basis elements forms a basis for the sums Freyja knows to evaluate to $0$ and a basis element outside this set is the fixed sum we want to evaluate to nonzero. Now, we insist that each element of the basis except the fixed sum evaluates to $0$ and the fixed sum evaluates to $1$; now do a change of basis back to get what the canonical basis evaluates to and use this to get the components of a numbering. By properties of change of basis, this numbering has the properties we want, and thus we are done.
27.12.2023 20:30
I think a majority of the time I spent on this was on lower bounding the dimension. Oops. The answer is $(m-1)^2+(n-1)^2$ if $\gcd(m,n)=1$, and otherwise Freyja cannot win. If $\gcd(m,n)=d>1$, then any labeling where any row is $d-1,\underbrace{-1,\ldots,-1}_{d-1\text{ times}}$ repeated works, so at any point it could be the case that all chosen squares could be $0$, and some faraway row looks like this, but Freyja will never be able to know for sure. Now suppose $\gcd(m,n)=1$. We are simply being asked to find the dimension of the set of all grids interpreted as a $\mathbb{R}$-vector space in the obvious way. To prove that this is at least $(m-1)^2+(n-1)^2$, note that the dimension of $m$-periodic labelings is $(m-1)^2$, since they are uniquely determined by the values in an $(m-1) \times (m-1)$ square, and the dimension of $n$-periodic labelings is similarly $(n-1)^2$. Furthermore, since $\gcd(m,n)=1$, by Bezout the only labeling that's both $m$-periodic and $n$-periodic is the coloring that's identically $0$, so we get $(m-1)^2+(n-1)^2$ linearly independent labelings as desired. To prove that this is at most $(m-1)^2+(n-1)^2$, WLOG let $m>n$ ($m=n=1$ is trivial). Consider an $(m-1) \times (m-1)$ square and a nonoverlapping $(n-1) \times (n-1)$ square which share a horizontal edge and vertical edge. I claim that knowing the values in these cells is enough for Freyja to win. We can first use $m \times n$ rectangles ($m$ wide, $n$ tall) to find the values in an $(m+n-2) \times (m-1)$ rectangle. Claim: Let $x_1,\ldots,x_{m+n-2}$ be real numbers. Suppose that we know the sum of any $m$ consecutive $x_i$, as well as the sum of any $n$ consecutive $x_i$. Then we can uniquely determine $(x_1,\ldots,x_{m+n-2})$. Proof 1: It suffices to show that the $n-1$ vectors in $\mathbb{R}^{m+n-2}$ with $m$ consecutive ones and the rest zeroes, as well as the $m-1$ vectors with $n$ consecutive ones and the rest zeroes, are linearly independent. We associate a vector $(a_1,\ldots,a_{m+n-2})$ with the polynomial $$a_1x^{m+n-3}+a_2x^{m+n-4}+\cdots+a_{m+n-3}x+a_{m+n-2},$$so we have $n-1$ polynomials of the from $x^a(x^{m-1}+\cdots+1)$ where $a \leq n-2$, and $m-1$ polynomials of the form $x^b(x^{n-1}+\cdots+1)$ where $b \leq m-2$. If these vectors are not linearly independent, then there exist nonzero polynomials $P,Q \in \mathbb{R}[x]$ with $\deg P \leq n-2$, $\deg Q \leq m-2$, and $$P(x)(x^{m-1}+\cdots+1)=Q(x)(x^{n-1}+\cdots+1).$$If we plug in an $n$-th root of unity other than $1$, the RHS vanishes, so the LHS should as well. But $x^{m-1}+\cdots+1$ won't vanish since $\gcd(m,n)=1$, so $P$ has $n-1$ roots and hence must be identically zero: contradiction. $\blacksquare$ Proof 2: We induct on $m+n$ given that $\gcd(m,n)=1$; with the trivial cases of $\min(m,n)=1$ being trivial. Now assume $m>n \geq 2$. With our given information, by subtraction we can find the sum of any $m-n$ consecutive $x_i$ among the first $m-2$. Since we can still find the sum of any $n$ consecutive $x_i$ among the first $m-2$ and $\gcd(m-n,n)=\gcd(m,n)=1$, it follows by hypothesis that we can determine the values of $x_1,\ldots,x_{m-2}$. Since $n \leq m-1$, we can then use the fact that we know the sum of $x_{m-1}+\cdots+x_{m-n}$ to find $x_{m-1}$, and repeating this will give us the values of $x_1,\ldots,x_{m+n-2}$ as desired. $\blacksquare$ Now, given our $(m+n-2) \times (m-1)$ rectangle, we are now able to find all of the values in the $(m+n-2) \times 1$ rectangle directly above it, expanding our known values to that of an $(m+n-2) \times m$ rectangle. Repeating this gives us the entire width-$(m+n-2)$ vertical "strip" of values. This strip now contains $(m-1) \times (m+n-2)$ rectangles everywhere, so we can find a height-$(m+n-2)$ horizontal "strip" of values at any height, giving us the entire grid as desired. $\blacksquare$
29.12.2023 05:08
Commentary (not by me, communicated by someone else): Once you've shown periodicity, you can define the rectangle indicator functions $r_{m,n}$ and $r_{n,m}$ for rectangles. Then if $f$ gives the output as chosen by Tsvety, then it follows that $f \star r_{m,n} = f \star r_{n,m} = 0$ where $\star$ is convolution. Then by the Convolution theorem taking a DFT in both dimensions gives that $\hat{f} \cdot \hat{r}_{m,n} = \hat{f} \cdot \hat{r}_{n,m} = 0$, which expands as the \[ \widehat{f}(\omega^a, \omega^b) \cdot \frac{\omega^{am} - 1}{\omega^a - 1} \cdot \frac{\omega^{bn} - 1}{\omega^b - 1} = \widehat{f}(\omega^a, \omega^b) \cdot \frac{\omega^{an} - 1}{\omega^a - 1} \cdot \frac{\omega^{bm} - 1}{\omega^b - 1} \]condition again.