School where every pair of students share a common grandfather

Question

There are $64$ pupils attending a particular school. Any two of these pupils share (at least) one common grandfather.

Does this imply that there are at least $43$ pupils all of which have a common grandfather?

Answer 1

First of all, with some half-sibling incest, it's possible for a student to only have one grandpa. If that happens, then all 64 students have that grandpa as well. So, we can assume everyone has two grandpas.

Let's say that a "grandpa triangle" is a set of three grandpas, where each pair have a common grandchild.

If there is no grandpa triangle, then all 64 students have a common grandpa.

This is certainly true if all students have the same pair of grandpas. So, suppose the Alice has grandpas $\{g_1,g_2\}$, and Bob student has grandpas $\{g_1,g_3\}$. Then every student must have $g_1$ as a grandpa: if they didn't, they would have to have $g_2$ in order to share a grandpa with Alice, and also have to have $g_3$ to share a grandpa with Bob, which would make a grandpa triangle.

If there is a grandpa triangle, then there are only three grandpas.

Let's say the grandpa triangle is $\{g_1,g_2,g_3\}$, where Alice, Bob and Charlie have the grandpa sets of $\{g_1,g_2\},\{g_2,g_3\}$ and $\{g_3,g_1\}$. If any student, Diane, had a grandpa $g_4$ which was different then $g_1,g_2,g_3$, then Diane's pair of grandpas would have to be either $\{g_4,g_1\},\{g_4,g_2\},$ or $\{g_4,g_3\}$, but this would mean she didn't share a grandpa with Bob, Charlie, or Alice, respectively. Therefore, every student must have both their grandpas in the set $\{g_1,g_2,g_3\}$, so these are the only three grandpas.

If there are only three grandpas, the some grandpa has 43 grandkids.

If we let $n_1,n_2,n_3$ be the number of grandkids that $g_1,g_2,g_3$ have. Then $n_1+n_2+n_3$ will be twice the number of kids, since every kid is counted twice. This means $n_1+n_2+n_3=2\cdot 64=128$. In order for three numbers to add to $128$, at least one must be $43$ or more.

Answer 2

Yes.

There can be at most three grandfathers (GPs). If there are four, a child could have GPs $A$ and $B$, and another one could have GPs $C$ and $D$, violating the first restriction.

So, our students can be divided into three groups, for each pairing of GPs.
$64$ divided by $3$ is $21.33$. So, if each group had $21$, then our max for a common GP would be $42$. But, that's only $63$ students, so by the pigeonhole principle, we have to add the last child to a group, allowing us to get to $43$ pupils with a common GP.

Answer 3

Yes, at least 43 pupils have the same grandfather.

Each pupil has two biological grandfathers, so in order for every pupil to have one grandfather in common with every other pupil, there would need to be a maximum of three grandfathers total. Call these grandfathers Larry, Curly, and Moe for the sake of argument.

The grandchildren of Larry and Curly are group A, Larry and Moe are group B, and Moe and Curly are group C. One of these groups (let's say group C) is the smallest. If group C has 21 pupils, A and B have a total of 43 pupils (i.e., Larry has 43 grandchildren at the school). If group C has fewer than 21 pupils, then Larry has more than 43 grandchildren at the school. If group C has more than 21 pupils, it is no longer the smallest group, and this process starts all over with some other group as the smallest group.

The Pigeonhole Principle is applied twice here. First, to find the maximum number of grandfathers, and then again to find the minimum number of grandchildren sharing the same grandfather. https://en.wikipedia.org/wiki/Pigeonhole_principle