This puzzle is an 7-9 grade math Olympiad puzzle. 50 criminals came to a meeting. Each of the criminals has a maximum of 24 enemies among those who came to the encounter. Prove that it is possible to seat all the criminals around a round table so that none of them sit next to their enemy. (if criminal A is an enemy of criminal B, so criminal B is an enemy of criminal A).
2
-
$\begingroup$ What year is this from? Do you have a link? $\endgroup$– bobbleOct 17 at 13:47
-
1$\begingroup$ The original question is in Hebrew from a local math olympiad in 2019. $\endgroup$– MG5Oct 17 at 19:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
This result follows almost immediately from
Construct a graph with 50 nodes representing the criminals and
edges between every pair of non-enemies. Each criminal has at most 24 enemies, so there are at least 25 non-enemies amongst the 49 other criminals. Therefore the graph nodes have degree 25 or more. Any pair of nodes therefore has a total degree of 50 or more. This satisfies the prerequisites of Ore's theorem (which merely needs pairs of non-adjacent nodes to have a combined degree of 50 or more). The theorem says there is a Hamiltonian cycle, and if you place the criminals in the order of that cycle around the table then each will be flanked by non-enemies.
Here is a direct proof.
This is basically a proof of Ore's theorem, rewritten to the context of this problem.
Put the criminals around the table in any order. If there is no pair of adjacent enemies, then we are done.
Otherwise, number the criminals in order so that a pair of enemies are $1$ and $2$. Consider each other adjacent pair, $k$, $k+1$ (with $3\le k<50$), and try to find such a pair that $1$ and $k$ are non-enemies, and $2$ and $k+1$ are non-enemies. If you find such a pair, then you can reverse the order of criminals $2...k$ to fix the enemy pair $(1,2)$. The new order becomes $1,k,k-1,...,2,k+1,k+2...,n$ and this replaces the $(1,2)$ and $(k,k+1)$ adjacencies by $(1,k)$ and $(2,k+1)$, reducing the number of adjacent enemy pairs by at least one.
Can you always find such a pair? Criminal $1$ has at most $24$ enemies including criminal $2$, and similarly criminal $2$ has at most $24$ enemies including criminal $1$. We are checking $47$ pairs from $(3,4)$ to $(49,50)$, and at most $23$ fail due to an enemy of criminal $1$, and at most $23$ fail due to an enemy of criminal $2$, so at least one such pair must work. Therefore the number of adjacent enemy pairs can always be reduced by the method above.
By repeating this, eventually the number of pairs of adjacent enemies is reduced to zero, and we are done.
answered Oct 17 at 13:31
-
$\begingroup$ Ok thanks for this answer but this has been asked in math Olympiad for 12 years old kids... I doubt anyone have ever heard about the Ore's theorem. $\endgroup$– MG5Oct 17 at 19:36
-
-
1$\begingroup$ Instead of Ore's theorem one could also use Dirac's theorem, which says if every vertex in a graph has degree at least n/2 than it is Hamiltonian. I don't know whether this has an easier proof. $\endgroup$– quaragueOct 19 at 8:00
-
$\begingroup$ @quarague I didn't know of Dirac's theorem, but the proofs I saw in a quick search all seem to be similar to the proof I transcribed above, in that they all involve reversing a section of a path/cycle when things get stuck. $\endgroup$ Oct 19 at 12:20
-
$\begingroup$ @MG5 The only thing we are looking for is a value of k such that (1,k) are non-enemies and (2,k+1) are non-enemies. For that particular k we do not care about the relationships (1,k+1), (2,k) or even (k,k+1). $\endgroup$ Nov 4 at 19:23
$\begingroup$
$\endgroup$
2
We can show easily by induction that n criminals where each has a maximum of $\lfloor\frac {n - 2} {2} \rfloor$ enemies can be placed in such a way. For n=2 this is trivial, since there are no enemies at all.
Assume we have placed n criminals in such a way and the n+1 th criminal has to be seated. There are n ways to place him between the other criminals around the table. Count for each of these n places the number of enemies next to him. This number can be 0, 1 or 2. If it is 0, we found his place. Assume this is not possible. Then all numbers are at least 1. They sum up to a number M which is at least n. Since we count each enemy twice, the n+1 th criminal has exactly $\frac M 2$ enemies. But since M>=n this is at least $\frac n 2$ which is always more then $\lfloor\frac {n-1} {2} \rfloor$, which is the maximum of allowed enemies for n+1 criminals. So this is a contradiction and cannot happen.
Edit: Comment below shows that the proof in the given version is not correct.
-
$\begingroup$ I'm not entirely convinced. So we keep one criminal aside, and place the other 49 around the table. How can we be sure we can place those 49 around the table without adjacent enemies? Each may or may not have that 50th criminal as an enemy, and those that don't may still have 24 enemies amongst the group of 49. That means it does not necessarily reduce to the smaller case. One should always start with the generic $n+1$ case and reduce it to a valid $n$ case to show it can be built from there, otherwise mistakes can happen. $\endgroup$ Oct 18 at 13:20
-
$\begingroup$ @ Jaap Scherphuis: I think I understand your argument. My proof would only work if we were able to order the 50 criminals in such a way that the k+1 th criminal has at most Floor((k-1)/2) enemies with the first k criminals in that given order. And this this not obvious at all and even might be impossible. So I do not know if it is possible to fix the proof. And I wonder even more how 7 - 9 graders can solve the problem. $\endgroup$ Oct 18 at 13:42