# pigeonhole principle combination problem: find number of students in class

New to combinatorics (second lesson in the course). I'd like you to explain to me how to solve the following problem.

Consider this:

We have two classes of students, A and B.

In class A: every student except Dan knows exactly 12 students from class B, Dan knows exactly 8 students from class B

In class B: every student knows exactly 8 students from class A we know that class B contains 43 students

We need to find the number of students in class A.

To be honest, I don't know where to start -

1. I know that class A contains more than 8 students (if 8 then in this case every student in a knows 43 students in class b).

2. I feel that we need to apply the pigeonhole principle to solve this problem but I don't know where.

We know there are at least $8$ students in class $A$, but to go any further we have to assume that "knowing" is a reflexive relation, that is: "$c$ knows $d$" $\iff$ "$d$ knows $c$".

Given that assumption, it seems more like simple graph theory, with students as nodes and "$c$ knows $d$" represented as an edge; a bipartite graph of part $A$ and $B$ with $8\times 43=344$ edges connecting the parts.

Then Dan accounts for $8$ of these edges on the $A$ side and there are $(344-8)/12=28$ other students in class $A$.

• Thanks, just want to make sure - there no other way to solve this without graph theory? – misha312 Aug 19 '17 at 9:20
• Oh probably - I would rarely claim there is only one way to solve a problem. This does seem like a straightforward use though. – Joffan Aug 19 '17 at 13:46

Joffan helped a lot but there is another way without using the graph theory.

To solve this we will define a group of pairs of students - $R$

The group of class B is $B$

The group of class A is $A$

for class $B$ - $$\forall b\in B$$ $$\mid\{b\mid \langle b,a\rangle \in R, a\in A \}\mid = 8$$ every student in $B$ stands with exactly 8 students from $A$

So the total number of pairs in $R$ is $8\cdot 43 = 344$

for class $A$ -

$\forall a\in A$ except Dan $$\mid\{a\mid \langle b,a\rangle \in R , b\in B \}\mid = 12$$ for Dan: $$\mid\{dan\mid \langle b,dan\rangle \in R, b\in B \}\mid = 8$$

Lets assume the number of students in class $B$ is $x$: $$344 = (x-1)\cdot 12 + 1 \cdot 8$$ Which will give us $x=29$

I hope this is right what do you think?

• yes my point was that this is what I was aiming for... but I got your point – misha312 Aug 20 '17 at 20:41