2
$\begingroup$

Suppose a person has 7 friends, whom he wants to invite for dinner over a week. Here are the rules:

  • Each night, exactly 3 people will be invited.
  • Any pair of friends is invited on at most one common night. Namely for any $i \neq j$, $i$ and $j$ can both be invited only on at most one night.

How many possible ways are there to achieve this task? Any help is appreciated.

[I've tried to argue via subsets of a set. Here is an interpretation. Take any 7-element set $A$, we want to count the number of 7-element sets $B$ where for each $B_i\in B$, $B_i$ is a 3-element subset of $A$, and for any $i\neq j$, $|B_i\cap B_j|\leq 1$. Once we have all such sets, we basically need to multiply the total number of all such $B$'s by $7!$].

$\endgroup$
2
$\begingroup$

Each friend will come over $3$ times, each time with disjoint sets from the other $6$. For example, $A$ could be invited in the groups $ABC$, $ADE$, and $AFG$. After that, $A$ can't come over anymore, and we get to decide how $B$ comes over again. They have to avoid $C$, so we could do $BDF$ and $BEG$, or else $BDG$ and $BEF$. Whichever pairs accompany $B$, different pairs must accompany $C$ on their next two visits: If we chose $BDF$, $BEG$, then we have to choose $CDG$, $CEF$. Now we have filled the week.

Thus, we need to count up how many ways $A$ could be matched with other pairs: $\frac{\binom{6}{2}\binom{4}{2}}{3!}=15$, and multiply by $2$ for the two ways we have of handling $B$'s next two visits. That gives us a total of $30$.


This solution counts the number of ways to choose the dinner parties. If we also need to choose how to arrange them among the seven days of the week, then we need to multiply by $7!=5040$, for a total of $151200$.

$\endgroup$
  • $\begingroup$ Does order matter? In that case, one must multiply by $7!$. $\endgroup$ – jvdhooft May 17 '17 at 20:07
  • $\begingroup$ Good point. My answer calculates the number of ways to choose the dinner parties, but not the number of ways to arrange them on the calendar. $\endgroup$ – G Tony Jacobs May 17 '17 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.