Yesterday, $n\ge 4$ people sat around a round table. Each participant remembers only who his two neighbours were, but not necessarily which one sat on his left and which one sat on his right. Today, you would like the same people to sit around the same round table so that each participant has the same two neighbours as yesterday (it is possible that yesterday’s left-hand side neighbour is today’s right-hand side neighbour). You are allowed to query some of the participants: if anyone is asked, he will answer by pointing at his two neighbours from yesterday. a) Determine the minimal number $f(n)$ of participants you have to query in order to be certain to succeed, if later questions must not depend on the outcome of the previous questions. That is, you have to choose in advance the list of people you are going to query, before effectively asking any question. b) Determine the minimal number $g(n)$ of participants you have to query in order to be certain to succeed, if later questions may depend on the outcome of previous questions. That is, you can wait until you get the first answer to choose whom to ask the second question, and so on.
Problem
Source: Benelux Mathematical Olympiad 2012
Tags: algorithm, combinatorics proposed, combinatorics
24.04.2012 07:57
(a) $f(n) = n-3$. This is fairly easy to verify. If $n-4$ questions are asked and you don't ask four people that were sitting consecutively, then you can't figure out who was who in the middle. (b) If $n = 3q - r$ for $r \in \{0,1,2\}$, then $g(n) = 2q - r - 1$. Call a chain a group of people $a_1, a_2, \ldots a_k$ ($k > 1$) such that we know $a_i, a_{i+1}$ sat next to each other. We can define the known information at any given point in terms of chains. Initially we have no chains, and we're done asking questions when we have 1 chain with all $n$ people or 1 chain with $n-1$ people. Suppose we have a configuration of chains where $c$ is the total number of chains, $p$ is the total number of people not in chains, and $r_p$ is such that $r_p \in \{0,1,2\}$ and $p = 3q_p - r_p$. We will say this configuration of chains has $3(c-1)+2p-r_p$ points. It can be computed that we initially start with $3(2q-r-1)$ points, and we finish as soon as we have no points left. This is true regardless of whether the finish is with 1 chain of $n$ or 1 chain of $n-1$. Suppose an algorithm asks a person not in a chain. One of three things can happen. (i) They point to two people not in chains. This creates a new chain out of those three people. Loses 3 points. (ii) They point to exactly one person in a chain. This lengthens that chain by two. Loses 3 or 6 points (depends on $r_p$). (iii) They point to two people in different chains. This merges those chains and adds one total person to them. Loses 3 or 6 points (depends on $r_p$). If an algorithm asks a person on the edge of a chain (asking in the middle is pointless), there are a couple possibilities for the unknown neighbor they point to. (iv) They point to a person not in a chain. The chain lengthens by one. Loses 0 or 3 points (depends on $r_p$). (v) They point to a person in another chain. The chains merge. Loses 3 points.
That means in the worst case, any algorithm can lose at most 3 points each turn. On the other hand, by always asking a person not in a chain when one exists and otherwise asking anyone on the edge of a chain (this avoids (iv) entirely), we can always guarantee to lose at least 3 points each turn. So $g(n)$ is equal to the initial number of points divided by 3, namely $2q-r-1$.
24.04.2012 23:57
Nice proof Best result in the contest was 3/7... Did you think the problem was too hard? I thought it's maybe a IMO2-5 level?
25.04.2012 02:39
Time would be the main issue. I imagine a lot of methods for solving this require substantial casework or such, what with the fact that there's two ending states (1 chain of either $n$ or $n-1$) and multiple ways to obtain the best bound $g(n)$ (if $n$ is 1 or 2 mod 3 you can afford to ask people at the edge of a chain early). I specifically went after the "scoring" approach above to deal with these issues, but for someone trying other solution methods they're probably time-consuming to address. I take it this was the last problem. That would make the time issue worse. Otherwise, IMO 2/5 sounds about right.
25.04.2012 08:50
I solved problem 4 quite early (and got also 3), they were really strong: if you give your pattern and then shows if we take a step in an other way, it loses , they didn't give any point due to the marking scheme that hadn't 1/3 for that part, because you don't mention explecitely enough the normal worst case keeps being it.