Maths Olympiad Prep

Library / /257 of 520

Combinatorics Difficulty 5.5 AIME, harder Find the answer

14. (15 points) From the sequence of consecutive natural numbers 1,2,3,,20141,2,3, \cdots, 2014, select nn numbers such that no two of these nn numbers satisfy the condition where one is 7 times the other. Determine the maximum value of nn and provide a justification.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

【Analysis】First, group these numbers.
4 numbers in a group: {1,7,49,343},{2,14,98,686},{3,21,147,1029}{4,28\{1,7,49,343\},\{2,14,98,686\},\{3,21,147,1029\}\{4,28, 196,1372}{5,35,245,1715}196,1372\}\{5,35,245,1715\}
3 numbers in a group: {6,42,294}{8,56,392}{9,63,441}{41,287,2009}\{6,42,294\}\{8,56,392\}\{9,63,441\} \cdots\{41,287,2009\} Note the first number skips 7,14,21,28,357, 14, 21, 28, 35, etc., a total of 416+15=3141-6+1-5=31 groups.
2 numbers in a group: {43,301}{44,308}{286,2002}\{43,301\}\{44,308\} \cdots\{286,2002\}, Note to skip the numbers that have already appeared, i.e., 49, 98, 147, 196, 245,56,63,280245, 56, 63, \cdots 280, a total of 34 numbers, so there are 28643+134=210286-43+1-34=210 groups of 2 numbers.

【Solution】Solution:
From the analysis, we know: {1,7,49,343},{2,14,98,686},{286,2002}\{1,7,49,343\},\{2,14,98,686\}, \cdots\{286,2002\}, in total 246 groups of numbers, in the first five groups, at most 2 can be taken from each group, at least 10 cannot be taken, in the groups of 3 numbers, at least 31 cannot be taken, in the groups of 2 numbers, at least 210 cannot be taken, so the maximum number that can be taken is 20141031210=17632014-10-31-210=1763 numbers. In these 1763 numbers, answer: taking any 2, one will not be 7 times the other, the maximum value of nn is 1763.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.