A certain organization has $n$ members, and it has $n+1$ three-member committees, no two of which have identical member-ship. Prove that there are two committees which share exactly one member.
Problem
Source: USAMO 1979 Problem 5
Tags: modular arithmetic, AMC
basketball9
25.07.2011 05:05
Unless I am missing something if $[n]$ has $3n$ distinct elements this problem does not work. ???
basketball9
25.07.2011 05:08
I looked it up and I think found the problem in the statement. There should be $n$ elements in $[n]$ and $n+1$ subsets to consider.
djmathman
25.07.2011 05:15
So the last subset should be $A_{n+1}$ then, right?
Mewto55555
25.07.2011 05:41
Define $f(i)$ to be the number of subsets that the element $a_i$ is in.
Note that $\sum_{i=1}^n{f(i)}=3n+3$
Thus, there exist $2n+3$ (an odd number) of "sharings" (3n+3 minus the n total elements). Thus, there exists an odd number (and therefore, non-zero number) of pairs $i,j$ such that $|A_i \cap A_j|$ is an odd number. As $|A_i \cap A_j|<3$, there must exist at least one pair $(i,j)$ such that $|A_i \cap A_j|=1$
McTeague
26.07.2014 22:36
I was thinking of something similar to what Mewto55555 suggested, though most sources that I look at use an inductive approach that seems more laborious. Did I underthink this?:
Assume for contradiction that for any two committees, they are either disjoint or have two members in common. There are $n+1$ of $3$-member committees, implying $3n+3$ committee members (counting repeats of people). To compensate for the overcounting of organization members in multiple committees, we consider two such committees both containing the same person, call him $A$. Then since each committee has either $2$ or $0$ people in common, there is exactly one other person, $B$, in the two same committees, i.e., the committees look like $\{A,B,C\}$ and $\{A,B,D\}$. Then we can compensate for overcounting by subtracting $2$ from our count of $3n+3$, to account for the duplicate occurrences of $A$ and $B$.
We can continue this for each occurrence of an organization member in multiple committees. Assume we subtract $k$ times to get the count of $n$ organization members. Then we have $3n+3-2k = n$, however, taking this $\pmod{2}$, we get $0 \equiv 1 \pmod{2}$, a contradiction, so that some two committees share exactly one member.
MSTang
26.07.2014 23:20
@McTeague: I think the problem is that it is not guaranteed that each of the $n$ members is in at least one committee. For example, we could have $n = 6$ members $A, B, C, D, E, F$ and the $n + 1 = 7$ committees $BCD, BCE, BCF, BDE, BDF,$ and $BEF$, where $A$ is not in any committee. This means that after you finish subtracting $2$s from your count of $3n+3$, you might not end up with $n$ members - in the above example you would get $n - 1 = 5$.
McTeague
27.07.2014 01:16
Ah, thanks. Actually, since not using an organization member in a committee would be in some sense "wasteful", maybe instead consider the scenario where $r \le n$ people are in the $n+1$ committees. Then look at a subset of the set of committees, consisting of $r+1$ committees. I think we could then go through the same argument, with $3r+3$ committee people, once again counting duplicates, and then subtracting $k$ times, $3r+3-2k = r$, which again leads to a contradiction $\pmod 2$.