Olympiad Maths Prep

Library / /4 of 4

Combinatorics Difficulty 6.8 National olympiad Prove it Turkey

A school with 20232023 pupils organized either a museum tour or a nature tour every day during the summer holidays. No pupil participated in the same type of tour twice, and all tours were attended by different numbers of pupils. If no two pupils participated in two different tours together, find the maximal possible value of the total number of tours.

Solution

Answer: 7777.

First of all, let us give an example for 7777 tours. Let us take 26×77=200226 \times 77 = 2002 school pupils and divide them into groups AA and BB consisting of 26×51=132626 \times 51 = 1326 and 26×26=67626 \times 26 = 676 pupils, respectively. To each pupil from AA we assign a different pair from the set
A={(i,j):i,jZ+,i+j52} A = \{(i, j) : i, j \in \mathbb{Z}_+, i + j \leq 52\}
To each pupil from BB we assign a different pair from the set
B={(i,j):i,jZ+,i26,j26}. B = \{(i, j) : i, j \in \mathbb{Z}_+, i \leq 26, j \leq 26\}.
Now for each 1k771 \leq k \leq 77 in the kk-th day:

† if k51k \leq 51 then kk pupils from the group AA for which i=52ki = 52 - k attend a museum tour,

†† if k52k \geq 52 then kk pupils from the groups AA and BB for which j=78kj = 78 - k attend a nature tour.

It can be readily seen that all conditions of the problem are fulfilled.

Now we show that if an nn days program satisfies the conditions then n77n \leq 77. Let us consider 5252 tours with largest numbers of pupils: M1,M2,,Mk,Nk+1,,N52M_1, M_2, \dots, M_k, N_{k+1}, \dots, N_{52} (here each MiM_i denotes a pupil group attending a museum tour and NiN_i denotes a pupil group attending a nature tour). By conditions MiNj1|M_i \cap N_j| \leq 1 and for iji \neq j we have MiMj=0|M_i \cap M_j| = 0 and NiNj=0|N_i \cap N_j| = 0. Therefore,
Mi+Ni \sum |M_i| + \sum |N_i|
=M1MkNk+1N52+MiNj = |M_1 \cup \dots \cup M_k \cup N_{k+1} \cup \dots \cup N_{52}| + \sum |M_i \cap N_j| \leq
2022+k(52k)2698<26104 2022 + k(52 - k) \leq 2698 < 26 \cdot 104
On the other hand, since all tours were attended by different numbers of pupils, we get
Mi+Din+(n1)++(n51)=(2n51)26 \sum |M_i| + \sum |D_i| \geq n + (n-1) + \dots + (n-51) = (2n-51) \cdot 26
Therefore, 2n51<1042n-51 < 104 and hence n77n \leq 77.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.