Maths Olympiad Prep

Library / /18 of 31

, 2023

Combinatorics Difficulty 8.1 Shortlist Prove it Saudi Arabia

An academic club of 20232023 members wants to organize some seminars. In each seminar, each member of the club will present exactly one of three subjects: Math, Physics, and Chemistry. It is given that for any two members, there exists some seminar where they do not present the same subject. Find the smallest possible value of the number of seminars.

Solution

Let kk be the number of seminars the club can organize. In the ii-th seminar with 1ik1 \le i \le k, denote AiA_i, BiB_i, CiC_i as the collection of participants presenting Math, Physics, Chemistry respectively. Then, for each ii, we have AiA_i, BiB_i, CiC_i are the partition of the members of the club. Replace 2023n2023 \to n.

In each seminar, the members will have 33 ways to choose subjects to present, so there will be 3k3^k ways to choose in total. If 3k<n3^k < n then, according to the pigeonhole principle, there will be two members who must have the same choice in all kk seminars. However, the two members will always present the same subject for every seminar, contradiction. So there must be n3kn \le 3^k.

We will show that for n3kn \le 3^k it is always possible to construct. Indeed, converting the members' numbers from 0,1,2,,n10, 1, 2, \ldots, n-1 to base 33, each number will correspond to a ternary string of length no more than kk. To synchronize those strings, we add 00 in front so that all strings have the same length kk. We define the following rule: in the iith seminar with 1ik1 \le i \le k, all members having 00 at position ii on their string will present Math, similarly, the same 11 for Physics and the same 22 for Chemistry.

Note that any two strings are different, so they must be different at a certain position, and the index of that position will be the index of the seminar in which the two respective members present 22 different subjects, satisfying the constraint.

For n=2023n = 2023, we have klog32023=7k \ge \lceil \log_3 2023 \rceil = 7 and k=7k = 7 is the minimum value. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.