Problem B. 4081. (March 2008)
B. 4081. Prove that natural numbers can be coloured in 2008 colours, such that each colour occurs, and whenever 3a+5b=7c is true, there are two numbers among a, b and c that have the same colour.
(5 pont)
Deadline expired on April 15, 2008.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás: Egy n pozitív egészre jelölje f(n) azt a legnagyobb nemnegatív k egész számot, amelyre n osztható 2k-nal. A számokat színezzük ki a színekkel a következő módon. Ha f(n)
2006, akkor legyen n színe f(n), egyébként pedig 2007. Állítjuk, hogy ez a színezés megfelelő.
Tegyük fel ugyanis, hogy a és b színe, i és j különböző, ekkor 3a+5b=7c esetén c színe m=min {i,j} lesz. Valóban, konstrukciónk szerint a és b is osztható lesz 2m-nel, ezért 3a+5b=7c is. Mivel 7 páratlan, c is osztható 2m-nel, vagyis c színe legalább m. De az is igaz, hogy 2m+1 már nem osztója c-nek. Ha ugyanis i<j, akkor i2006, vagyis a nem osztható 2i+1-nel, b viszont osztható, hiszen osztható 2j-nel. Következésképpen 2i+1 osztja 5b-t, de nem osztja 3a-t, ezért 7c-t, és így magát c-t sem osztja, és hasonlóképpen érvelhetünk az i>j esetben is a és b szerepének felcserélésével.
Megjegyzés: A bizonyításhoz mindössze annyit használtunk ki, hogy a 3a+5b=7c összefüggésben mind a három együttható páratlan szám. Egy egészen eltérő konstrukciót kaphatunk úgy, hogy az összes olyan számot, amelyik 105-tel osztva nem 1 maradékot ad, azonos színnel színezzük, a többi számot pedig tetszés szerint. E konstrukció helyességének igazolása önmagában is érdekes feladat, melyet az olvasóra bízunk.
Statistics:
24 students sent a solution. 5 points: Aujeszky Tamás, Bálint Dániel, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Éles András, Énekes Péter, Fonyó Dávid, Frankl Nóra, Kalina Kende, Keresztfalvi Tibor, Kovács 999 Noémi, Lamm Éva, Márkus Bence, Nagy 648 Donát, Somogyi Ákos, Szalkai Balázs, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Zieger Milán. 4 points: Pap Máté, Szenczi Zoltán. 0 point: 1 student.
Problems in Mathematics of KöMaL, March 2008