In a school with $2022$ students, either a museum trip or a nature trip is organized every day during a holiday. No student participates in the same type of trip twice, and the number of students attending each trip is different. If there are no two students participating in the same two trips together, find the maximum number of trips held.
Problem
Source: Turkey National Mathematical Olympiad 2022 P6
Tags: combinatorics, graph theory
24.12.2022 01:11
The answer is $77$. Example for $77$ trips: $52$ nature trips that consists of $1,2,3,...,25,52,53,54,...,77$ students and total of $2002$ students participated in these trips. $25$ museum trips that consist of $26,27,28,...51$ students The trip with $26 + i$ ($0\le i<26$)students has $1$ student from each nature trip with more than $25-i$ students Proof of we can't plan $78$ trips : Assume otherwise, and we can assume trips have exactly $1,2,...,78$ students. Let $t_i$ be the trip with $i$ students. Look at $t_{30},t_{31},...,t_{78}$. We counted total of $(30+31+...+78) = 2646 = 2022 + 624$ students and each student have appeared less than $3$ times. We counted at least $624$ students two times. However, let's construct a graph with vertices $t_{30},...t_{78}$ and draw and edge between two vertices if a student participated in both of them. Notice that graph is bipartite since there is no edge between two nature trips and two museum trips. So the maximum number of edge is $24*25=600$ when the graph is $K_{24,25}$ Each edge was representing a student that we counted two times in $t_{30},...,t_{78}$. So $624\le$ number of students counted two times$\le 600$, a clear contradiction. Hence we cannot plan more than $77$ trips