# If 1 boy knows r girls and 1 girl knows r boys ,then number of boys=girls

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

3p=3(p)+4(0)

and we are done.

$3p+1$: Plugging k=p-1 and z=1, we get

3(p-1)+4=3p+1

$3p+2$: Plugging k=p-2 and z=2,we get

3(p-2)+4(2)=3p+2

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?

-
$r=5$ can't be written as $3k+4z$ for positive integers $k,z$. Your proof needs to consider closure of the natural numbers, which subtraction does not satisfy. –  Tim Ratigan Dec 7 '13 at 9:04
@TimRatigan,thanks.Is there a way to patch up the hole in my proof? –  rah4927 Dec 7 '13 at 9:27
Make $p\geq 2$, then $p-2$ (the least number you use) is $\ge 0$ –  Tim Ratigan Dec 7 '13 at 9:29
Well, I'm not a mathematician (wandered in here from Stackoverflow's "hot network questions") but it seems to me that if all the boys and girls are too shy to talk to one another (ie r is 0) then their numbers could vary independently, invalidating the question's conclusion :D –  Jan Van Herck Dec 7 '13 at 13:39
@rahul, haha, point conceded, but that is just semantics. Obviously, the question allows for the possibility that a boy and a girl can go to the same class without knowing each other, so the point remains that if this is true for all of them, their number can vary independently. I just tried to word it in a funny way explaining it as shyness :) –  Jan Van Herck Dec 7 '13 at 13:50

Let $b$ be the number of boys, and $g$ the number of girls.

For any boy $B$ and girl $G$ who know each other, write on a slip of paper "$B$ and $G$ know each other." We count the number of slips of paper in two different ways.

Since every boy knows $r$ girls, there are $br$ slips of paper.

Since every girl knows $r$ boys, there are $gr$ slips of paper.

Thus $br=gr$ and therefore $b=g$ (if $r\ne 0$).

Remark: For a more romantic version, let us suppose that each boy-girl pair who know each other kiss (once). Instead of counting slips of paper, count kisses.

-
How do I know that br=gr?Why must the number of slips of paper be equal? –  rah4927 Dec 7 '13 at 9:29
Because friendship is symmetric. –  Henry Swanson Dec 7 '13 at 9:38
@HenrySwanson,Ah,thanks. –  rah4927 Dec 7 '13 at 9:42
I feel that it is important to note that the result does not hold if r=0,as pointed out by Jan Van Herck in the comments. –  rah4927 Dec 7 '13 at 13:58
Yes, it is important to note that we want $r\ne 0$, thank you, I have added it. As to your earlier question, the answer computes the number of kisses in two different ways. Same kisses. –  André Nicolas Dec 7 '13 at 16:58

Note that the relationships across gender form a bipartite graph $G$ with subgraphs $A$ (vertices are girls) and $B$ (vertices are boys). The graph is regular, that is all vertices have the same degree $r:=\deg{v}$. However, we also note that for every edge incident on a vertex on $B$, the other end of the edge is incident on $A$, since $G$ is bipartite. It follows that $\deg B=\deg A\Longrightarrow r|B|=r|A|\Longrightarrow |B|=|A|$

-
Can you please tell me the prerequisites to understanding this proof? –  rah4927 Dec 8 '13 at 11:46
Just some basic graph theory. I understand it might look intimidating because of the terminology, but really it's a formal way of saying what Andre Nicolas said. This and this may be useful. –  Tim Ratigan Dec 8 '13 at 20:50