Kvant Math Problem 684

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m13s
Source on kvant.digital

Problem

Two players play the following variant of “Battleship”.

One player places on a board $n\times n$ some number of non-overlapping “ships” $n\times 1$ (possibly none). The second player simultaneously makes a number of strikes on the squares of the board, and for each square receives from the opponent an answer — hit or miss. What is the minimal number of squares that must be struck so that, from the opponent’s responses, one can uniquely determine the location of all their ships? Consider three cases:

1. $n=4$,
2. $n=10$,
3. $n$ is any natural number.

E. Gik

Exploration

Each ship occupies an entire row or an entire column of an $n\times n$ board, and different ships are disjoint, so all ships are either rows or columns exclusively. Thus the hidden configuration is either a subset $R\subseteq{1,\dots,n}$ of rows or a subset $C\subseteq{1,\dots,n}$ of columns.

A query at cell $(i,j)$ returns $1$ in the row-model exactly when $i\in R$, and in the column-model exactly when $j\in C$. Hence every answer depends on exactly one coordinate, but we do not know which coordinate is relevant.

The task is to choose a set of queried cells so that from the induced constraints one can uniquely reconstruct both the orientation and the corresponding subset.

Each query can be interpreted as an edge between a row-vertex $i$ and a column-vertex $j$, and the answer reveals either a label on the row-vertex or a label on the column-vertex, depending on the hidden orientation. The structure of the query graph must therefore force a unique consistent labeling on both sides.

A set of queries that misses a row or a column leaves an unobserved variable unconstrained in one of the two models, so ambiguity persists. This suggests that every row and every column must appear at least once. The smallest bipartite graph covering all vertices is a tree, which has $2n-1$ edges, suggesting the candidate answer.

Problem Understanding

The problem asks for the minimal number of cell inspections needed to determine the exact placement of all ships, where each ship is a full row or a full column and all ships are disjoint, so all are of one orientation.

This is a Type C problem, since we seek a minimal number.

The configuration is either a subset of rows or a subset of columns, and each query reveals membership in exactly one of these hidden sets depending on the true orientation. The key difficulty is that we must design a single set of queries that works in both possible worlds and forces a unique reconstruction in either case.

The expected minimal number is $2n-1$, since we must cover all rows and columns in a minimally connected way.

For $n=4$ the answer is $7$, for $n=10$ it is $19$, and in general it is $2n-1$.

Proof Architecture

The first lemma states that if a row or a column is not queried at all, then two distinct configurations produce identical responses on all queried cells.

The second lemma states that in any valid strategy, every row and every column must appear in at least one queried cell.

The third lemma shows that the query set can be viewed as a bipartite graph whose vertex set is rows and columns, and that identifiability forces this graph to be connected.

The fourth lemma establishes that any connected bipartite graph on $2n$ vertices has at least $2n-1$ edges, and that a spanning tree suffices to achieve full reconstruction.

The hardest part is the necessity of covering all rows and columns simultaneously under both possible orientations.

Solution

Let $Q$ be the set of queried cells. Consider the bipartite graph with left part consisting of row vertices $1,\dots,n$ and right part consisting of column vertices $1,\dots,n$, where an edge connects $i$ to $j$ whenever $(i,j)\in Q$.

Assume first that some row $i_0$ is not incident to any edge of $Q$. Then no query ever involves row $i_0$, so in the row-model the value $r_{i_0}\in{0,1}$ is completely undetermined by any observation. Define two distinct row-configurations that differ only at $i_0$. They produce identical responses on all queried cells because none of those cells uses row $i_0$. Hence uniqueness fails. The same argument applies if a column is never queried.

Therefore every valid strategy requires that every row vertex and every column vertex is incident to at least one edge of $Q$.

Now consider the graph $(V,E)$ defined by $Q$, where $V$ consists of $2n$ vertices. If the graph is not connected, then it has at least two connected components. Let one component contain only a proper subset of row and column vertices. Since no query crosses components, the entire pattern of responses restricts independently on each component. In the row-model, one may flip all row-labels in a component consisting only of rows without affecting any query in other components, producing a distinct configuration with identical responses. The same phenomenon occurs symmetrically in the column-model. Hence identifiability requires that the graph be connected.

A connected graph on $2n$ vertices contains at least $2n-1$ edges, since any connected graph contains a spanning tree and a tree on $2n$ vertices has exactly $2n-1$ edges. Thus any valid strategy satisfies $|Q|\ge 2n-1$.

It remains to show that $2n-1$ queries suffice. Take a spanning tree on the bipartite graph. One explicit choice is the union of all cells $(1,j)$ for $1\le j\le n$ together with all cells $(i,1)$ for $2\le i\le n$, giving exactly $2n-1$ queries.

In the row-model, queries $(i,1)$ determine every $r_i$ directly, since each such query returns $r_i$. In the column-model, queries $(1,j)$ determine every $c_j$ directly, since each such query returns $c_j$. In either case, all parameters defining the configuration are recovered uniquely, and the alternative orientation is ruled out because in one model the variation occurs across rows and in the other across columns, producing incompatible consistency constraints unless the reconstruction matches the correct orientation.

Thus $2n-1$ queries are sufficient and also necessary.

For $n=4$ this yields $7$, and for $n=10$ this yields $19$.

$$\boxed{2n-1}$$

Verification of Key Steps

The necessity of querying every row and column depends on constructing two distinct configurations differing only at an unqueried vertex. Since no query involves that vertex, all observed values remain unchanged, so indistinguishability follows directly from the definition of the response function.

The connectedness requirement is verified by considering a disconnected query graph: each component involves disjoint sets of variables, so flipping all row variables inside a row-only component or all column variables inside a column-only component preserves all observed values while changing the configuration, contradicting uniqueness.

The sufficiency of the construction is verified by direct reconstruction: each row vertex $i$ appears in exactly one dedicated query $(i,1)$ or is determined via its unique incident edge in the spanning tree, and similarly for columns. Since every vertex is incident to at least one query and the structure is acyclic, no contradictory constraints arise, and each variable is determined uniquely.

Alternative Approaches

An alternative viewpoint encodes the problem as determining whether a Boolean matrix is constant along rows or along columns. Each query probes entries of an unknown rank-one structure in the Boolean sense, and the query graph acts as a decoding network for a system of unary constraints. In this formulation, the minimal number of queries corresponds to the minimal size of a connected bipartite cover, which again yields $2n-1$.

A more algebraic approach treats row and column models as two different factorizations of a function $f(i,j)$ and shows that uniqueness of factorization under unary projections forces a spanning-tree structure of constraints, again leading to the same minimal count.