Problem C. 1611. (May 2020)

C. 1611. Some numbers are selected from the set of the first 21 positive integers such that the absolute values of the differences of all pairs of selected numbers should be different. What is the largest possible number of different absolute values obtained? Give an example of a case when this occurs.

(5 pont)

Deadline expired on June 10, 2020.

Sorry, the solution is available only in Hungarian. Google translation

Megjegyzés. A megoldás során végig úgy képezzük a különbséget, hogy a nagyobb számból vonjuk ki a kisebbet, így a különbség eleve pozitív lesz, nem szükséges az abszolútértékét venni.

A legkisebb lehetséges különbség az 1, a legnagyobb a 20 lehet, azaz összesen 20-féle érték állhat elő különbségként. Ha \(\displaystyle n\) számot választottunk ki megfelelő módon, akkor \(\displaystyle \binom{n}{2}\) különbség jön létre, vagyis azt kell meghatároznunk, legfeljebb mekkora lehet \(\displaystyle n\), azaz legfeljebb hány számot választhattunk ki.

Ha 7 számot választanánk ki, akkor közülük minden lehetséges módon kettőt kiválasztva \(\displaystyle \binom72=21\) különbség adódna. Ezek közül nem lehet mind különböző, hiszen csak 20-féle értéket kaphatunk az előbbiek szerint. Ha 7-nél több számot választunk ki, akkor még több különbség adódik, amik között az előbbiek szerint lesz egyforma.

6 szám kiválasztható megfelelően, és ilyenkor 15 különböző érték jön létre különbségként. (Ha kevesebb számot választanánk, akkor kevesebb féle érték jöhetne létre különbségként.) Például az \(\displaystyle 1,2, 4,8,13\) és \(\displaystyle 21\) számok választása esetén az alábbi különbségek adódnak:

\(\displaystyle 1, 2, 3, 4,5, 6, 7, 8,9, 11, 12, 13, 17, 19, 20.\)

Tehát legfeljebb 15 különböző érték jöhet létre.

Statistics:

90 students sent a solution.
5 points:	63 students.
4 points:	10 students.
3 points:	6 students.
2 points:	2 students.
1 point:	6 students.
0 point:	3 students.

Problems in Mathematics of KöMaL, May 2020