11.5. On one side of each of 100 cards, one of the natural numbers from 1 to 100 inclusive was written (each number is written on exactly one card), after which they were turned face down and laid out in a random order on the table. In one question, Vasya can point to any two cards, after which he receives an answer from the host indicating whether the numbers written on them are adjacent (differing by 1). What is the minimum number of questions Vasya can guarantee to name at least one pair of cards with adjacent numbers?
Answer. In 98 questions.

Solution. Let Vasya choose some card A and ask 98 questions, each of which will be about A and one of the 99 cards different from A. The total number of numbers not adjacent to the number written on A does not exceed 98 if 1 or 100 is written on A, and 97 if numbers from 2 to 99 are written on A. Then either one of the 98 answers will be positive, and Vasya will have found the required pair of adjacent numbers, or all these cards contain numbers not adjacent to the number on A. Therefore, the remaining card contains a number adjacent to the number on A. Thus, Vasya needs only 98 questions.

We will prove that if Vasya asks only 97 any questions, he may not find any pair of cards with adjacent numbers. Suppose the opposite, that by asking some 97 questions, he could accurately indicate a pair of cards with adjacent numbers. Let's translate the problem into the language of graph theory. Cards will be considered vertices of the graph G, and the questions asked by Vasya - edges of G (blue edges), connecting the corresponding pairs of cards. To these edges, we need to add one more, corresponding to the pair of cards, on which, according to Vasya, a pair of adjacent numbers is written. Now we need to prove that the vertices of G can be numbered in such an order that no edge connects two vertices with adjacent numbers. That is, we need to draw in the graph a path of 99 edges, passing sequentially through all 100 vertices, and not containing any of the 98 "Vasya's" blue edges. This will mean that Vasya's guess is incorrect. Let's call such a path red and build it by mathematical induction on the number of vertices of the graph $\Gamma$.

Suppose that in any graph with the number of vertices $n \leq 99$, in which no more than $n-2$ blue edges are drawn, there exists a red path P through all vertices, not containing blue edges. We will construct a red path in $G$.

1) Suppose that in G there is an "extreme" vertex $v$, from which exactly one edge $\boldsymbol{e}$ comes out. In the graph $\Gamma^{\prime}$, obtained from G by removing the vertex $\boldsymbol{v}$ and the edge $\boldsymbol{e}$, the number of vertices is 99, and the number of edges is no more than 97, the induction hypothesis is satisfied, so in G' a red path of length 98 can be constructed with the start at vertex $\boldsymbol{a}$ and the end at vertex $\boldsymbol{b}$. Then the edge $\boldsymbol{e}$ does not connect the vertex $\boldsymbol{v}$ with one of $\boldsymbol{a}$ or $\boldsymbol{b}$, by drawing a red edge from $\boldsymbol{v}$ to this vertex, we get a red path of length 99 in $\Gamma$.
2) Suppose that in G there are no vertices from which exactly one edge comes out. In this case, all blue edges are incident to a total of 196 vertices, each with a degree of at least 2, so among them there are no more than 98 different ones. Therefore, in G there are at least two vertices $\boldsymbol{u}, \boldsymbol{v}$ from which no blue edge comes out. Remove from G the vertices $\boldsymbol{u}, \boldsymbol{v}$ and two edges coming out of some fourth vertex $s$ (but not the vertex itself). The resulting graph G' again satisfies the induction hypothesis and in it a red path of length 97 can be constructed with the start at vertex $\boldsymbol{a}$ and the end at vertex $\boldsymbol{b}$. If it does not pass through $s$, or passes through it but does not pass through the removed edges, connect $\boldsymbol{a}$ with $\boldsymbol{u}$ and $\boldsymbol{b}$ with $\boldsymbol{v}$ and get a red path in G of length 99.

In the remaining cases, denote by $\boldsymbol{x}$ and $\boldsymbol{y}$ the second ends of the removed edges.

If the red path in $\Gamma^{\prime}$ passes through $\boldsymbol{x}, \boldsymbol{s} \boldsymbol{y}, \boldsymbol{y}$, replace this segment with $\boldsymbol{x}, \boldsymbol{u}$, $s, \boldsymbol{v}, \boldsymbol{y}$. If it passes only through one removed edge, say, through $\boldsymbol{x}$, $\boldsymbol{s}$, replace it with $\boldsymbol{x}, \boldsymbol{u}, \boldsymbol{v} \boldsymbol{s}$. In both cases, a red path in $\Gamma$ will be obtained.

The base of induction - the cases of graphs with 3 and 4 vertices - is obvious.

Grading criteria. ($\cdot$) An algorithm for finding a pair of cards with adjacent numbers is provided: 2 points. Lack of justification - minus 1 point. ($\cdot$)

($\cdot$) With a correctly described algorithm, an incorrect answer of 99 questions: 1 point ($\cdot$) The statement to be proved by induction is correctly formulated, that for any 98 marked edges, a chain of 99 edges can be constructed that does not contain marked edges: 1 point. ($\cdot$) Proof that the number of questions is not less than 98: 5 points. If, in an otherwise correct inductive proof, significant cases are not considered - minus up to 3 points.