0
$\begingroup$

In a colony of $(m n+1)$ mice, must at least one of the following statements be true? If so, why?

  1. There is a set $A$ of $(m+1)$ mice none of which is a parent of any other in the set.
  2. There is an ordered set $B$ of $(n+1)$ mice $a_{1}, a_{2}, \ldots, a_{n}, a_{n+1}$ such that $a_{i+1}$ is a parent of $a_{i}$ for each $i=1,2, \ldots, n$.
$\endgroup$
2

1 Answer 1

5
$\begingroup$

This seems quite straightforward.

Draw up the family trees. In each tree, number the generations starting from 1, with their children as generation 2, and so on. In this way every individual gets some generation number.
As fljx points out in the comments, parents don't necessarily have the same generation number, but in that case use the largest of the parents' numbers plus one as the generation number for the children. The important properties of these generation numbers are: (1) no parent and child shares the same generation number, and (2) each individual in a later generation has at least one parent in the immediately previous generation.

If there are $n$ or fewer generations, and each generation has $m$ or fewer individuals, then there are no more than $mn$ mice all together.

The contrapositive to the previous statement is:
If there are more than $mn$ mice, then there are either more than $n$ generations, or some generation has more than $m$ individuals. In the first case there is a descendant chain of at least $n+1$ mice (using property (2) to find a chain from generation $n+1$ back to generation $1$), and in the second case there are at least $m+1$ mice that are not in a parent-child relationship (using property (1) ).

$\endgroup$
3
  • 1
    $\begingroup$ Under normal circumstances, each mouse has two parents, which don't have to have the same "generation number". I think your solution works if you assign each child max(parent generation) +1, but could do with some clarification. $\endgroup$
    – fljx
    Commented May 20, 2022 at 14:06
  • $\begingroup$ @fljx That is a very good point that I had not considered. $\endgroup$ Commented May 20, 2022 at 14:08
  • $\begingroup$ For some definition of straightforward. Very nice solution! $\endgroup$
    – Simd
    Commented May 20, 2022 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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