Library / Iberoamerican Mathematical Olympiad /42 of 57

Iberoamerican Mathematical Olympiad

Combinatorics Difficulty 6.2 National Olympiad Prove it Ibero-American Mathematical Olympiad

Problem:

A $A \subset \{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)?

Solution

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 $|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 \cdot 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 \cdot 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 \cdot 6 - 1$ (3 and 44, 4 and 45, 5 and 46, 6 and 47). There are 3 ways to get a difference of $7 \cdot 6 - 2$ (4 and 44, 5 and 45, 6 and 46), 2 ways to get a difference of $7 \cdot 6 - 3$ (5 and 44, 6 and 45), and 1 way to get a difference of $7 \cdot 6 - 4$ (6 and 44).

If the difference is $7 \cdot 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 one 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 \cdot 6 - 4$ , we can shorten one by four (7), one by three and one by one (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$ .

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.