Marvin just wants to know everything
Source: MEMO 2024 T3
August 27, 2024
combinatoricscombinatorics proposedgamegame strategy
Problem Statement
There are 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 such that Marvin can always accomplish his goal with at most questions.