Maths Olympiad Prep

Library / /96 of 101

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it Estonia

Let n2n \ge 2 be a natural number. Laura's mathematics teacher likes group exercises. In Laura's class the teacher composed new groups in every lesson of statistics. When all of the statistics curriculum had been covered, it appeared that every two different students had belonged together into exactly one group and every two different groups had contained exactly one student in common. On the day when correlation was studied there were precisely nn students besides Laura in her group. How many students were in Laura's class if their number was larger than n+2n + 2?

Answer: n2+n+1n^2 + n + 1.

Solution

By assumptions, one group contained n+1n + 1 students while the whole class contains more than n+2n + 2 students. As every two students belonged together into one group, more than one groups with more than one members must have occurred. If some group contained only one student CC, this student must have belonged to every group while every other student must have belonged to exactly one group (the one where the student was together with CC). But this would mean that there was only one group with more than one student which contained the whole class. Consequently groups with only one member cannot have occurred. Consider two cases.

1) Suppose that there were two groups such that each student belonged to at least one of them. Let CC be the student that belonged to both of these two groups and let these groups be {C,A1,,Ak}\{C, A_1, \dots, A_k\} and {C,B1,B2,,Bl}\{C, B_1, B_2, \dots, B_l\}. As every pair of different students is together in exactly one group, the other groups must have had to be of the form {Ai,Bj}\{A_i, B_j\} where i=1,2,,ki = 1, 2, \dots, k and j=1,2,,lj = 1, 2, \dots, l, whereby all such groups must have occurred. As these groups have to pairwise share one student we have either k=1k=1 or l=1l=1. Let w.l.o.g. k=1k=1. As Laura's group on the day of correlation studies contained n+1n+1 students while n+1>n2n+1 > n \ge 2, this must have been the large group with l+1l+1 students. Thus l=nl=n and the total number of students is n+2n+2. But it is given that the total number of students has to be bigger than that.

2) Suppose now that there were no two groups such that every student belonged to at least one of them. We prove that there was an equal number of students in each group. Let R\mathcal{R} and S\mathcal{S} be arbitrary groups formed and let CC be an arbitrary student contained by neither of them. Let mm be the number of groups that contain CC. Each of these mm groups has exactly one student in common with R\mathcal{R}; all these students are distinct as CC is the only common member of every two groups containing CC. There can be no more students in R\mathcal{R} because every student in R\mathcal{R} must belong to some group together with CC. Hence R\mathcal{R} contained exactly mm students. Analogously we see that S\mathcal{S} contains exactly mm students. As R\mathcal{R} and S\mathcal{S} were arbitrary, it follows that each group contains exactly mm students. As on the day of studying correlation there were n+1n+1 students in Laura's group, we have m=n+1m = n+1. We can find the size of the class by only considering CC's groups: there are n+1n+1 of them and each contains nn students besides CC, whence we have 1+(n+1)n1 + (n+1)n students in total. This is indeed more than n+2n+2 and suits as the answer.

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 and solution reproduced as published; topic and difficulty added by this site.