Searching on a chess board

Alice fills each cell of an $n \times n$ chess board with real numbers, such that there is exactly one zero somewhere on that board. The rest of the cells could be filled with positive or negative numbers, so that all numbers are distinct. Furthermore, she filled it such that each row is sorted from left to right and each column is sorted from top to bottom.

Now she asks Bob to find the location of the zero via a guessing game. Bob is told about the sortedness of the board and that all numbers are distinct, but he doesn't know the numbers themselves. He is allowed to make a series of guesses (of locations), and after each guess, he would be told the number on that cell. The game ends when Bob discovers the zero.

Show that Bob can devise a strategy that guarantees discovery after $2n-1$ guesses.

Show that there is no strategy that guarantees discovery with less than $2n-1$ guesses.

Solution to First Problem

Let cell $(i,j)$ refers to the cell on the $i$-th row and $j$-th column, with $i,j \geq 1$ (usual matrix notation, NOT the usual computer science notation). Bob can follow the following algorithm:

First start by guessing $(n,1)$. If that number is positive, go up 1 cell, and if it's negative, go right one cell.

In order to show that this strategy works, we have to prove three things: termination, correctness, and running time.

Proof of termination and running time

If $(i,j)$ represents the cell of our last guess, let $S = i-j$. Note that in the beginning, $S = n-1$. And for each move, whether that's 1 up or 1 right, $S$ decreases by one. Also that the minimum number of $S$ is attained when $i$ is minimum and $j$ is maximum, namely on cell $(1,n)$, which means $S = 1-n$. That means that after $(n-1)-(1-n)+1 = 2n-1$ moves we are guaranteed to terminate.

Proof of correctness

Let $A$ be the event that we guessed the column (but not necessarily the row) of the zero correctly, and $B$ denotes the event that we guessed the row of the zero correctly. It's easy to see that after $A$ or $B$ is reached, we are guaranteed to reach the zero. For example, once $A$ happens, our guess will keep moving up until it reaches the zero, and vice versa.

Now to show that $A$ or $B$ is ever reached, suppose the zero is at a location $(i_0, j_0)$. That means $A$ happens after $(i_0-1)$ right moves, and $B$ happens after $(n-j_0)$ up moves. Every move is either a right move or an up move, so after many enough moves, either $A$ or $B$ will happen.

Solution to Second Problem

Define the "major" diagonal to be cells $(i,j)$ such that $i+j = n+1$. That is, bottom left to top right. Define the "minor" diagonal to be cells $(i,j)$ such that $i+j = n$. That is, cells above (or to the left of) major diagonal. Now suppose Alice populates the board in the following way: populate everything above the minor diagonal with numbers less than -1, and populate everything below major diagonal with numbers > 1, all while still satisfying the sortedness criteria.

As for the diagonals themselves, note that if the major diagonal is populated with numbers between 0 and 1, and the minor diagonal populated with numbers between -1 and 0, and if the zero is anywhere on the two diagonals, the sortedness criteria is still satisfied. Between cells in the major diagonals themselves (say $(n,1)$ versus $(n-1,2)$) there is no constraint, and likewise there is no constraint between cells in the minor diagonals.

Now suppose Alice never decides on the content of the major and minor diagonals until Bob asks for the content of those cells. In other words, even Alice herself doesn't know where the zero will be. As Bob executes his strategy, if he asks for a cell on the major diagonal, Alice just generates a random number between zero and one. If he asks for a cell on the minor diagonal, she generates a random number between -1 and zero. Note that at any given point, even if Bob knows the content of all the other non-diagonal cells, these numbers are still consistent with the sortedness of the board.

Alice reveals zero only after all the other diagonal cells are exhausted. In other words, Alice only reveals zero if that is the last diagonal cell (major or minor) that Bob hasn't asked. Because there are $2n-1$ diagonal cells, any strategy that Bob has can never guarantee discovery with less than $2n-1$ guesses.