![]() |
A B. 4742. feladat (2015. november) |
B. 4742. Mutassuk meg, hogy az \(\displaystyle n\ge 3\) csúcsú teljes gráf éleire írhatunk 1-et, 2-t vagy 3-at úgy, hogy minden csúcsban különböző legyen az oda befutó élekre írt számok szorzata.
(4 pont)
A beküldési határidő 2015. december 10-én LEJÁRT.
Megoldásvázlat. Indukció \(\displaystyle n\)-re; \(\displaystyle n=3\) esetén egy élnek 1-es, egynek 2-es és egynek 3-as számot adva a feltétel teljesül. Ha a \(\displaystyle k\) csúcsú teljes gráf éleit már megfelelően számoztuk, és egy \(\displaystyle k+1\)-edik csúcsból kiinduló valamennyi élre a \(\displaystyle v\) számot írjuk, akkor a régi \(\displaystyle k\) csúcs bármelyikébe befutó élek számainak szorzata a korábbi \(\displaystyle v\)-szeresére változik, így e szorzatok mind különbözőek maradnak. Az új, \(\displaystyle k+1\)-edik csúcsba befutó élek számainak szorzata pedig \(\displaystyle v^{k}\). Legyen \(\displaystyle v=i\), ha a \(\displaystyle k\) és \(\displaystyle i\) szám 3-mal való osztási maradéka megegyezik.
Statisztika:
151 dolgozat érkezett. 4 pontot kapott: 108 versenyző. 3 pontot kapott: 27 versenyző. 2 pontot kapott: 5 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 7 versenyző. Nem versenyszerű: 3 dolgozat.
A KöMaL 2015. novemberi matematika feladatai