Let $n \geq 2$ be a positive integer. In a mathematics competition, there are $n+1$ students, with one of them being a hacker. The competition is conducted as follows: each receives the same problem with an open-ended answer, has 5 minutes to give their own answer, after which all answers are submitted simultaneously, the correct answer is announced, then they receive a new problem, and so on. The hacker cheats by using spy cameras to see the answers of the other participants. A correct answer gives 1 point, while a wrong answer gives -1 point to everyone except the hacker; for him, it's 0 points because he managed to hack the scoring system. Prove that regardless of the total number of problems, if at some point the hacker is ahead of the second-place contestant by at least $2^{n-2} + 1$ points, then he has a strategy to ensure he will be the sole winner by the end of the competition.
Problem
Source: XIII International Festival of Young Mathematicians Sozopol 2024, Theme for 10-12 grade
Tags: combinatorics
15.09.2024 23:43
Claim: (For our inductive hypothesis) ,When the hacker is ranked $1$st on the leaderboard, his strategy should always be to copy the answers of player $2$. Proof:Since the $2$nd place contestant gets $1$ point for each question he answers correctly, the difference in score between him and the hacker does not change. Let's say the $2$nd place player gets it wrong, in this case the hacker's score does not change, while the $2$nd player's score decreases by $1$. (If there is someone who gets the same score as the $2$nd player and the $2$nd player gets the question wrong and the other player gets the question right, he can pass the $1$st player, but this is not possible due to our inductive hypothesis.) Inductive Hypothesis: Let's assume that for $n$, if the hacker increases the point difference with the $2nd$ ranked player by $2^{n-2}+1$ and comes to the $1st$ ranked position, he will not be defeated at any point in the process.In this case, at any point in the process, the score of player $2$ can be at most $2^{n-2}$. If the score of player $3$ is $2^{n-2}$, there is a possibility of rising to rank $1$ as a result of finite moves since there are two $2^{n-2}$ points on the scoreboard. Applying Induction once more, it is seen that at any point in the process, the points of the players (excluding the hacker) are at most $\{2^{n-2}+1,2^{n-2},2^{n-2}-1,..,2^{n-2}+1-n\}$. Now, let's include a player with $0$ points, who is not in the process, into the set $\{2^{n-2}+1,2^{n-2},2^{n-2}-1,..,2^{n-2}+1-n\} \rightarrow\{2^{n-2}+1,2^{n-2},2^{n-2}-1,..,2^{n-2}+1-n,0\}$ In this case, this player will answer all $2^{n-2}$ questions correctly, causing two $2^{n-2}$ point players to appear on the scoreboard, so the hacker must have a difference of $2^{n-2}+ 2^{n-2}+1= 2^{n-1}+1$ points. (Also similar with Turkey Olympic Revenge 2024 Station Problem)