20-Questions on a grid

Question

^{Posted this on /r/puzzles too, none have given the right strategy as of now :)}

There is a square grid of width and height $m$. Three facts about the grid:

1. Each cell has a value, and no two cells have the same value.

2. Each row and column is either ascending or descending.

3. $1 \le m \le 1000$

You have to find some value v in the grid, (or see if it exists in the grid or not). What you can do: Ask an oracle for the value in a particular cell. But you can only ask a maximum of $4\times m$ questions to the oracle. What's your strategy?

For an easier version, try to solve it with around $m. \log(m)$ questions.

Best of luck!

^{Also, $4\times m$ doesn't necessarily mean that the puzzle can be solved in $4\times m$ questions for all $m > 1000$ ;)}

PS: Row $i$ can be ascending, row $j$ can be descending, column $a$ can be ascending, $b$ can be descending etc, the entire grid isn't sorted, the rows and columns have their individual sorting.

Answer 1

Partial answer (the idea to solve it by $O(M~log(M))$):

You may try to find the value independently for each row (or column). What you have to do is to use Binary Search Algorithm -- like to find a word in a dictionary -- on each row.

Answer 2

Edit: There's a flaw in the answer below as pointed out in the comments, I will leave this here because some ideas might help other people (then again, maybe I'm on the wrong way)

I think the following strategy works, might be slightly off with roundings, but would probably be ok for m a power of 2:

First, query all the elements on both diagonals. This takes $2m$ queries, and is the fastest way to determine all the ordering in each row/column.
This restricts the value you're looking for in at most one of the 4 triangular quadrants defined by the 2 diagonals: up/left/right/bottom.
You're left with $2m$ queries and have to search in a triangle of basis $m-2$, and height $(m-2)/2$.
Then, we finish by an easy induction / binary search. We can cut the triangle in half with $(m-2)/2$, and have a rectangle triangle that you can cut with only $(m-2)/4$ queries. Then you're left with a triangle that is identical, but $4$ times smaller than the previous one, and repeat.
The cost in query of this induction is thus $\sum_i (m-2)/2^i$, which is less than $2m$

Answer 3

I show a solution for

$m \in \{5,6\}$, that is the smallest $m$s where allowed number of questions ($4\times m$) is less than the number of cells.

First,

query the $2\times m$ cells on the main diagonal and another 'parallel' translated diagonal which starts in the $\lceil\frac{m+2}2\rceil$th column, so the queried diagonals are as far from each other as possible. This way, we will have 2 queried cells in each row, and the rest of the $m-2$ cells in the row are divided into 2 or 3 groups, where the largest group's size is $\lceil\frac{m-2}2\rceil$. As $m\le6$, $\lceil\frac{m-2}2\rceil\le2$, so even if we have to check all the $\lceil\frac{m-2}2\rceil$ cells in each of the $m$ rows, we don't exceed the limitation of $4\times m$ questions.

Please notice that

the restriction for the columns wasn't even utilised, and that the strategy wasn't really adaptive: which values to ask from the oracle wasn't depending on the previous answer for the first $2\times m$ cells at all. I have the intuition, that in a typical case the monotonity criteria coming from the columns gives another factor of $\frac12$ on the size of the groups, so $m\le10$ can be solved.

Answer 4

The General Answer

First of all, we need to consider odd dimension grids and even dimension grids separately. Because their solution is close but separate.

Let's start with odd dimension one: 5x5

This is

The first numbers you need to ask for, because you would know the biggest and the smallest value in the grid. Even cells are easier in my option.

Then

you may even be able to eliminate some cells which would not be having the number you are looking for. But if you are unlucky, you may not if our number is in between all those values. For example, if $A=100$, $B=1$, $C=12$ and $D=50$, and the number you are looking for $27$, you will not able to eliminate any cell for this moment.

Let's guess

other corner values in the inner square

shown below:

This is better guess because you will able to eliminate some cells for sure now because

If our number is in between E-F you will able to eliminate first and last cells on the second column, if our number is greater/smaller than F and smaller/greater than E, we can eliminate two cells. So whatever our number is, we can eliminate two cells from the grid. For example let's say our number is $27$, $E$ is 20 and $F$ is $10$, then you can eliminate two cells etc. Likewise, we can eliminate two more cells from the second row which is not common with the column, (I will call it E-H column) Likewise on the H-G column and F-G row, we can eliminate another 4 cells whatever number we have!

So ,

So for example, one of the worst case is

Note that the red cells are the cells where our number cannot be there.

So only asking 4 more cells shown below, will eliminate another 4 cells with

the same logic above, asking for I,K,L,J will guarantee that 2 white cells left:

So

in total for 5x5, 15 cell asking guarantee to find or not your number exists. This is optimal solution for 5x5! Even if you asked for every white cells left, it would be sufficient for $4m$,

Here is why:

In general You need to ask diagonal values first, then eliminate all cells when possible, then ask for cells not to next to each other in a row or column, and eliminate accordingly. When the dimension increases, elimination number of cell you can eliminate is getting bigger, for example for 5x5, you can eliminate $8$ cells in this process, but for 7x7, you can eliminate $8+16$ cells in total.

In general, you can eliminate

$4\left (\frac{m-1}{2}-1 \right )\left (\frac{m-1}{2}\right )=m^2-4m+3$

so you asked for

$2(m-1)$ cells,

and

eliminated $m^2-4m+3$ out of $m^2$ cells

and white cell count becomes

$m^2-(m^2-4m+3)-(2m-2)=2m-1$

so we asked for

$2m-2$ and $2m-1$ cells left. If we ask all cells one by one, $4m-3$ cells would be asked which is smaller than $4m$.

As shown below (11x11):

And for the rest of while cells,

$2(m-1)$ diagonal cell asking + even you dont have to, asking the rest of while cells which is $2m-1$ is sufficient to have smaller than $4m$. For your information, asking all white cells left is not optimal, but as I said it is sufficient to have less than $4m$.