Maths Olympiad Prep

Library / /475 of 520

Number theory Difficulty 4.6 AIME Prove it

Given 93 distinct positive integers a1,a2,,a93a_1, a_2, \ldots, a_{93}, prove that there exist four positive integers am,an,ap,aqa_m, a_n, a_p, a_q such that (aman)(apaq)(a_m - a_n)(a_p - a_q) is a multiple of 1998.

Solution

Since 1998=37×54=74×271998 = 37 \times 54 = 74 \times 27,

(1) By the pigeonhole principle:
Among the 93 distinct positive integers a1,a2,,a93a_1, a_2, \ldots, a_{93}, there must be two numbers whose remainders are the same when divided by 37. Let these two numbers be ama_m and ana_n, then amana_m - a_n is a multiple of 37;
Among the remaining 91 numbers, there must be two numbers whose remainders are the same when divided by 54. Let these two numbers be apa_p and aqa_q, then apaqa_p - a_q is a multiple of 54.
Therefore, there must exist four positive integers am,an,ap,aqa_m, a_n, a_p, a_q such that (aman)(apaq)(a_m - a_n)(a_p - a_q) is a multiple of 1998.

(2) By the pigeonhole principle:
Among the 93 distinct positive integers a1,a2,,a93a_1, a_2, \ldots, a_{93}, there must be two numbers whose remainders are the same when divided by 74. Let these two numbers be ama_m and ana_n, then amana_m - a_n is a multiple of 74;
Among the remaining 91 numbers, there must be two numbers whose remainders are the same when divided by 27. Let these two numbers be apa_p and aqa_q, then apaqa_p - a_q is a multiple of 27.
Therefore, there must exist four positive integers am,an,ap,aqa_m, a_n, a_p, a_q such that (aman)(apaq)(a_m - a_n)(a_p - a_q) is a multiple of 1998.

In conclusion, there must exist four positive integers am,an,ap,aqa_m, a_n, a_p, a_q such that (aman)(apaq)(a_m - a_n)(a_p - a_q) is a multiple of 1998. Proven\boxed{\text{Proven}}

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.