Maths Olympiad Prep

Library / /41 of 101

Combinatorics Difficulty 6.0 AIME, harder Prove it Estonia

Parents have nn children, where nn is a given natural number. Find all possibilities for how many children in this family can have both a brother and a sister.

Solutions — 2

Solution 1

If all the children have the same gender, then nobody can have a brother as well as a sister. In that case the number of children that match the condition is 0, regardless of nn.

If there are children of either gender, but for at least one gender there is exactly one child of that gender, then this child does not have a brother (if he's a boy) or a sister (if she's a girl). If there is exactly one child of the other gender as well (n=2n = 2), then the number of children that fulfill the condition is 0. If n3n \ge 3, then all other children have both a brother and a sister and there are n1n-1 children that satisfy the condition given in the problem statement. If there are at least 2 children of either gender, then all children have both a brother as well as a sister, and there are nn children satisfying the condition. This can happen when n4n \ge 4.

Summing up, for n2n \le 2 the answer is 0, for n=3n = 3 there can be 0 or n1n-1 (in other words 2) such children and for n4n \ge 4 there are either 0, n1n-1 or nn such children.

Solution 2

For some child to have both a brother and a sister, there must be at least 3 children in this family. Therefore if n2n \le 2, then the answer is 0. Now assume that n3n \ge 3. It is clear that children of the same gender either all satisfy the condition given in problem statement or none of them do. In order for children of some gender not to satisfy the condition there must either be 1 child of such gender or 0 of the opposite gender. In the first case there are n1n-1 children satisfying the condition (since n3n \ge 3 and therefore there must be at least 2 children of the opposite gender), in the second case there are 0 such children. Therefore for n3n \ge 3 the possible answers are 0, n1n-1, and nn. It suffices to note that children of both gender can only satisfy the condition if n4n \ge 4.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.