2
$\begingroup$

A company has $100$ employees. The company together has $101$ work teams. A work team consists of $3$ employees. An employee is allowed to participate in multiple work teams. Two different work teams have at least one employee, not in common. Prove that there can be found $2$ work teams such that they have only one employee in common.

The only useful thing I have found out is that it is possible to make $98$ work teams from $100$ employees such that every team has $2$ people or no people in common. I suspect it is possible to make $100$ but I haven't found such a configuration. I feel that the crux move of the problem is to show that $101$ work teams are the smallest number of teams for which it is guaranteed that only one common person will be found.

Any ideas?

$\endgroup$
  • 1
    $\begingroup$ What attempts have you made? How far have you gotten with them? $\endgroup$ – saulspatz Oct 12 '19 at 16:32
  • $\begingroup$ The only useful thing I have found out is that it is possible to make 98 work teams from 100 employees such that every team has 2 people or no people in common. I suspect it is possible to make 100 but I haven't found such a configuration. I feel that the crux move of the problem is to show that 101 work teams are the smallest number of teams for which it is guaranteed that only one common person will be found. $\endgroup$ – Niks Topics Oct 12 '19 at 16:40
  • $\begingroup$ You should add these thoughts to the body of the question. You get a much better response when you show you've actually tried to do the problem yourself. That is, more help and fewer votes to close. $\endgroup$ – saulspatz Oct 12 '19 at 16:41
2
$\begingroup$

This is a special case of what's commonly known as the Oddtown problem: a family of subsets of $\{1,2,\dots,n\}$ where every set has odd size, but every two sets intersect in an even number of elements, can have at most $n$ sets. Conversely, given a family of $n+1$ sets of odd size, two of them must have an odd intersection.

The complete solution to the Oddtown problem is given in an answer to the question I linked to above.

In the special case of this problem, every set (work team) has three elements (employees). If $n=100$ but there are $101$ sets in the family, two of them must have an odd intersection. We forbid work teams from sharing all three employees, so this must mean that two work teams share exactly one employee.


Here's a non-linear algebra solution. We assume that no two work teams have exactly one employee in common, and show that there's at most $100$ teams.

The key lemma is that "share $2$ members in common" must be transitive. If teams $A$ and $B$ share two employees, and so do teams $B$ and $C$, then both $A$ and $C$ contain two of $B$'s three members, so they overlap in at least $1$ employee: and therefore in two.

So we can split up the work teams into connected components, so that any two teams in each component share $2$ employees, and teams in different components share no employees. Now we show that if a component has $k$ teams, those teams together must include at least $k$ employees.

There are two kinds of components:

  1. We could have a component where the same $2$ employees are in each work team. Then the third employee in the work team must be a separate one each time, and so we have $k$ teams with $k+2$ employees.
  2. For every two employees, there's a team in the component that doesn't include both. Let $\{a,b,c\}$ and $\{a,b,d\}$ be two teams. There must be a team that doesn't include both $a$ and $b$; then it must have both $c$ and $d$, and it ends up being one of $\{a,c,d\}$ or $\{b,c,d\}$. Now there's no way to add a team with a fifth employee to the component; it will have an intersection less than $2$ with one of these teams. The best we can do is add the other one of $\{a,c,d\}$ or $\{b,c,d\}$, giving us $4$ teams with $4$ employees.

So now in each component there's at least as many employees as teams, and therefore overall there's at least as many employees as teams: for $101$ teams we'd need $101$ employees, which is a contradiction.

$\endgroup$
  • $\begingroup$ Is there a good way to solve it without linear algebra? $\endgroup$ – Niks Topics Oct 12 '19 at 21:07
  • $\begingroup$ In the general case, I don't think so. There might be a special argument in the case where all sets in the family have size $3$. $\endgroup$ – Misha Lavrov Oct 12 '19 at 22:05
  • $\begingroup$ I understand the proof using linear independence, but this is a problem from a highschool level math competition, so that is why I was wondering if there is a simpler proof for the concrete example. $\endgroup$ – Niks Topics Oct 12 '19 at 22:08
  • $\begingroup$ @NiksTopics Here's a purely combinatorial argument. $\endgroup$ – Misha Lavrov Oct 12 '19 at 23: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.