olymmath

USAMO 2004 Problem 2

Suppose a1,…,ana_1, \dots, a_n are integers whose greatest common divisor is 1. Let SS be a set of integers with the following properties:

(a) For i=1,…,ni=1, \dots, n , ai∈Sa_i \in S . (b) For i,j=1,…,ni,j = 1, \dots, n (not necessarily distinct), ai−aj∈Sa_i - a_j \in S . (c) For any integers x,y∈Sx,y \in S , if x+y∈Sx+y \in S , then x−y∈Sx-y \in S .

Prove that SS must be equal to the set of all integers.

Dataset text AI-MO AoPS. Quoted with source.

Solutions

Human solution Solution 1 by Calvin Lin

Let (b1,b2,…)=S(b_1, b_2, \ldots ) = S and (b1,b2−b1,…,bn−b1)=T(b_1, b_2-b_1, \ldots , b_n-b_1) = T. WTS S=TS = T.

Consider TT:

  • by (ii), b1−b1=0∈Tb_1 - b_1 = 0 \in T
  • by (ii), (bi−b1)−b1=bi−2b1∈T(b_i - b_1 ) - b_1 = b_i - 2b_1 \in T
  • 0,b1,0+b1∈T0, b_1, 0+b_1 \in T so by (iii), 0−b1=−b1∈T0 - b_1 = -b_1 \in T.
  • bi−b1,−b1,(bi−b1)+(−b1)∈Tb_i - b_1, -b_1, (b_i-b_1) + (-b_1) \in T, so by (iii), (bi−b1)−(−b1)=bi∈T(b_i - b_1) - ( - b_1 ) = b_i \in T.

Mathematics Stack Exchange. Open licence.

Similar problems

These problems have the most words in common with this statement.

Locator usamo/2004/p2 · Tag Y1G4C7ZB68 · Edit this page on GitHub · Keys: j next, k previous