Maths Olympiad Prep

Library / /445 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Let A={a1,a2,,a7}A=\{a_{1}, a_{2}, \ldots, a_{7}\} be a set of distinct positive integers such that the mean of the elements of any nonempty subset of AA is an integer. Find the smallest possible value of the sum of the elements in AA.

A number or a short expression. Spacing and $ signs are ignored.

Solution

For 2i62 \leq i \leq 6, we claim that a1a7(modi)a_{1} \equiv \ldots \equiv a_{7}(\bmod i). This is because if we consider any i1i-1 of the 7 numbers, the other 7(i1)=8i7-(i-1)=8-i of them must all be equal modulo ii, because we want the sum of all subsets of size ii to be a multiple of ii. However, 8i28-i \geq 2, and this argument applies to any 8i8-i of the 7 integers, so in fact all of them must be equal modulo ii. We now have that all of the integers are equivalent modulo all of 2,,62, \ldots, 6, so they are equivalent modulo 60, their least common multiple. Therefore, if the smallest integer is kk, then the other 6 integers must be at least k+60,k+602,,k+606k+60, k+60 \cdot 2, \ldots, k+60 \cdot 6. This means the sum is 7k+60217+6021=12677k+60 \cdot 21 \geq 7+60 \cdot 21=1267. 1267 is achievable with {1,1+60,,1+606}\{1,1+60, \ldots, 1+60 \cdot 6\}, so it is the answer.

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