Maths Olympiad Prep

Library / /42 of 61

Combinatorics Difficulty 6.9 National Olympiad Prove it Canada

Problem:

At a dinner party there are NN hosts and NN guests, seated around a circular table, where N4N \geq 4. A pair of two guests will chat with one another if either there is at most one person seated between them or if there are exactly two people between them, at least one of whom is a host. Prove that no matter how the 2N2N people are seated at the dinner party, at least NN pairs of guests will chat with one another.

Solution

Solution:

Let a run refer to a maximal group of consecutive dinner party guests all of whom are the same type (host or guest). Suppose that there are exactly kk runs of hosts and kk runs of guests. Let GiG_{i} and HiH_{i} denote the number of runs of guests and hosts, respectively, of length exactly ii. Furthermore, let XX denote the number of hosts surrounded by two runs of guests, both of length exactly 11. We claim that the number of pairs of guests who chat is at least
2N3k+G1+2H1+H2X 2N - 3k + G_{1} + 2H_{1} + H_{2} - X
The number of pairs of guests who chat with no host between them is at least the sum of max{23,0}\max\{2\ell - 3, 0\} over all guest run lengths \ell. This sum is at least 2N3k+G12N - 3k + G_{1}. The number of pairs of guests who chat with exactly two hosts between them is H2H_{2}. Furthermore, the number of pairs of guests who chat with exactly one host between them is at least 2H1X2H_{1} - X. This is because any host surrounded by two runs of guests causes at least two pairs of guests to chat unless these runs are both of length exactly 11. This proves the claim. Now note that
2H1+H2+N3k 2H_{1} + H_{2} + N \geq 3k
because each run of hosts contributes at least three to the left hand side. Furthermore, pairing each run counted in XX with the guest run of length 11 immediately following it in clockwise order shows that G1XG_{1} \geq X. Combining these inequalities yields that 2N3k+G1+2H1+H2XN2N - 3k + G_{1} + 2H_{1} + H_{2} - X \geq N, completing the proof of the desired result.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.