A ⊆ {1, 2, 3, ... , 49} does not contain six consecutive integers. Find the largest possible value of |A|. How many such subsets are there (of the maximum size)?
Answer
max = 41; no. ways 495
Solution
We must exclude at least one element of each of the 8 sets {1, 2, ... , 6}, {7, ... , 12}, {13, ... , 18}, ... , {43, ... , 48}. So |A| ≤ 41. But a value of 41 is certainly possible, for example, exclude 2, 8, 14, ... , 44.
The largest excluded element must be at least 44 (or we have the 6 consecutive elements 44, 45, 46, 47, 48, 49). The smallest excluded element must be at most 6. If we exclude 2 and 44, then the difference between them is 7·6 and so the other 6 excluded elements are fixed. But if we exclude 3 and 44, for example, then there are several possible choices for the other elements.
There are 5 ways of choosing the smallest and largest excluded element to get a difference of 7·6 between them (2 and 44, 3 and 45, 4 and 46, 5 and 47, 6 and 48). There are 4 ways to get a difference of 7·6 - 1 (3 and 44, 4 and 45, 5 and 46, 6 and 47). There are 3 ways to get a difference of 7·6 - 2 (4 and 44, 5 and 45, 6 and 46), 2 ways to get a difference of 7·6 - 3 (5 and 44, 6 and 45), and 1 way to get a difference of 7·6 - 4 (6 and 44).
If the difference is 7·6 - 1, then we can shorten any of the 7 gaps, so there are 7 possibilities. For example, with 3 and 44, we could shorten the first gap, so excluding 3, 8, 14, 20, 26, 32, 38 and 44, or the second gap, so excluding 3, 9, 14, 20, 26, 32, 38 and 44, and so on.
If the difference is 7·6 - 2, then we can shorten one gap by two (7 possibilities) or two gaps by one (21 possibilities), total 28. If the difference is 7·6 - 3, then we can shorten on gap by three (7), one by two and one by one (42) or three by one (35), total 84. Finally, if the difference is 7·6 - 4, we can shorten one by four (7), one by three and one by 1 (42), two by two (21), one by two and two by one (105), or four by one (35), total 210.
So the total number of possibilities is 5·1 + 4·7 + 3·28 + 2·84 + 1·210 = 495.
© John Scholes
jscholes@kalva.demon.co.uk
30 Dec 03
Last corrected 30 Dec 03