Maths Olympiad Prep

Library / /57 of 60

Number theory Difficulty 6.0 AIME, harder Prove it South Africa

A new sequence is formed by deleting numbers from the sequence 1,2,3,4,,5001, 2, 3, 4, \dots, 500 such that the sum of any two numbers of the new sequence is never a multiple of seven.
What is the maximum length of the new sequence?

Solution

Group the numbers into 77 groups according to their remainders upon division by 77: the groups are
{1,8,15,,498},{2,9,16,,499},{3,10,17,,500},{4,11,18,,494},{5,12,19,,495},{6,13,20,,496},{7,14,21,,497}. \begin{aligned} \{1, 8, 15, \dots, 498\}, & \{2, 9, 16, \dots, 499\}, \{3, 10, 17, \dots, 500\}, \\ \{4, 11, 18, \dots, 494\}, & \{5, 12, 19, \dots, 495\}, \{6, 13, 20, \dots, 496\}, \{7, 14, 21, \dots, 497\}. \end{aligned}
Note that if a number from a group that leaves remainder xx is not deleted, then all the numbers from the group that leaves remainder 7x7-x must be deleted, otherwise two numbers will sum to a multiple of 77. In particular, only one number from the last group above may be selected.
Note also that if one number from a group (besides the last one) is selected, we may select all numbers in that group, since they all leave the same remainder when divided by 77. The first three groups contain 7272 numbers each, while the last four contain 7171 numbers each. If we select the first three groups, we may not select any number in the next three groups, and finally we can select one number from the last group. This yields 72×3+1=21772 \times 3 + 1 = 217 numbers.

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 and solution reproduced as published; topic and difficulty added by this site.