A B. 4733. feladat (2015. október)

B. 4733. Egy \(\displaystyle n\ge 2\) csúcsú egyszerű, összefüggő gráf minden élére 1-est vagy 2-est írunk. Ezután minden csúcshoz hozzárendeljük a belőle kiinduló élekre írt számok szorzatát. Mutassuk meg, hogy lesz két olyan csúcs, melyekhez ugyanazt a számot rendeltük.

Javasolta: Ademir Hujdurović (Koper)

(3 pont)

A beküldési határidő 2015. november 10-én LEJÁRT.

Megoldásvázlat. Mivel a gráf egyszerű, ezért minden csúcsból legfeljebb \(\displaystyle n-1\) él indul ki, így a csúcsokhoz rendelt szorzatok értéke \(\displaystyle 1,2,2^2,\dots,2^{n-1}\) lehet, ami összesen \(\displaystyle n\) féle lehetőség. Azonban megmutatjuk, hogy nem fordulhat elő mind az \(\displaystyle n\) érték. Csak úgy lehetséges, hogy egy csúcshoz a \(\displaystyle 2^{n-1}\) számot rendeljük, ha ez a csúcs az összes többi csúccsal össze van kötve, és a belőle induló élek mindegyikére 2-est írtunk. Ekkor viszont minden csúcsnál legalább 2 a szorzat, tehát 1-es szorzatot egyik csúcshoz sem rendeltünk. Vagyis az 1 és a \(\displaystyle 2^{n-1}\) nem szerepelhet egyszerre csúcshoz rendelt szorzatként. Azt kaptuk tehát, hogy a csúcsokhoz legfeljebb \(\displaystyle n-1\) féle szám kerülhet, így a skatulya-elv miatt biztosan lesz két egyenlő.

Statisztika:

204 dolgozat érkezett.
3 pontot kapott:	170 versenyző.
2 pontot kapott:	13 versenyző.
1 pontot kapott:	7 versenyző.
0 pontot kapott:	12 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2015. októberi matematika feladatai