MHB Problem of the Week # 222 - Jun 29, 2016

[Ackbach]

Here is this week's POTW:

-----

Suppose that each of 20 students has made a choice of anywhere from 0 to 6 courses from a total of 6 courses offered. Prove or disprove: there are 5 students and 2 courses such that all 5 have chosen both courses or all 5 have chosen neither course.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 222 - Jun 29, 2016

This was Problem A-3 in the 1996 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

The claim is false. There are $\binom{6}{3} = 20$ ways to choose 3 of the
6 courses; have each student choose a different set of 3 courses. Then
each pair of courses is chosen by 4 students (corresponding to the
four ways to complete this pair to a set of 3 courses) and is not
chosen by 4 students (corresponding to the 3-element subsets of the
remaining 4 courses).

Note: Assuming that no two students choose the same courses,
the above counterexample is unique (up to permuting students).
This may be seen as follows: Given a group of students, suppose that
for any pair of courses (among the six) there are at most 4 students
taking both, and at most 4 taking neither. Then there are at most
$120=(4+4)\binom{6}{2}$ pairs $(s,p)$, where $s$ is a student, and $p$
is a set of two courses of which $s$ is taking either both or none.
On the other hand, if a student $s$ is taking $k$ courses, then he/she
occurs in $f(k)=\binom{k}{2}+\binom{6-k}{2}$ such pairs $(s,p)$. As
$f(k)$ is minimized for $k=3$, it follows that every student occurs in
at least $6=\binom{3}{2}+\binom{3}{2}$ such pairs $(s,p)$. Hence
there can be at most $120/6=20$ students, with equality only if each
student takes 3 courses, and for each set of two courses, there are
exactly 4 students who take both and exactly 4 who take neither.
Since there are only 4 ways to complete a given pair of courses to a
set of 3, and only 4 ways to choose 3 courses not containing the given
pair, the only way for there to be 20 students (under our hypotheses)
is if all sets of 3 courses are in fact taken. This is the desired conclusion.