Skip to main content
OlympiadHQ

Browse · MathNet

Print

Belarusian Mathematical Olympiad

Belarus counting and probability

Problem

Every one of six pupils attends exactly two of four hobby groups. There are no pupils attending the same two hobby groups. Each hobby group is open every day. During some consecutive days, every one of these six pupils has attended one of her/his hobby group. It has been observed that each of these days each hobby group has been attended by either one or two of the pupils. Moreover, for any chosen two days, there has been a pupil who has attended different hobby groups during these two days. Find the largest number of the days for which the situation described above is possible.
Solution
Answer: 24 days. Note that from four hobby groups one can form exactly different pairs. Since we have exactly six pupils, for each pair of the hobby group there exists exactly one pupil attending just these two hobby groups. By condition, each hobby group is attended by either one or two pupils and there are exactly four hobby group, so in each of these days there are exactly two hobby groups attended by two pupils and there are exactly two hobby groups attended by one pupil.

Consider arbitrary day. Let this day hobby group and be attended by two pupils. Since, as was shown above, there is a pupil attending just these two hobby groups, without loss of generality we can assume that this pupil has attended hobby group . Each of two remained hobby groups and has been attended by one pupil. Again, there exists a pupil attending just these hobby groups and . Suppose that this pupil has attended hobby group . Show that this information is sufficient to uniquely indicate for each hobby group who of the pupils has attended this hobby group.

Since in the considered day hobby group has been attended by exactly one pupil (this pupil attends hobby groups and ), the pupil attending and has attended hobby group , and the pupil attending and has attended hobby group . Further, since hobby group has been attended by two pupils (one of them attends hobby groups and , and the other one attends hobby group and ), the pupil attending and has attended hobby group . Finally, the pupil attending hobby groups and has attended hobby group , since hobby group has been attended by exactly one pupil attending hobby groups and .

We have exactly ways to choose the pair that have been attended by two pupils, and for each such pair we have two ways to fix the hobby group has been attended by the pupil attending just these two hobby groups. For hobby groups and we have two ways to choose the hobby group that has been attended by the pupil attending these hobby groups and . Thus, we obtain different days in total.
Final answer
24

Techniques

Recursion, bijectionCounting two ways