At a dinner party there are N hosts and N guests, seated around a circular table, where N≥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 2N people are seated at the dinner party, at least N 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 k runs of hosts and k runs of guests. Let Gi and Hi denote the number of runs of guests and hosts, respectively, of length exactly i. Furthermore, let X denote the number of hosts surrounded by two runs of guests, both of length exactly 1. We claim that the number of pairs of guests who chat is at least 2N−3k+G1+2H1+H2−X The number of pairs of guests who chat with no host between them is at least the sum of max{2ℓ−3,0} over all guest run lengths ℓ. This sum is at least 2N−3k+G1. The number of pairs of guests who chat with exactly two hosts between them is H2. Furthermore, the number of pairs of guests who chat with exactly one host between them is at least 2H1−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 1. This proves the claim. Now note that 2H1+H2+N≥3k because each run of hosts contributes at least three to the left hand side. Furthermore, pairing each run counted in X with the guest run of length 1 immediately following it in clockwise order shows that G1≥X. Combining these inequalities yields that 2N−3k+G1+2H1+H2−X≥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.