In a meeting of $4042$ people, there are $2021$ couples, each consisting of two people. Suppose that $A$ and $B$, in the meeting, are friends when they know each other. For a positive integer $n$, each people chooses an integer from $-n$ to $n$ so that the following conditions hold. (Two or more people may choose the same number). Two or less people chose $0$, and if exactly two people chose $0$, they are coupled. Two people are either coupled or don't know each other if they chose the same number. Two people are either coupled or know each other if they chose two numbers that sum to $0$. Determine the least possible value of $n$ for which such number selecting is always possible.
Problem
Source: KJMO 2021 P6
Tags: combinatorics, graph theory
genius09
14.11.2021 14:51
The answer is 1347. Let each couple be $B_i, G_i$ for $1\leq i\leq2021$. If two people who are not coupled are friends we connect them by black edges, and otherwise connect them by white edges. Then the two color of edges form a clique of size $2021$ but the edges connecting couples are deleted. Also, the numbers of two people connected by a white edge are equal, and the sum of numbers of two people connected by a black edge is zero. Let $T_i$ be the subgraph of people who chose $-i$ or $i$ for $1\leq i\leq n$. If $T_i$ has a cycle which contains odd black edges, there would be odd times of sign changes while touring the cycle, which is contradiction. Hence $T_i$ should not contain a cycle with odd black edges. Step 1 $n=1347$ For $1\leq i\leq 673$, set $T_{2i-1}=\{B_{3i-2}, G_{3i-2}, B_{3i-1}\}, T_{2i}=\{G_{3i-1}, B_{3i}, G_{3i}\}$, and $T_{1347}=\{B_{2020}, G_{2020}\}, T_0=\{B_{2021}, G_{2021}\}$. You can easily show that this numbering always holds the condition for any graph. Step 2 $n\leq 1346$ Lets construct the graph by the following method: For $1\leq i < j \leq 2021$, $(B_i, B_j)$, $(G_i, G_j)$ and $(B_i, G_j)$ are friends(black edges), respectively. (Others are not friends, white edges) It is easy to prove that we should use two zeros to one couple. I will assume it as $B_{2021}, G_{2021}$. If there exists an integer $1\leq i\leq n$ such that $|T_i|\geq 4$, there are four cases. Case 1. $T_i$ contains three boys or three girls. Contradiction because they form a 3-cycle with all black edges. By case 1, we can conclude that $|T_i|=4$, and $T_i$ contains exactly two boys and two girls. Case 2. $T_i$ contains two couples. Let the two couples be $(B_i, G_i)$ and $(B_j, G_j)$ $(1\leq i<j \leq2020)$, then cycle $B_i, B_j, G_i, G_j$ contains three black edges, contradiction. Case 3. $T_i$ contains exactly one couple. Let $T_i=\{B_i, G_i, B_j, G_k\}$. $(B_i, B_k)$, $(G_i, G_k)$ are connected with black edges. If $(B_j, G_i)$ are friends, $j<i$. Since the 4-cycle should contain even black edges, $(B_i, G_k)$ are also friends, so $i<k$. Then $j<k$ and $(B_j, G_k)$ are friends, which is contradiction because of 3-cycle. If $(B_j, G_i)$ are not friends, $j>i$. Since the 4-cycle should contain even black edges, $(B_i, G_k)$ are also not friends, so $i>k$. Then $j>k$ and $(B_j, G_k)$ are not friends, which is contradiction because of 3-cycle. Case 4. $T_i$ does not contain couple. Let $T_i=\{B_i, B_j, G_k, G_l\}$. $(B_i, B_j)$, $(G_k, G_l)$ are connected with black edges. Because of 4-cycle, $(B_i, G_k)$ and $(B_j, G_l)$ are both friends or both not friends. If they are both friends, $(B_i, G_l)$ and $(B_j, G_k)$ are both not friends because of 3-cycle. Then $i<k<j<l<i$, contradiction. The other case also makes contradiction. Therefore, $|T_i|\leq 3$ for all $1\leq i\leq 2020$. However, $4040=\sum_{i=1}^{n}|T_i|\leq 3n\leq 4038$, contradiction. It means it is impossible to choose the numbers to satisfy the conditions. $\therefore n=1347$
EagleEye
03.12.2021 05:31
To get rid of misunderstanding, I think the translation of the last line should be Quote: Determine the least possible value of $n$ which such number selecting is possible in any circumstance of friendship in the meeting.