Bogdanov I.I.

On each of 2013 cards, a number is written, and all these 2013 numbers are distinct. The cards are face down. In one move, it is allowed to point to ten cards, and in response, one of the numbers written on them will be reported (it is unknown which one).

For what largest $t$ can it be guaranteed to find $t$ cards, for which it is known what number is written on each of them?
1) Let's first show that it is impossible to guess $1987=2013-26$ cards. We will number the cards $A_{1}, \ldots, A_{2013}$, place the numbers from 1 to 2013 on them in the same order, and indicate how to answer so that none of the numbers on the cards $A_{1}, \ldots, A_{27}$ can be determined.

For each $i=1, \ldots, 9$, we will combine the cards $A_{3 i-2}, A_{3 i-1}, A_{3 i}$ into a triplet $T_{i}$. If among the specified 10 cards there are cards with numbers greater than 27, we will name the smallest such number. If all 10 cards lie within the triplets, then in some triplet $T_{i}$ there are at least two cards; in this case, we will name the number on the edge between these cards on the diagram (if there are several such pairs, we will name the smallest of the numbers on the corresponding edges).

![](https://cdn.mathpix.com/cropped/2024_05_06_2434826925a2883e8926g-21.jpg?height=451&width=558&top_left_y=998&top_left_x=750)

Note that if the numbers on the cards $A_{1}, A_{1}, A_{1}$ are $3,1,2$ (instead of $1,2,3$), our answers will not change. There is also no "uniqueness" in the other triplets. Therefore, none of the numbers on the cards in the triplets can be determined.

2) It remains to prove that the numbers on all cards except 27 can be determined. For this, we will show that if we ask all possible questions about some 28 cards, then we can determine the number on one of them. After that, we can replace this card with one of the remaining ones and repeat the procedure. Acting this way, we will eventually determine the numbers on all cards except 27.

We will need the following lemma.

Lemma. Suppose a graph has at least $3 n-2$ vertices and no more than $3 n-2$ edges ($n \geq 2$). Then there exist $n$ vertices with no edges between them.

Proof. Induction on $n$. Note that we can remove several vertices and then add several edges so that the number of vertices and edges becomes $3 n-2$.

Base case. For $n=2$, on four vertices there are fewer than six edges; hence, some pair of vertices is not connected, and we can choose these two vertices.

Inductive step. Let the degrees of the vertices be $d_{1}, \ldots, d_{3 n-2}$; then $d_{1}+\ldots+d_{3 n-2}=2(3 n-2)$. Therefore, either there exists a number $d_{i} \leq 2$, or all degrees are 2. In the first case, remove the $i$-th and $j$-th vertices, as well as the only neighbor of the $i$-th vertex (if it exists); we removed no more than three vertices and no fewer than three edges. In the second case, remove an arbitrary vertex (let its number be $i$) and its two neighbors; since their degrees are 2, we removed no fewer than three edges and exactly three vertices. In the remaining graph, by the inductive hypothesis, there exist $n-1$ vertices with no edges between them; adding the $i$-th vertex to them, we get the required set of $n$ vertices (since we removed all neighbors of the $i$-th vertex).

Returning to the solution of the problem. Suppose we asked all questions about 28 cards, and let $c_{1}, \ldots, c_{k}$ be all the numbers that appear in the answers (then $k \leq 28$). For each $i=1,2, \ldots, k$, consider all tens of cards for which we received the number $c_{i}$ as an answer; denote their intersection by $S_{i}$ (this set is non-empty, as it contains the card with the number $c_{i}$). If this set has one element, then this is the card with the number $c_{i}$, and we have determined the number on it.

Otherwise, in each of these sets, there are at least two cards. For each $i$, choose two cards in $S_{i}$ and connect them with an edge. We obtained a graph satisfying the condition of the lemma for $n=10$; hence, in this graph, we can choose 10 cards with no edges between them. The answer to this ten was some number $c_{i}$. Therefore, this ten must contain the set $S_{i}$, and consequently, two cards from the ten are connected by the corresponding edge. Contradiction.

## Answer

$t=1986$.