Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4081. feladat (2008. március)

B. 4081. Bizonyítsuk be, hogy a pozitív egész számok kiszínezhetők 2008 színnel úgy, hogy mindegyik színt felhasználjuk, és valahányszor 3a+5b=7c, akkor a, b és c között van két ugyanolyan színű.

(5 pont)

A beküldési határidő 2008. április 15-én LEJÁRT.


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 0,1,\ldots,{2007} színekkel a következő módon. Ha f(n)\le2006, 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 i\le2006, 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.


Statisztika:

24 dolgozat érkezett.
5 pontot kapott: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 pontot kapott:Pap Máté, Szenczi Zoltán.
0 pontot kapott:1 versenyző.

A KöMaL 2008. márciusi matematika feladatai