Maths Olympiad Prep

Library / /243 of 520

Combinatorics Difficulty 5.5 AIME, harder Find the answer

2792 \cdot 79 Determine the smallest integer n4n \geqslant 4, from which any nn different integers, 4 different integers a,b,c,da, b, c, d can be selected such that a+bcda+b-c-d is divisible by 20.
(39th International Mathematical Olympiad Preliminary Question, 1998)

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

Solution

[Solution] Since C72=7×62=21C_{7}^{2}=\frac{7 \times 6}{2}=21,
it follows that from 7 different integers, one can definitely select a pair of integers that are congruent modulo 20. Let this pair of integers be a,ca, c, then ac(mod20)a \equiv c(\bmod 20).

After selecting a,ca, c from the 7 different integers, there are still 5 different integers left. Adding 2 more integers that are different from the above 7 integers, we again form a set of 7 different integers. By the same analysis, we can select another pair of integers (let them be b,db, d), such that bd(mod20)b \equiv d(\bmod 20).
From (1) and (2), we get a+bc+d(mod20)a+b \equiv c+d(\bmod 20).
Thus,
a+bcd0(mod20), a+b-c-d \equiv 0 \quad(\bmod 20),

Therefore,
20a+bcd 20 \mid a+b-c-d \text {. }

Hence, from any 9 different integers, one can select 4 different numbers a,b,c,da, b, c, d such that 20a+bcd20 \mid a+b-c-d.
On the other hand, we can find 8 numbers, for example,
0,1,2,4,7,12,20,40 0,1,2,4,7,12,20,40

In these 8 numbers, no 4 numbers a,b,c,da, b, c, d can satisfy
20a+bcd. 20 \mid a+b-c-d .

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.