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