There are $2024$ mathematicians sitting in a row next to the river Tisza. Each of them is working on exactly one research topic, and if two mathematicians are working on the same topic, everyone sitting between them is also working on it. Marvin is trying to figure out for each pair of mathematicians whether they are working on the same topic. He is allowed to ask each mathematician the following question: “How many of these 2024 mathematicians are working on your topic?” He asks the questions one by one, so he knows all previous answers before he asks the next one. Determine the smallest positive integer $k$ such that Marvin can always accomplish his goal with at most $k$ questions.
Problem
Source: MEMO 2024 T3
Tags: combinatorics, combinatorics proposed, game, game strategy
18.10.2024 04:12
If I've done it right,the answer should be $2023$ though this might be a little trolling like 24IMO5. $\color{red}\rule{25cm}{1pt}$ $\color{red}\textbf{Strategy of Marvin.}$This part is quite trivial since Marvin only need to ask the $i$th mathematician $(1\le i\le 2023)$ to accomplish his goal. $\color{blue}\rule{25cm}{1pt}$ $\color{blue}\textbf{Strategy of mathematicians.}$We claim that even if all the mathematicians only answer $1$ or $2$,they are still able to confuse Marvin as long as $k\le 2022$. Here's the specific strategy.Assume at some point Marvin asks the $i$th mathematician. $\color{blue}\textbf{Case 1.}$There exist $1\le j\le i+1$th and $i+1\le k\le 2024$th mathematicians haven't been asked before.Then we make the $i$th mathematician answer $2$. $\color{blue}\textbf{Case 2.}$All $1\le j\le i+1$th mathematicians have been asked before.Assume that all $i+1\le k\le i+s$th mathematicians have been asked before,($s$ could be $0$)and we maximize $s$.If $s$ is odd,make the $i$th one answer $2$,and answer $1$ when $s$ is even. By induction it's easy to see that there do exist a construction satisfies the answers in this case. $\color{blue}\textbf{Case 3.}$All $i+1\le k\le 2024$th mathematicians have been asked before.This case is symmetrical to the second case. $\rule{25cm}{1pt}$ When Marvin asked all $2022$ questions,there exist $1\le i<j\le 2024$th mathematicians who haven't been asked.Thus Marvin can only determine the situation of $1\le p\le i-1$th and $j+1\le q\le 2024$th mathematicians ,but since obviously all the $i+1\le k\le j-1$th mathematicians answered $2$,it's ez to construct $2$ possible forms of question distributions that fit all the answers,thus $k\ge 2023$.And we're done.