A B. 5299. feladat (2023. február)

B. 5299. A számegyenes \(\displaystyle 1,2,3\) pontjában egy-egy bolha ül. Ha egy bolha az \(\displaystyle a\) pontban, míg egy másik bolha a \(\displaystyle b\) pontban van, akkor az \(\displaystyle a\)-ban levő bolha átugorhat a \(\displaystyle 2b-a\) pontba. Előfordulhat-e véges sok ilyen ugrást követően, hogy a bolhák a \(\displaystyle 2^{100},3^{100},2^{100}+3^{100}\) pontokban vannak?

Javasolta: Pach Péter Pál (Budapest)

(6 pont)

A beküldési határidő 2023. március 10-én LEJÁRT.

Megoldás. Először is figyeljük meg, hogy az ugrálás során minden bolha végig egész értékeken marad, sőt ugyanolyan paritásún, mint ahol az elején is volt. Ha ugyanis \(\displaystyle a,b\) egészek, akkor \(\displaystyle 2b-a\) is egész, és \(\displaystyle 2\mid (2b-a)-a=2(b-a)\).

Továbbá a bolhák közti távolságok legnagyobb közös osztója is végig változatlan marad. Ha a három bolha az \(\displaystyle a,b,c\) pontokban van, akkor ez az érték \(\displaystyle (a-b,b-c,c-a)\). Világos, hogy elég két távolság legnagyobb közös osztóját venni, vagyis \(\displaystyle (a-b,b-c,c-a)=(a-b,b-c)\), ha ugyanis egy szám osztja \(\displaystyle a-b\) és \(\displaystyle b-c\) mindegyikét, akkor összegüket, vagyis \(\displaystyle (c-a)\)-t is osztja. Ha az \(\displaystyle a\)-ban lévő bolha átugrik \(\displaystyle (2b-a)\)-ba, akkor \(\displaystyle ((2b-a)-b,b-c,c-a)=((2b-a)-b,b-c)=(b-a,b-c)=(a-b,b-c,c-a)\) valóban teljesül.

Mind az \(\displaystyle \{1,2,3\}\) hármasban, mind a \(\displaystyle \{2^{100},3^{100},2^{100}+3^{100}\}\) hármasban két páratlan és egy páros szám szerepel, továbbá

\(\displaystyle ((2^{100}+3^{100})-2^{100},(2^{100}+3^{100})-3^{100})=(3^{100},2^{100})=1=(2-1,3-1),\)

így az eddigi észrevételeink nem zárják ki, hogy a bolhák az egyik hármasról átugrálhassanak a másikra. Megmutatjuk, hogy ezt valóban meg is tudják tenni. Mivel egy ugrássorozat fordított sorrendben is elvégezhető, ezért elég megmutatnunk, hogy mindkét hármasból el lehet jutni a \(\displaystyle \{0,1,1\}\) hármasba. Egészen pontosan azt igazoljuk, hogy ha \(\displaystyle a,b,c\) nemnegatív egész számok, melyek között két páratlan és egy páros van, továbbá \(\displaystyle (a-b,b-c,c-a)=1\), akkor a három bolha az \(\displaystyle \{a,b,c\}\) hármasról átugráltatható a \(\displaystyle \{0,1,1\}\) hármasba.

Ezt úgy mutatjuk meg, hogy amíg csak lehetséges, megpróbáljuk az \(\displaystyle a+b+c\) összeget csökkenteni szabályos ugrásokkal úgy, hogy \(\displaystyle a,b,c\) nemnegatív egészek maradjanak. Mivel az összeg így mindig legalább 1-gyel csökken, véges sok lépésen belül biztosan elakadunk majd.

A szimmetria miatt feltehető, hogy \(\displaystyle 0\leq a\leq b\leq c\). Először tegyük fel, hogy a három érték páronként különböző, vagyis \(\displaystyle 0\leq a<b<c\). Először a \(\displaystyle c\)-ben lévő bolha ugorja át a \(\displaystyle b\)-ben lévőt, ezzel \(\displaystyle (2b-c)\)-be érkezik. Amennyiben ez egy nemnegatív érték, sikerült is csökkentenünk az összeget a pozitív \(\displaystyle 2(c-b)\) értékkel. Ha \(\displaystyle 2b-c\) negatív, akkor a bolha ezután ugorja át az \(\displaystyle a\)-ban lévőt is, így biztosan pozitív számra érkezik. A bolha így \(\displaystyle c\)-ből két lépésben \(\displaystyle 2a-2b+c=c+2(a-b)\)-be került, így az összeg a pozitív \(\displaystyle 2(b-a)\) értékkel csökkent.

Most tegyük fel, hogy \(\displaystyle a,b,c\) nem mind különböző. Mivel \(\displaystyle (a-b,b-c,c-a)=1\), ezért ekkor a harmadik érték a két egybeesőtől pontosan 1-gyel tér el. Tehát vagy \(\displaystyle 0\leq a=b<c=a+1\) vagy \(\displaystyle 0\leq a<b=c=a+1\). Ha \(\displaystyle 0<a\), akkor a \(\displaystyle c\)-ben lévő bolha az \(\displaystyle a\)-ban lévőt átugorva \(\displaystyle (a-1)\)-be kerül, az összeg csökkent és \(\displaystyle a-1\) is nemnegatív.

Tehát csak úgy akadhatunk el, ha \(\displaystyle a=0\), ekkor a hármas vagy \(\displaystyle \{0,0,1\}\) vagy \(\displaystyle \{0,1,1\}\), de a paritásra vonatkozó feltétel alapján csak \(\displaystyle \{0,1,1\}\) lehet. Ezzel az állításunkat igazoltuk, tehát mind az \(\displaystyle \{1,2,3\}\), mind a \(\displaystyle \{2^{100},3^{100},2^{100}+3^{100}\}\) hármasból el lehet jutni a \(\displaystyle \{0,1,1\}\)-be.

Tehát előfordulhat, hogy az \(\displaystyle 1,2,3\) pontokból indulva véges sok ugrást követően a \(\displaystyle 2^{100},3^{100},2^{100}+3^{100}\) pontokba kerülnek a bolhák.

Megjegyzés. A bizonyítás során feltettük, hogy \(\displaystyle a,b,c\) nemnegatívak, de enélkül is igaz a segédállítás. Ha \(\displaystyle a,b,c\) mindegyike negatív, akkor hivatkozhatunk a szimmetriára, ha pedig negatív és nemnegatív érték is van köztük, akkor a negatív helyről vagy helyekről a nemnegatívat átugorva pozitív helyre küldhetők a bolhák.

Statisztika:

33 dolgozat érkezett.
6 pontot kapott:	Bodor Mátyás, Chrobák Gergő, Csonka Illés, Czirják Márton Pál, Diaconescu Tashi, Fülöp Csilla, Holló Martin, Horváth 530 Mihály, Kosztolányi Karina, Kovács Benedek Noel, Máté Lőrinc, Melján Dávid Gergő, Mizik Lóránt, Molnár István Ádám, Nádor Artúr, Nguyen Kim Dorka, Prohászka Bulcsú, Sárdinecz Dóra, Szakács Ábel, Szanyi Attila, Tarján Bernát, Varga Boldizsár, Vigh 279 Zalán, Zhai Yu Fan, Zömbik Barnabás.
5 pontot kapott:	Kocsis 827 Péter, Virág Rudolf.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2023. februári matematika feladatai