 |
A B. 5536. feladat (2026. május) |
B. 5536. Egy szabályos hatszög csúcsaiba hat természetes számot írtunk, amelyek összege \(\displaystyle 2027\). Egy lépésben a hat szám közül egyet kicserélünk a két szomszédos csúcsban álló szám különbségének abszolút értékével.
Elérhető-e ilyen lépésekkel, hogy mindegyik csúcsban \(\displaystyle 0\) álljon?
Javasolta: Róka Sándor (Nyíregyháza)
(5 pont)
A beküldési határidő 2026. június 10-én LEJÁRT.
Megoldás. A hatszög csúcsaiba írt természetes számokat \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\), \(\displaystyle D\), \(\displaystyle E\) és \(\displaystyle F\) fogja jelölni (a hat számot ebben a sorrendben írjuk a hatszög csúcsaihoz). Továbbá – az alábbi ábra alapján – az \(\displaystyle A\), \(\displaystyle C\) és \(\displaystyle E\) másodszomszédos számokat ,,kiszínezzük szürkére'' (és szürke számokként fogunk hivatkozni rájuk), míg a másik három \(\displaystyle B\), \(\displaystyle D\) és \(\displaystyle F\) másodszomszédos számot fehér számoknak hívjuk. Ha néhány szabályos lépést teszünk a hatszögünk számain; az új állapotban lévő számokat az \(\displaystyle A'\), \(\displaystyle B'\), \(\displaystyle C'\), \(\displaystyle D'\), \(\displaystyle E'\) és \(\displaystyle F'\) betűkkel fogjuk jelölni.
A feladatot általánosabban oldjuk meg, a következő lemmát kimondva:
Lemma: Ha a hat (a hatszög csúcsába írt) szám összege páratlan, akkor a megengedett műveletekkel minden esetben elérhető, hogy (véges sok lépés után) a hat szám mindegyike \(\displaystyle 0\) legyen.
Mivel \(\displaystyle 2027\) páratlan szám, a lemma következményeként adódik, hogy a feladat kérdésére is igen a válasz.
Mielőtt a lemma bizonyítására rátérünk, mutatunk példát olyan hat, a hatszög csúcsaira írt számra, hogy a megengedett lépésekkel ne lehessen elérni a csupa \(\displaystyle 0\) állapotot. Tekintsük a következő ábrát.
Azaz legyenek \(\displaystyle A=B=D=E=1\) és \(\displaystyle C=F=0\). Azonnal látszik, hogy bármelyik csúcsra is alkalmazzuk a megengedett lépést a csúcsban lévő szám nem változik (például \(\displaystyle A'=|B-F|=|1-0|=1=A\), vagy \(\displaystyle C'=|D-B|=|1-1|=0=C\)), így valóban nem érhető el a csupa \(\displaystyle 0\) állapot. Sőt, ha a hat szám \(\displaystyle \pmod 2\) veszi fel a \(\displaystyle A=B=D=E=1\) és \(\displaystyle C=F=0\) értéket (azaz pontosan \(\displaystyle C\) és \(\displaystyle F\) számok párosak), akkor sem érhető el a csupa \(\displaystyle 0\) állapot, hiszen a számok paritása ezen kezdőértékek esetén nyilván megmarad, azaz bármely állapotban pontosan négy darab páratlan számunk lesz.
Most pedig lássuk a lemma bizonyítását. Mivel a hat szám összege páratlan, ezért a szürke számok összege (azaz \(\displaystyle A+C+E\)) és a fehér számok összege (azaz \(\displaystyle B+D+F\)) közül pontosan az egyik páratlan. Az általánosság megszorítása nélkül feltehetjük, hogy a szürke számok összege páratlan, és a fehér számok összege páros.
Három különböző típusú (több lépésből álló) lépéssorozatot definiálunk, amelyeket véges sokszor használva el fogjuk érni a ,,csupa \(\displaystyle 0\) számhatost'', így voltaképpen egy algoritmust is definiálva, aminek az eredménye a kívánt csupa \(\displaystyle 0\) végállapot.
– \(\displaystyle \mathbb{A}\) lépéssorozat; ezt akkor alkalmazzuk, ha a szürke \(\displaystyle A\), \(\displaystyle C\) és \(\displaystyle E\) számok egyike sem \(\displaystyle 0\). Ekkor az általánosság megszorítása nélkül feltehető, hogy \(\displaystyle A \geq C \geq E >0\) (különben a számok ,,átcimkézhetőek'', vagy a hatszög elforgatható). Alkalmazzunk szabályos lépéseket rendre a \(\displaystyle B\), \(\displaystyle D\) és \(\displaystyle F\) számokra, így kapjuk, hogy \(\displaystyle B'=A-C\), \(\displaystyle D'=C-E\) és \(\displaystyle F'=A-E\) (az alábbi ábrán az első nyíl utáni állapot), majd az \(\displaystyle A\) és végül az \(\displaystyle E\) számokra, így kapjuk, hogy \(\displaystyle A'=F'-B'=C-E\) és \(\displaystyle E'=F'-D'=A-C\) (és persze \(\displaystyle C'=C\) marad).
Az \(\displaystyle \mathbb{A}\) lépéssorozat hatására a fehér számok összege \(\displaystyle B'+D'+F'=2(A-E)\) páros marad, a szürke számok összege \(\displaystyle A'+C'+E'=A+C-E=A+C+E-2E\) pedig páratlan marad, és pontosan a \(\displaystyle 2E>0\) pozitív páros számmal csökken, továbbá – természetesen – mind a hat új szám nemnegatív egész marad. Mivel az \(\displaystyle A+C+E\) összeget csak véges sokszor tudjuk úgy pozitív páros számmal csökkenteni, hogy \(\displaystyle A',C'\) és \(\displaystyle E'\) továbbra is nemnegatív egészek legyenek, ezért az \(\displaystyle \mathbb{A}\) lépéssorozatot csak véges sokszor alkalmazhatjuk, és amikor már nem tudjuk többször alkalmazni az pontosan azt jelenti, hogy \(\displaystyle A', C'\) és \(\displaystyle E'\) számok valamelyike (esetleg egyszerre több is) 0. Ekkor következik a \(\displaystyle \mathbb{B}\) (ha pedig \(\displaystyle A',C',E'\) közül több is \(\displaystyle 0\) akkor a \(\displaystyle \mathbb{C}\)) lépéssorozat.
– \(\displaystyle \mathbb{B}\) lépéssorozat; ezt akkor alkalmazzuk, ha a szürke \(\displaystyle A\), \(\displaystyle C\) és \(\displaystyle E\) számok közül pontosan egy, mondjuk \(\displaystyle E=0\). Ekkor az általánosság megszorítása nélkül feltehető, hogy \(\displaystyle A \geq C \geq E =0\). Továbbá mivel \(\displaystyle A+C+E=A+C\) páratlan, így \(\displaystyle A>C\), azaz \(\displaystyle 0<A-C<A\) és innen \(\displaystyle -A<A-2C<A-C<A\), azaz \(\displaystyle |A-2C|<A\). Alkalmazzunk szabályos lépéseket (az előzőekhez hasonlóan) rendre a \(\displaystyle B\), \(\displaystyle D\) és \(\displaystyle F\) számokra, így kapjuk, hogy \(\displaystyle B'=A-C\), \(\displaystyle D'=C-0=C\) és \(\displaystyle F'=A-0=A\) (az alábbi ábrán az első nyíl utáni állapot), majd az \(\displaystyle A\) és végül a \(\displaystyle C\) számokra, így kapjuk, hogy \(\displaystyle A'=F'-B'=A-(A-C)=C\) és \(\displaystyle C'=|B'-D'|=|A-2C|\) (és persze \(\displaystyle E'=0\) marad).
A \(\displaystyle \mathbb{B}\) lépéssorozat hatására a fehér számok összege \(\displaystyle B'+D'+F'=2A\) páros marad, a szürke számok összege \(\displaystyle A'+C'+E'=C+|C-2A|+0\) pedig páratlan marad, és mivel \(\displaystyle |C-2A|<A\) ezért csökken is (megint legalább 2-vel), továbbá – természetesen – mind a hat új szám újra csak nemnegatív egész marad. Mivel az \(\displaystyle A+C+E\) összeget csak véges sokszor tudjuk úgy pozitív páros számmal csökkenteni, hogy \(\displaystyle A',C'\) és \(\displaystyle E'\) továbbra is nemnegatív egészek legyenek, ezért az \(\displaystyle \mathbb{B}\) lépéssorozatot is csak véges sokszor alkalmazhatjuk, és amikor már nem tudjuk többször alkalmazni az pontosan azt jelenti, hogy \(\displaystyle A'\) és \(\displaystyle C'\) számok közül (az eddig is \(\displaystyle 0\) értékű \(\displaystyle E\) mellett) valamelyik szintén 0. Mivel \(\displaystyle A'=C >0\) ez pontosan akkor következik be, ha \(\displaystyle C'=|A-2C|=0\). Ekkor következik majd a \(\displaystyle \mathbb{C}\) lépéssorozat.
– \(\displaystyle \mathbb{C}\) lépéssorozat; ezt pedig akkor alkalmazzuk, ha a szürke \(\displaystyle A\), \(\displaystyle C\) és \(\displaystyle E\) számok közül (legalább) kettő, mondjuk \(\displaystyle C=E=0\). Innen triviális mit kell csinálnunk. Alkalmazzunk szabályos lépéseket (az előzőekhez hasonlóan) rendre a \(\displaystyle B\), \(\displaystyle D\) és \(\displaystyle F\) számokra, így kapjuk, hogy \(\displaystyle B'=A-0=A\), \(\displaystyle D'=0-0=0\) és \(\displaystyle F'=A-0=A\) (az alábbi ábrán az első nyíl utáni állapot), majd az \(\displaystyle A\) számra, így kapjuk, hogy \(\displaystyle A'=F'-B'=A-A=0\) és végül újra a \(\displaystyle B'\) és \(\displaystyle F'\) számokra, kapva, hogy \(\displaystyle B''=A'-C'=0-0=0\) és \(\displaystyle F''=A'-E'=0-0=0\). Azaz ekkor el is érjük a csupa \(\displaystyle 0\) (vég)állapotot.
A fentiek – nyilvánvalóan – egy véges lépésben véget érő eljárást is definiálnak, amelyet végrehajtva tetszőleges hat páratlan összegű természetes számból kiindulva elérjük a csupa \(\displaystyle 0\) végállapotot. Az algoritmusunk lépései (feltéve, hogy a szürke számok összege páratlan):
Az algoritmus leírása:
1. lépés): Amennyiben az \(\displaystyle A,C,E\) szürke számok valamelyike \(\displaystyle 0\) folytassuk a 2. lépéssel, amennyiben pedig az \(\displaystyle A\), \(\displaystyle C\), \(\displaystyle E\) szürke számok egyike sem \(\displaystyle 0\), hajtsuk végre az \(\displaystyle \mathbb{A}\) lépéssorozatot, majd térjünk vissza újra (az új számokkal) az 1. lépés elejére.
2. lépés): Amennyiben az \(\displaystyle A\), \(\displaystyle C\), \(\displaystyle E\) szürke számok közül legalább kettő \(\displaystyle 0\) folytassuk a 3. lépéssel, amennyiben pedig az \(\displaystyle A\), \(\displaystyle C\), \(\displaystyle E\) szürke számok közül pontosan egy darab \(\displaystyle 0\), hajtsuk végre az \(\displaystyle \mathbb{B}\) lépéssorozatot, majd térjünk vissza újra (az új számokkal) a 2. lépés elejére.
3. lépés): (Ekkor az \(\displaystyle A\), \(\displaystyle C\), \(\displaystyle E\) szürke számok közül legalább kettő \(\displaystyle 0\).) Hajtsuk végre a \(\displaystyle \mathbb{C}\) lépéssorozatot pontosan egyszer, ezzel (a fentebb leírtak alapján) elérjük a csupa \(\displaystyle 0\) végállapotot.
Ezzel készen vagyunk, mivel a hatszög csúcsaiba írt természetes számok összege 2027 (azaz páratlan), az eljárásunkat végrehajtva véges lépésben elérjük a csupa \(\displaystyle 0\) végállapotot, azaz a feladat kérdésére igen a válasz.
Statisztika:
A B. 5536. feladat értékelése még nem fejeződött be.
A KöMaL 2026. májusi matematika feladatai