Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$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
1  
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

2 Answers 2

up vote 19 down vote accepted

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.

share|improve this answer
1  
How do I know that br=gr?Why must the number of slips of paper be equal? –  rah4927 Dec 7 '13 at 9:29
8  
Because friendship is symmetric. –  Henry Swanson Dec 7 '13 at 9:38
    
@HenrySwanson,Ah,thanks. –  rah4927 Dec 7 '13 at 9:42
2  
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
1  
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|$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.