Knight and Knaves Castle

Question

I was pretty bored in the lockdown so I thought up a mathematics puzzle, which I haven's solved yet, so the community can solve together.

Let $n>1$ be a positive integer. There is a square castle with $n^2$ rooms, $n$ columns and $n$ rows. Each room lives a knight or a knave. Knights always tell the truth and knaves always lie. You are required to choose a room, then specify a non-empty proper subset $S$ of $\{0,1,2,...,n\}$, choose an integer $1\le i\le n$, then ask the person living in the room,

“Is the number of knights in row/column $i$ an element of $S$?"

Find the optimal number of questions to be asked to determine all the knights and knaves in the castle in the worst case.

I will also work on this question, and sometimes give progress. You can use a computer. Hope this problem can be solved in a month!

PS: Wow, this is solved in one day! Originally I thought this should need a week.

Answer 1

Here's an optimal procedure that lets you find out the status of every person after exactly

$n^2$

questions:

Ask everyone "Are there exactly $0$ or $n$ knights in row $1$?"

Reasoning:

Let's ask those in row $1$ first. If you get $n$ times "yes", they're all knights. If you get $n$ times "no", they're all knaves. Otherwise, everyone who answers "yes" is a knave and everyone else is a knight.

Next, ask everyone else. You already know the answer by now, so you can tell whether they're knights and knaves too.

Proof of optimality:

Suppose there was a strategy to complete with fewer than $n^2$ questions. Then for any arrangement of knights and knaves, if you list your answers, you'll get a list of fewer than $n^2$ yes/no answers. Unfortunately there are fewer than $2^{n^2}$ such lists, but $2^{n^2}$ possible arrangements of knights and knaves, so by the pigeonhole principle there are going to be two arrangements you can't distinguish.

Answer 2

A better upper bound is

$n^2 + \mathrm{ceil} \log_2(n+1)$

Solution:

Pick any room, row 1 column 1 for example. Let $k=\mathrm{ceil} \log_2(n+1)$, and ask $k$ questions to the inhabitant of the following form:
- Is the number of knights in row 1 an integer having $i$-th bit = 1 when written in binary (of course, constructing a subset of such numbers in $\{0, 1, \dots, n\}$)?
(Of course, due to our choice of $k$ all such subsets will be proper and nonempty.)
So, after doing such "binary search", we can narrow down the number of knights in row 1 to a single integer $Q$. If our inhabitant is a knight, this number is indeed $Q$, but if she/he is a knave, this number should be $2^k-1-Q$ (because the inhabitant lied all the times, so all her/his answers should be inverted). So, now we have a question with a known answer (this is an important part).
Now the remaining part is to ask each and every inhabitant (in all rooms) the same question:
- Is the number of knights in row 1 in the set $\{Q, 2^k-1-Q\}$?
Since we know that it is definitely true, so we can determine if the answerer is a knight (if he/she said "yes") or a knave (if "no").

P.S.

Of course, it may happen that $2^k-1-Q>n$. In this case we're lucky (we know that our first answerer was a knight), so we get 1 question less (of course, we need to discard the $2^k-1-Q$ value and ask if the number of knights in row 1 is in the single-element set $\{Q\}$.

Answer 3

A naive upper bound is

$n(n+2)$, since row/column information isn't always enough to uniquely determine a pattern.
Pick a room, and present a subset with at least two elements. Regardless of the answer, divide the subset in two and present each piece individually. An even number of "yes" answers indicates a knight, and an odd number indicates a knave. Once you identify a person in each row, the remaining rooms can be identified by asking "Are there ${0}$ knights?" if you found a knight or "Are there ${n}$ knights?" if you found a knave.

EDIT:

I forgot you can ask people about rows they're not in! This means you only need to identify one room, and then use the elimination process mentioned above. Additionally, if your initial subset is the set of even numbers, the last room of the initial row is determined by the others and can be skipped.
This solves the castle in $n^2+1$ questions.