## Problem B1

A $\square\{1,2,3, \ldots, 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, \ldots, 6\},\{7, \ldots, 12\},\{13, \ldots$, $18\}, \ldots,\{43, \ldots, 48\}$. So $|\mathrm{A}| \leq 41$. But a value of 41 is certainly possible, for example, exclude $2,8,14, \ldots, 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 \cdot 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 \cdot 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 \cdot 1+4 \cdot 7+3 \cdot 28+2 \cdot 84+1 \cdot 210=495$.

