Problem B. 4345. (March 2011)

B. 4345. Prove that in any set of seven different positive integers there are three numbers such that the greatest common divisor of any two of them leaves the same remainder when divided by three.

(Suggested by S. Kiss, Budapest)

(4 pont)

Deadline expired on April 11, 2011.

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

Megoldás. Az állítás nyilvánvaló, ha a számok között van három olyan, amelyik osztható 3-mal, ekkor ugyanis ezek közül bármely kettő legnagyobb közös osztója 0 maradékot ad 3-mal osztva. Ellenkező esetben a számok között található 6 olyan, hogy legfeljebb az egyikük osztható 3-mal. Ez azt jelenti, hogy ezen 6 szám közül bármely kettő legnagyobb közös osztója vagy 1, vagy 2 maradékot ad 3-mal osztva; a lényeg az, hogy csak kétféle maradék léphet fel. Legyen a 6 szám közül az egyik \(\displaystyle a\). A fennmaradó 5 szám között található 3, mondjuk \(\displaystyle b\), \(\displaystyle c\) és \(\displaystyle d\) úgy, hogy \(\displaystyle (a,b)\), \(\displaystyle (a,c)\) és \(\displaystyle (a,d)\) ugyanolyan maradékot adnak 3-mal osztva. Ha a \(\displaystyle (b,c)\), \(\displaystyle (b,d)\) és \(\displaystyle (c,d)\) legnagyobb közös osztók közül valamelyik, mondjuk \(\displaystyle (b,c)\) is ezt a maradékot adja, akkor \(\displaystyle a,b,c\) megfelelő hármast alkot. Ha nem, akkor \(\displaystyle (b,c)\), \(\displaystyle (b,d)\) és \(\displaystyle (c,d)\) biztos egyforma maradékot ad, és ekkor \(\displaystyle b,c,d\) alkot megfelelő hármast.

Statistics:

51 students sent a solution.
4 points:	Ágoston Péter, Baráti László, Beleznay Soma, Bogár Blanka, Csernák Tamás, Csörgő András, Czipó Bence, Damásdi Gábor, Dudás 002 Zsolt, Énekes Péter, Fonyó Viktória, Géczi Péter Attila, Gyarmati Máté, Hajnal Máté, Hartvig 147 Dániel, Herczeg József, Janzer Barnabás, Kabos Eszter, Kenéz Balázs, Maga Balázs, Máthé László, Mihálykó András, Nagy Bence Kristóf, Nagy Róbert, Perjési Gábor, Schultz Vera Magdolna, Sieben Bertilla, Simig Dániel, Strenner Péter, Szabó 928 Attila, Tossenberger Tamás, Viharos Andor, Weimann Richárd, Weisz Gellért, Zelena Réka, Zilahi Tamás, Zsakó András.
3 points:	Homonnay Bálint, Kiss 666 Péter.
2 points:	2 students.
1 point:	6 students.
0 point:	4 students.

Problems in Mathematics of KöMaL, March 2011