In the class, there are $ 15$ boys and $ 15$ girls. On March $ 8$, some boys made phone calls to some girls to congratulate them on the holiday ( each boy made no more than one call to each girl). It appears that there is a unique way to split the class in $ 15$ pairs (each consisting of a boy and a girl) such that in every pair the boy has phoned the girl. Find the maximal possible number of calls.
Problem
Source: Russian 2007
Tags: linear algebra, matrix, induction, graph theory, combinatorics proposed, combinatorics
06.09.2007 14:33
For a class with $ N$ boys and $ N$ girls, the maximal number of calls is $ \frac{N\left(N+1\right)}{2}$. If more calls are made, the partition is not unique. Consider the boys numbered in any order as $ b_{1},b_{2},...,b_{N}$, and the girls numbered as $ g_{1},g_{2},...,g_{N}$, so that boy $ b_{i}$ is paired up with girl $ g_{i}$ in the unique partition, for all $ i=1,2,3,...,N$. Consider now an $ N\times N$ matrix such that, in position $ \left(i,j\right)$, a 1 is placed iff boy $ b_{i}$ called girl $ g_{j}$. Obviously, the diagonal has all 1's since boy $ b_{i}$ called girl $ g_{i}$ for all $ i=1,2,...,N$ (since they are paired). Now, positions $ \left(i,j\right)$ and $ \left(j,i\right)$ cannot both have 1 for any $ i\neq j$, since otherwise boy $ b_{i}$ could also be paired up with girl $ g_{j}$, and boy $ b_{j}$ with girl $ g_{i}$, making the partition not unique. So, out of the $ N^{2}-N$ elements not in the main diagonal of the matrix, at most half have 1's. The total number of ones (and hence of phone calls) is then no larger than $ N+\frac{N^{2}-N}{2}=\frac{N\left(N+1\right)}{2}$. Assume now that, for any ordering of boys as $ b_{1},b_{2},...,b_{N}$, and girls as $ g_{1},g_{2},...,b_{N}$, boy $ b_{i}$ called exactly the $ i$ girls numbered as $ g_{1},g_{2},...,g_{i}$. It is a trivial exercise in induction to prove that boy $ b_{i}$ is then paired up with girl $ g_{i}$ in the unique possible partition. So for exactly $ \frac{N\left(N+1\right)}{2}$ calls the partition is unique, and this is the maximal number that we were looking for.
06.09.2007 15:06
06.09.2007 15:58
I give in detail the next example of $ \frac{15\cdot16}{2}= 120$ phone calls: $ b_{i}$ makes $ i$ calls: he calls $ g_{1},g_{2},...,g_{i}$. The sum of these calls is then $ 1+2+...+15 = 120$. Now, $ b_{1}$ can only be paired with $ g_{1}$, since he didn't call any other girl. $ b_{2}$ called $ g_{1}$ (already taken) and $ g_{2}$, and no other girl. So he can only be paired with $ g_{2}$. $ b_{3}$ called $ g_{1}$ (taken), $ g_{2}$ (taken) and $ g_{3}$, and no other girl. So he can only be paired with $ g_{3}$. And so on, until $ b_{15}$, who called all the girls, but can be paired only with $ g_{15}$, since all other girls are already taken. So the partition is unique... or so it seems to me. Could you be so kind as to point where my mistake lies? Thanks in advance...
06.09.2007 16:13
You are obviously right sorry, I made a stupid mistake , the cyclic thing is completely wrong.
06.09.2007 16:21
No need to be sorry, it is good to have somebody look at your solutions critically (otherwise if a real mistake was made, I could have never known about it). So actually, thanks...