Maths Olympiad Prep

Library / /44 of 61

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

Problem:

A A{1,2,3,,49}A \subset \{1,2,3, \ldots, 49\} does not contain six consecutive integers. Find the largest possible value of A|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,,6},{7,,12},{13,,18},,{43,,48}\{1,2, \ldots, 6\}, \{7, \ldots, 12\}, \{13, \ldots, 18\}, \ldots, \{43, \ldots, 48\}. So A41|A| \leq 41. But a value of 41 is certainly possible, for example, exclude 2,8,14,,442,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 767 \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 767 \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 7617 \cdot 6 - 1 (3 and 44, 4 and 45, 5 and 46, 6 and 47). There are 3 ways to get a difference of 7627 \cdot 6 - 2 (4 and 44, 5 and 45, 6 and 46), 2 ways to get a difference of 7637 \cdot 6 - 3 (5 and 44, 6 and 45), and 1 way to get a difference of 7647 \cdot 6 - 4 (6 and 44).

If the difference is 7617 \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,383,9,14,20,26,32,38 and 44, and so on.

If the difference is 7627 \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 7637 \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 7647 \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 51+47+328+284+1210=4955 \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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