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.

Please help me understand how to address this kind of problem.


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$.

| cite | improve this answer | |
  • $\begingroup$ Thanks, just want to make sure - there no other way to solve this without graph theory? $\endgroup$ – misha312 Aug 19 '17 at 9:20
  • $\begingroup$ Oh probably - I would rarely claim there is only one way to solve a problem. This does seem like a straightforward use though. $\endgroup$ – 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?

| cite | improve this answer | |
  • $\begingroup$ yes my point was that this is what I was aiming for... but I got your point $\endgroup$ – misha312 Aug 20 '17 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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