The following is true for n guests at a Christmas party:
1) In any group of three guests, there are two people who do not know each other
2) In any group of seven guests, there are two people who do know each other
At the end of the party, everyone gives gifts to those that they know. Prove that the total number of gifts given is at most 6n.
My attempt:
Suppose that everyone at the party knows one another. I believe that the total number of connections at the party would be $n^2$ - $n$. So my next step would be to subtract the number of connections based on the fact that 2 out of 3 guests do not know each other. At this point, we probably overcounted connections and need to add those back based on the fact that 2 out of 7 people do know each other. Is this somewhat the right idea?
Suppose there are more than $6n$ gifts.
Then there is a person, which we shall call $A$, that knows at least $7$ persons, say $A_1,A_2,A_3,A_4,A_5,A_6,A_7$.
None of these persons can know each other, since if $A_i$ knows $A_j$ then $A,A_i,A_j$ all know each other (which contradicts condition $1$)
Therefore $A_1,A_2,A_3,A_4,A_5,A_6,A_7$ are $7$ persons such that none of them know each other. This contradicts condition $2$.
We conclude at most $6n$ gifts can be given.