Yet another question from BdMO 2013 Nationals:
In a class,every boy knows $r$ number of girls and every girl knows $r$ number of boys.Show that there are equal number of boys and girls[Assume that friendship is symmetric i.e. if A knows B then B knows A].
This question was set in the Secondary section of the Nationals.In the Junior Section,a similar but easier question came.
In a class,every boy knows $3$ number of girls and every girl knows $3$ number of boys.If there are 13 boys,find the number of girls in the class.
I solved this question by noting that (i)If there are 3 number of boys in the class,then number of girls also has to be 3. (ii)If there are 4 boys,required number of girls is also 4.This gives us the required tool to solve the problem.We just have to note that
$13$ boys=$(3+3+3)+4$ boys
For every 3 boys,we need 3 girls[From (i)]. Hence,(3+3+3) boys implies that there are $3+3+3=9$ girls.From (ii),we know that if there are 4 boys,we need 4 girls in the class.
Summing up,$(3+3+3)+4$ boys need $(3+3+3)+4$ girls that is 13 girls.
However,I can't see how I am going to generalize this problem.Never mind,here's my work.
MY TRY: We once again utilize the following facts:
(i)If there are 3 number of boys in the class,then number of girls also has to be 3. (ii)If there are 4 boys,required number of girls is also 4.
So if we can rewrite $r$ in the form $3k+4z$,we are done.
Lemma: Every integer $r\ge 3$ except 5 can be written in the form $3k+4z$ [k and z are positive integers,not both of them $0$]
PROOF: A number greater than or equal to 3 is of the form $3p$,$3p+1$,$3p+2$ for some positive integer p.We treat the cases individually[we must note that 5 cannot be expressed as a sum of multiples of 3 and 4.For this,we consider $p\ge 2$. So,we consider the cases r=3,4,5 separately and see that the number of boys and girls are indeed equal].
$3p$: If r=3p for some positive integer p,then plugging k=p and z=0 gives us
and we are done.
$3p+1$: Plugging k=p-1 and z=1, we get
$3p+2$: Plugging k=p-2 and z=2,we get
and the proof is complete.
Since r can always be written in the form $3k+4z$,
(1)Number of girls needed for 3k number of boys is 3k[From (i)].
(2)Number of girls needed for 4z number of boys is 4z[From (ii)].
Therefore total number of girls=3k+4z=r and we are done.Am I correct?