At a party there are eight guests, and each participant can't talk with at most three persons. Prove that we can group the persons in four pairs such that in every pair a conversation can take place.
Problem
Source: Romanian JBTST V 2007, problem 3
Tags: graph theory, combinatorics proposed, combinatorics
07.06.2007 17:18
Hmm.. I think there is a straightforward proof but is it not a direct consequence of Hall's theorem? Pierre.
09.06.2007 15:53
pbornsztein wrote: Hmm.. I think there is a straightforward proof but is it not a direct consequence of Hall's theorem? Pierre. Hall's theorem only applies to bipartite graphs.
09.06.2007 16:25
Groumpf.. Well, the graph whose vertices are the persons and any edge connect two of them if and only if they can have a conversation has an hamiltonian cycle, because each vertex has degree at least $4$, so that it satisfies Dirac's condition. To find the desired pairing, you only have to cut the hamiltonian cycle into appropriate pairs. Pierre.
10.06.2007 02:16
Here's another (clumsier) way: Suppose that no such grouping exists; that is, every grouping has at least one pair of people who can't talk to each other. We show that at least one person can't talk to more than 3 people. Call a pair of people "forbidden" if they can't talk to each other. There are $\frac{{{8}\choose{2}}{{6}\choose{2}}{{4}\choose{2}}}{4!}= 105$ possible groupings. Label the people from 1 to 8. WLOG assume that 1 and 2 can't talk to each other. There are $\frac{{{6}\choose{2}}{{4}\choose{2}}}{3!}=15$ groupings that contain the pair (1 2). Similarly, there 15 - 3 = 12 additional groupings that contain the pair (3 4), 10 additional groupings containing the pair (5 6), and 8 additional groupings that contain the pair (7 8). We continue the process of constructing "forbidden" pairs until every person can't talk with 3 other people. Eventually we find that there are 15+12+10+8+10+7+5+3+5+5+5+5+5+5 = 100 groupings containing these pairs (just some counting). But there are 105 groupings in total, so there is at least one more "forbidden" pair. Contradiction.
26.12.2011 04:17
see here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=151&t=47785&