There are two round tables with $n{}$ dwarves sitting at each table. Each dwarf has only two friends: his neighbours to the left and to the right. A good wizard wants to seat the dwarves at one round table so that each two neighbours are friends. His magic allows him to make any $2n$ pairs of dwarves into pairs of friends (the dwarves in a pair may be from the same or from different tables). However, he knows that an evil sorcerer will break $n{}$ of those new friendships. For which $n{}$ is the good wizard able to achieve his goal no matter what the evil sorcerer does? Mikhail Svyatlovskiy
Problem
Source: 42nd International Tournament of Towns, Junior A-Level P6 & Senior A-Level P4, Fall 2020
Tags: combinatorics, Tournament of Towns
18.02.2023 17:34
Answer: for odd $n$. Number the dwarves sitting at the first table $1, 2, \dots, n$ and sitting at the second table $1', 2', \dots, n'$ by their order. That is, $(1, 2), (2, 3), \dots, (n-1, n), (n, 1), (1', 2'), (2', 3'), \dots, (n-1', n'), (n', 1')$ are friends. For convenience, define $n+k$ as $k$ and $n+k'$ as $k'$ for any $k$. For $2\nmid n$, the wizard can make the $2n$ pairs: $(i, i+1')$ and $(i+1, i')$ for all $i=1, 2, \dots, n$. If the sorcerer doesn't want wizard to achieve the goal, $\forall i$, one of $(i, i-1')$ or $(i+1, i')$ should be broken, and one of $(i-1, i'), (i, i+1')$ should be broken. $\Rightarrow$ at least $\lceil\frac n2\rceil$ elements of $\{(i, i-1')|i=1, 2, \dots, n\}$ and at least $\lceil\frac n2\rceil$ elements of $\{(i, i+1')|i=1, 2, \dots, n\}$ should be broken. $\Rightarrow$ at least $2\lceil\frac n2\rceil=n+1$ friendships should be broken, which is impossible. $\therefore$ the wizard always achieves the goal when $n$ is odd. For $2|n$, split the dwarves into $4$ groups: $A=\{1, 3, \dots, n-1\}, B=\{2, 4, \dots, n\}, C=\{1', 3', \dots, n-1'\}, D=\{2', 4', \dots, n'\}$. $\because$ each new friendship can be related to at most $2$ groups. $\therefore$ by pigeonhole principle, $\exists$ a group that is related to at most $\frac{2\times2n}4=n$ new friendships. $\Rightarrow$ the sorcerer can cut $n$ new friendships to make all dwarves in a group having no new friendships. WLOG suppose that group is $A$. In the new arrangement, all dwarves in $A$ need to seat adjacent to dwarves in $B$. Since $|B|=|A|$, all dwarves in $B$ need to seat adjacent to dwarves in $A$. $\Rightarrow$ none of dwarves of $A$ or $B$ can seat adjacent to those in $C$ or $D$, and therefore the wizard fails.
09.03.2023 18:34
A generalised version of the problem appeared in Kvant Magazine No. 11-12 2020 M2633. It's the same, with $k{}$ instead of two: There are $k{}$ round tables with $n{}$ dwarves sitting at each table. Each dwarf has only two friends: his neighbours to the left and to the right. A good wizard wants to seat the dwarves at one round table so that each two neighbours are friends. His magic allows him to make any $kn$ pairs of dwarves into pairs of friends (the dwarves in a pair may be from the same or from different tables). However, he knows that an evil sorcerer will break $n{}$ of those new friendships. For which $n{}$ is the good wizard able to achieve his goal no matter what the evil sorcerer does?