We make groups of numbers. Each group consists of five distinct numbers. A number may occur in multiple groups. For any two groups, there are exactly four numbers that occur in both groups. (a) Determine whether it is possible to make $2015$ groups. (b) If all groups together must contain exactly six distinct numbers, what is the greatest number of groups that you can make? (c) If all groups together must contain exactly seven distinct numbers, what is the greatest number of groups that you can make?
Problem
Source: Dutch NMO 2015 p1
Tags: combinatorics, Sets, maximum
20.09.2019 06:47
(a) It is possible to make 2015 groups. For example, take the 2015 groups {−4, −3, −2, −1, i}, where i runs from 1 to 2015. Each group consists of five distinct numbers, as required, and any two groups have exactly four numbers in common: −4, −3, −2, and −1. (b) Using six available numbers, there are only six possible groups of five numbers (each obtained by leaving out one of the six numbers). Those six groups do satisfy the requirement that any two of them have exactly four numbers in common. We conclude that six is the greatest number of groups we can make in this case. (c) A way to make three groups is to take {1,2,3,4,5}, {1,2,3,4,6}, and {1,2,3,4,7}. More than three groups is not possible. Indeed, suppose we have four or more groups. The first two groups are A = {a, b, c, d, e} and B = {a,b,c,d,f}, where a, b, c, d, e, and f are distinct numbers. Then there must be a third group C containing a seventh number g. The remaining four numbers in C must be in both A and B, hence C = {a,b,c,d,g}. Now consider a hypothetical fourth group D. This group cannot contain the number g since otherwise, using a similar reasoning as for C, we would have D = {a, b, c, d, g}. Because D does not contain the number g, it must contain the remaining four numbers a, b, c, and d from C. Comparison with groups A and B then shows that D can contain neither e nor f. It follows that besides a, b, c, and d, D cannot contain a fifth number, contradicting the requirements. We conclude that the greatest number of groups we can make is three.