15
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ I hated Habsburg High $\endgroup$ – question_asker Mar 4 '16 at 3:00
  • $\begingroup$ @question_asker lol $\endgroup$ – Richard Roe Mar 8 '16 at 20:30
21
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ Back in Grandpa Triangle's day, you only got 2 sides not 3, and they were both uphill! And they didn't have right angles like today's triangles! $\endgroup$ – corsiKa Oct 16 '15 at 2:36
9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ "There can be at most 3 grandfathers (GPs)" This is a minor point to a nice solution, but technically this isn't true. $\endgroup$ – Tyler Seacrest Oct 15 '15 at 14:59
  • $\begingroup$ Yes, but the other configuration is everyone having the same repeat grandfather, but that makes the question trivial. $\endgroup$ – JonTheMon Oct 15 '15 at 15:38
  • 2
    $\begingroup$ "If there are 4, a child could have GPs A and B, and another could have GPs C and D" That could needs to be a must, and proving this is an important part of the answer. $\endgroup$ – Taemyr Oct 16 '15 at 7:27
8
$\begingroup$

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

$\endgroup$

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.