Kvant Math Problem 371

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

Problem

On each square of a chessboard, an integer from 1 to 64 is written, with all numbers distinct. In a single query, by specifying any collection of squares, one can learn the collection (set) of numbers present on those squares. What is the minimum number of queries required to determine the number on each square?

S. V. Fomin

Exploration

Consider the problem on a $2\times 2$ chessboard first. There are four squares with numbers $1,2,3,4$ assigned distinctly. A single query that asks for all four squares reveals the full set ${1,2,3,4}$ but not which number belongs to which square. Asking each square individually, four queries suffice, but can fewer suffice? If we ask two overlapping pairs of squares, say the top row ${s_1,s_2}$ and the left column ${s_1,s_3}$, we obtain the sets of numbers on each pair. There are four numbers total, and each number appears in at least one query, but the overlapping information allows reconstructing the assignment. A systematic check shows that three queries suffice: the two overlapping pairs plus one extra single square resolves the ambiguity.

Scaling to an $8\times 8$ chessboard, the number of squares is $64$. Each query reveals a set of numbers on chosen squares. The problem reduces to designing a sequence of subsets whose set of results uniquely encodes the mapping from numbers to squares. This resembles encoding a bijection from $64$ elements to $64$ positions via membership in subsets. Each number can be represented by a binary string where each bit corresponds to presence in a query. To uniquely identify $64$ numbers, at least $6$ bits are required because $2^6 = 64$. Each bit corresponds to a query whose subset of squares is precisely those squares where the bit is $1$.

This suggests a lower bound of $6$ queries if each query can encode one bit per square. Testing small examples, such as $n=4$ squares, shows that $\lceil \log_2 4 \rceil = 2$ queries suffice using a similar binary encoding. The crucial point is ensuring that each number appears in a unique combination of queries and no two numbers share the same membership vector.

Problem Understanding

The problem asks to determine the minimum number of queries required to reconstruct the complete bijection between numbers $1$ through $64$ and the $64$ squares of a chessboard, given that each query returns only the set of numbers on the queried squares. This is a Type C problem: find the minimal number of queries. The core difficulty is encoding $64$ distinct numbers in a minimal number of set queries while ensuring each square can be uniquely determined. The intuitive answer is $6$ queries, because $6$ bits are sufficient to distinguish $64$ objects, and each query can provide one bit of information about every square.

Proof Architecture

Lemma 1. Any strategy of queries that uniquely determines all numbers must assign a distinct membership vector (sequence of presence/absence across queries) to each number, because if two numbers share the same vector, their positions cannot be distinguished. Sketch: This follows directly from the information returned by queries; identical vectors produce identical sets in all queries.

Lemma 2. The minimum number of queries required to produce $64$ distinct binary vectors is $6$. Sketch: There are $2^k$ distinct binary vectors with $k$ bits, and $2^5 = 32 < 64 < 2^6 = 64$, so $6$ is minimal.

Lemma 3. There exists an explicit construction of $6$ queries that assigns to each square a unique 6-bit vector. Sketch: Label the squares $0$ to $63$ and define query $i$ as the set of squares whose $i$-th binary digit is $1$; this guarantees all vectors are distinct.

Lemma 4. No strategy using fewer than $6$ queries can uniquely determine all numbers. Sketch: Any fewer than $6$ queries produces fewer than $64$ distinct membership vectors, which is insufficient to identify $64$ numbers.

The hardest step is rigorously arguing that fewer than $6$ queries cannot suffice, ensuring there is no clever combinatorial arrangement of overlapping sets that would reduce the number of queries below the binary bound.

Solution

Label the squares of the $8\times 8$ chessboard from $0$ to $63$. Consider each square's index expressed in binary as a 6-bit number $(b_5 b_4 b_3 b_2 b_1 b_0)$. For each $i$ from $0$ to $5$, define query $Q_i$ as the set of all squares whose $i$-th bit $b_i$ equals $1$. Execute these six queries. The number returned by query $Q_i$ belongs to $Q_i$ if and only if the corresponding square's $i$-th bit is $1$. By collecting the results of all six queries, one can reconstruct the 6-bit binary index of the square containing each number. This identifies uniquely the square for every number because all $64$ squares have distinct binary indices. Thus, $6$ queries suffice.

To prove that fewer than $6$ queries are insufficient, assume $k$ queries uniquely determine all $64$ numbers. Let each number be represented by a membership vector of length $k$, where the $j$-th component is $1$ if the number appears in the $j$-th query and $0$ otherwise. Distinct numbers must have distinct vectors; otherwise their positions are indistinguishable. The number of distinct vectors of length $k$ is at most $2^k$. Therefore, $2^k \ge 64$, which implies $k \ge 6$. Hence, $6$ is minimal.

The explicit construction shows the bound is achievable, and the counting argument shows no fewer queries suffice.

$\boxed{6}$

Verification of Key Steps

The critical verification concerns the encoding using 6-bit binary indices. Consider two distinct squares, for example, square $5$ (binary $000101$) and square $12$ (binary $001100$). For query $Q_0$, square $5$ is included because its least significant bit is $1$, square $12$ is excluded because its least significant bit is $0$. Checking all six queries reproduces the binary indices of both squares distinctly. No two squares have identical 6-bit vectors, confirming that all $64$ squares can be uniquely identified.

The argument that fewer than $6$ queries are insufficient is verified by considering that with $5$ queries, there are at most $2^5 = 32$ distinct vectors. Since $32 < 64$, at least two numbers would share the same vector and be indistinguishable, which shows $5$ queries cannot suffice.

Alternative Approaches

One could attempt a purely combinatorial design using overlapping sets of squares that do not directly correspond to binary digits but rather use a system akin to error-correcting codes or Latin squares. Such a construction could achieve $6$ queries as well, but the binary-index approach is preferable because it is simple, explicit, and guarantees uniqueness with a straightforward verification. Other methods would require checking more complex combinatorial interactions and provide no reduction in the number of queries.