All integers from 1 to 100 are written in a string in an unknown order. With one question about any 50 numbers, you can find out the order of these 50 numbers relative to each other. What is the minimum number of questions needed to definitely find out the order of all 100 numbers?

#
To find the desired order $a_{1}, a_{2}, \ldots, a_{100}$ of numbers in a row, it is necessary that each pair $\left(a_{i}, a_{i+1}\right), i=1,2, \ldots, 99$, appears in at least one of the sets about which questions are asked; otherwise, for two sequences $a_{1}, \ldots, a_{i}, a_{i+1}, \ldots, a_{100}$ and $a_{1}, \ldots, a_{i+1}, a_{i}, a_{100}$, all answers will be the same.

We will prove that after any two questions, a situation may arise where at least three more questions are needed to cover all pairs of adjacent numbers (not yet covered).

Let $k_{1}, k_{2}, \ldots, k_{50}$ be the order of the numbers about which the first question is asked, and $l_{1}, l_{2}, \ldots, l_{50}$ be the order of the numbers about which the second question is asked. We will construct a set $a_{1}, a_{2}, \ldots, a_{100}$ for which we cannot, by asking two more questions, uniquely determine the order of the numbers. Consider the situation where all numbers mentioned in both the first and second questions are in the same positions in the answers.

As the desired set, we will take the set where $k_{i}, l_{i} \in \{a_{2i-1}, a_{i}\}, i=1,2, \ldots, 50$, and, moreover, in each quartet $\left(a_{4m-3}, a_{4m-2}, a_{4m-1}, a_{4m}\right)$, $m=1,2, \ldots, 25$, there were no comparisons of adjacent pairs of numbers from this quartet in the first two questions. We will show that such a set exists.

Let $X$ be the set of numbers that did not appear in the first two questions. The following cases are possible:

$k_{2m-1}=l_{2m-1}, k_{2m}=l_{2m}$,

$k_{2m-1}=l_{2m-1}, k_{2m} \neq l_{2m}$,

$k_{2m-1} \neq l_{2m-1}, k_{2m} \neq l_{2m}$,

$k_{2m-1} \neq l_{2m-1}, k_{2m}=l_{2m}$,

For these cases, we will construct quartets $\left(a_{4m-3}, a_{4m-2}, a_{4m-1}, a_{4m}\right)$ as follows: $\left(k_{2m-1}, *, *, k_{2m}\right), \left(k_{2m-1}, *, k_{2m}, l_{2m}\right), \left(k_{2m-1}, l_{2m-1}, k_{2m}, l_{2m}\right)$

$\left(k_{2m-1}, l_{2m-1}, *, k_{2m}\right)$, where * can be any number from the set $X$ that did not appear in the questions and in the construction of previous quartets.

Thus, it is shown that after two questions, a situation is possible (regardless of the asker's desire) where no pair $(a_{i}, a_{i+1})$ for $i$ not divisible by 4 is covered. Each of the 100 numbers is part of at least one uncovered pair, and therefore, must appear in at least one of the subsequent questions.

Suppose that in this situation, all uncovered pairs can be covered in two questions; then each of the 100 numbers must appear in exactly one of such questions. Considering quartets of the form $(a_{4i-3}, a_{4i-2}, a_{4i-1}, a_{4i})$, $i=1,2, \ldots, 25$, we note that if one number from such a quartet appears in a question, then the other three must also (otherwise, not all pairs of adjacent numbers in this quartet will be covered). But then the number of numbers in the set about which the question is asked must be divisible by 4. Since 50 is not divisible by 4, we have a contradiction. Therefore, it is impossible to determine the order of the numbers $1,2, \ldots, 100$ in a row with four questions.

We will show how to do this in five questions. The first question is about the set $M_{1}=\{1,2, \ldots, 50\}$, the second is about the set $M_{2}=\{51,52, \ldots, 100\}$. The set $M_{3}$ will consist of the 25 leftmost numbers of the set $M_{1}$ and the 25 leftmost numbers of the set $M_{2}$, and the set $M_{4}$ will consist of the 25 rightmost numbers of the set $M_{1}$ and the 25 rightmost numbers of the set $M_{2}$. The answer to the question about the set $M_{3}$ will clearly determine the numbers $a_{1}, a_{2}, \ldots, a_{25}$, and the answer to the question about the set $M_{4}$ will determine the numbers $a_{76}, a_{77}, \ldots, a_{100}$. The fifth question will determine the order of the remaining 50 numbers in the desired row.

## Answer

In five questions.

Submit a comment