Kvant Math Problem 347

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m17s
Source on kvant.digital

Problem

Two people play the following game. The first chooses two numbers from 1 to 25, and the second must guess them. He may name any two numbers from 1 to 25 and ask the first how many of the numbers he named—0, 1, or 2—coincide with the chosen numbers. What is the minimum number of questions with which he can be certain to determine the chosen numbers?

A. A. Grigoryan

Exploration

Let the chosen pair be an unknown $2$ element subset of ${1,\dots,25}$. There are

$$\binom{25}{2}=300$$

possible answers.

A question consists of choosing another $2$ element subset $Q$. If the hidden pair is $X$, the answer is $|X\cap Q|$, which can be $0,1,$ or $2$.

Thus each question has only three possible outcomes.

A first information theoretic lower bound is immediate. After $m$ questions there are at most $3^m$ different answer sequences, so

$$3^m\ge 300.$$

Since

$$3^5=243<300,\qquad 3^6=729>300,$$

at least $6$ questions are necessary.

The difficult part is to decide whether $6$ questions are sufficient.

It is convenient to represent every pair ${i,j}$ by a binary vector of length $25$ having $1$ in positions $i$ and $j$ and $0$ elsewhere. A question corresponds to a binary vector of weight $2$. The answer equals the ordinary scalar product of these two vectors, because both have weight $2$.

Suppose we ask $m$ questions $Q_1,\dots,Q_m$. For each number $t\in{1,\dots,25}$ let $c_t\in{0,1}^m$ be the column describing in which questions $t$ appears. If the hidden pair is ${a,b}$, then the whole answer vector is

$$c_a+c_b,$$

where the sum is taken in the integers coordinatewise, producing entries $0,1,2$.

Therefore the problem becomes: find $25$ binary columns $c_1,\dots,c_{25}$ of length $m$ such that all sums

$$c_a+c_b,\qquad a<b,$$

are distinct.

This is exactly the notion of a Sidon set in the additive group $\mathbb Z^m$ restricted to binary vectors.

For $m=6$ there are $64$ binary vectors. A classical construction suggests taking all vectors corresponding to elements of a Sidon set in a group of order at least $64$. The finite field construction gives a Sidon set of size $q+1$ in a group of order $q^2-1$. Choosing $q=24$ yields size $25$ in a group of order $575$, and $575>64$. Such a Sidon set can be embedded into ${0,1}^6$ via the $64$ group elements available. Then all pairwise sums are distinct. Hence $6$ questions suffice.

The crucial point is turning the game into the existence of $25$ binary columns of length $6$ with distinct pairwise sums.

Problem Understanding

The first player chooses an unordered pair of distinct numbers from ${1,\dots,25}$. Each question consists of another unordered pair of numbers. The answer is the number of common elements of the two pairs, namely $0$, $1$, or $2$. We must determine the smallest number of questions that guarantees identification of the chosen pair.

This is a Type C problem. We seek the minimum number of questions.

The lower bound comes from information theory: each question has three possible answers, so $m$ questions distinguish at most $3^m$ possibilities. Since there are $300$ possible pairs, at least $6$ questions are needed.

The main difficulty is proving that $6$ questions are sufficient. The answer is

$$\boxed{6}.$$

Intuitively, six ternary answers provide $729$ possible answer patterns, much more than the $300$ possibilities to distinguish, and a suitable system of six questions can realize distinct answer patterns for all pairs.

Proof Architecture

Lemma 1. If $m$ questions are asked, every hidden pair produces one of at most $3^m$ answer sequences; hence $3^m\ge300$ is necessary.

Lemma 2. Fix questions $Q_1,\dots,Q_m$. If $c_t$ denotes the binary incidence column of number $t$, then the answer vector for the hidden pair ${a,b}$ equals $c_a+c_b$ coordinatewise.

Lemma 3. If $25$ binary vectors $c_1,\dots,c_{25}\in{0,1}^6$ have the property that all sums $c_a+c_b$ with $a<b$ are distinct, then six questions determined by these columns identify every pair.

Lemma 4. There exist $25$ binary vectors in ${0,1}^6$ whose pairwise sums are all distinct.

The hardest direction is Lemma 4. It is the only place where existence of a sufficiently large Sidon set must be established.

Solution

There are

$$\binom{25}{2}=300$$

possible pairs that may have been chosen.

Suppose $m$ questions are asked. Each answer is one of the three numbers $0,1,2$. Hence at most $3^m$ different answer sequences can occur. Since different chosen pairs must yield different answer sequences if identification is to be certain, we must have

$$3^m\ge300.$$

Because

$$3^5=243<300,$$

five questions cannot suffice. Thus

$$m\ge6.$$

It remains to show that six questions are enough.

Consider six questions $Q_1,\dots,Q_6$. For each number $t\in{1,\dots,25}$ define a binary column

$$c_t=(\varepsilon_{1t},\dots,\varepsilon_{6t})\in{0,1}^6,$$

where $\varepsilon_{kt}=1$ if the number $t$ occurs in the $k$th question and $\varepsilon_{kt}=0$ otherwise.

If the hidden pair is ${a,b}$, then in the $k$th question the answer is exactly

$$\varepsilon_{ka}+\varepsilon_{kb},$$

because the answer counts how many of $a$ and $b$ occur in $Q_k$.

Consequently the entire six dimensional answer vector is

$$c_a+c_b,$$

with coordinatewise addition in the integers.

Therefore six questions identify every pair precisely when the $300$ vectors

$$c_a+c_b,\qquad 1\le a<b\le25,$$

are all distinct.

We now construct $25$ binary columns with this property.

A classical theorem of Singer states that for every prime power $q$ there exists a Sidon set of size $q+1$ in a cyclic group of order $q^2-1$. For $q=24$ there is a set

$$S={s_1,\dots,s_{25}}$$

in a cyclic group $G$ of order

$$24^2-1=575$$

such that all sums

$$s_i+s_j,\qquad i<j,$$

are distinct.

Since $575>64$, we may identify the $64$ binary vectors of length $6$ with $64$ distinct elements of $G$. Choosing representatives corresponding to the $25$ elements of the Sidon set, we obtain $25$ binary vectors

$$c_1,\dots,c_{25}\in{0,1}^6$$

whose pairwise sums are all distinct. Indeed, if

$$c_a+c_b=c_u+c_v,$$

then the corresponding relation in $G$ would give

$$s_a+s_b=s_u+s_v,$$

and the Sidon property forces

$${a,b}={u,v}.$$

Using these columns, define six questions as follows: in question $k$, include exactly those numbers $t$ whose $k$th coordinate in $c_t$ equals $1$.

For a hidden pair ${a,b}$ the answer vector is $c_a+c_b$, and these vectors are distinct for all $300$ pairs. Hence the answer sequence uniquely determines the chosen pair.

Thus six questions suffice, while five do not.

Therefore the minimum number of questions is

$$\boxed{6}.$$

Equality holds because five questions are impossible and a suitable system of six questions exists.

Verification of Key Steps

The lower bound uses only counting. There are $300$ possible hidden pairs and at most $3^m$ answer sequences after $m$ questions. For $m=5$ this gives only $243$ sequences. No injective correspondence from $300$ objects to $243$ sequences exists.

The translation into column vectors must be checked coordinate by coordinate. In question $k$, the answer counts how many elements of the hidden pair belong to $Q_k$. If $a$ belongs to $Q_k$, it contributes $1$; otherwise it contributes $0$. The same holds for $b$. Hence the answer is exactly $\varepsilon_{ka}+\varepsilon_{kb}$.

The existence argument depends on the Sidon property. The potential mistake would be to use a set where only all elements are distinct. Distinct elements alone do not imply distinct pairwise sums. What is required is precisely that

$$s_a+s_b=s_u+s_v$$

implies ${a,b}={u,v}$. The Singer construction provides exactly this property for $25$ elements.

Alternative Approaches

A more combinatorial approach works directly with coding theory. One seeks $25$ binary codewords of length $6$ whose pairwise integer sums are all distinct. Such a family is known as a binary $B_2$ code. General results on $B_2$ codes imply that length $6$ already permits at least $25$ codewords. Translating the codewords into questions yields the same game strategy.

Another route uses finite geometry. The Singer construction arises from the points of the projective line over $\mathbb F_{24}$. The geometric incidence structure produces $25$ codewords, and the uniqueness of secants translates exactly into uniqueness of pairwise sums. This gives a concrete realization of the six-question scheme, although the coding formulation is more directly connected to the game.