At the beginning of school year in one of the first grade classes: $i)$ every student had exatly $20$ acquaintances $ii)$ every two students knowing each other had exactly $13$ mutual acquaintances $iii)$ every two students not knowing each other had exactly $12$ mutual acquaintances Find number of students in this class
Problem
Source: Regional Olympiad - Federation of Bosnia and Herzegovina 2014
Tags: combinatorics, acquaintance
24.09.2018 15:04
Let there be $n$ students. First observe that there are $10n$ pairs of acquaintances. Each pair contributes 1 to the count of acquaintances of both students in it. Since each student has 20 acquaintances, the sum of counts of acquaintances is $20n$; since each pair contributes 2 to this, the claim follows. A common triple is defined as a triple of students $(A,B,C)$ such that A-B and B-C are pairs of acquaintances. (A-C may or may not be a pair of acquaintances.) $(A,B,C)$ and $(C,B,A)$ are considered the same triple. We will count the number of common triples. On one hand, we can fix B and count the number of common triples for a fixed B. Since each student has 20 acquaintances, we have $\binom{20}{2} = 190$ ways to choose A and C given a fixed B, so summing over all B gives $190n$ common triples in total. On the other hand, we can look from the pairs A-C, depending on whether it's a pair of acquaintances or not. If A-C are acquaintances, by condition ii) there are exactly 13 possible B. Since there are $10n$ possible A-C, there are in total $130n$ common triples counted here. If A-C are not acquaintances, by condition iii) there are exactly 12 possible B. The number of non-acquaintances is $\binom{n}{2} - 10n = \frac{n-21}{2} n$ by complementary counting, and thus there are $6(n-21) \cdot n$ common triples counted here. In total, there are $130n + 6(n-21) \cdot n = (6n+4)n$ common triples. Since the two numbers should be equal, we have $190n = (6n+4)n$. Assuming the number of students is positive, this means $n > 0$, so $190 = 6n+4$ or $n = \boxed{31}$.