Fried Katalin
A KöMaL 74. évfolyam 7. számában jelent meg a B. 5390. feladatnak két szép versenyzői megoldása. A feladat:
B. 5390. Léteznek-e olyan \(\displaystyle a_0\), \(\displaystyle a_1\), \(\displaystyle \ldots\), \(\displaystyle a_{n-1}\) páros egész számok, amelyekre az \(\displaystyle x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\) polinom osztható az \(\displaystyle x^2+x+1\) polinommal?
(3 pont)
Javasolta: Kós Géza (Budapest)
Vagyis – kicsit másképpen fogalmazva – a feladatban arra kerestük a választ, hogy van-e olyan \(\displaystyle s(x)\) polinom, amellyel megszorozva a \(\displaystyle q(x)=x^2+x+1\) polinomot olyan \(\displaystyle p(x)=x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\) (nem azonosan nulla) egész együtthatós polinomot kapunk, amelynek ismeretlen együtthatói páros számok.
Megjegyzés a beküldött megoldásokhoz.
A legtöbb megoldó ,,visszaszorzással'' kereste az \(\displaystyle s(x)\) polinomot – és indirekt úton mutatta meg, hogy ilyen nincs.
Többen viszont polinomosztással oldották meg a feladatot. Mivel a kétféle hozzáállás lényegében ugyanazt a gondolatmenetet követi, ilyen megoldást nem közöltünk, ám a polinomosztásról, illetve a feladat polinomosztással történő megoldásáról érdemes néhány szót ejteni.
A valós együtthatós polinomokra vonatkozó maradékos osztás tétel szerint minden \(\displaystyle p(x)\) és \(\displaystyle q(x)(\not\equiv 0)\) valós együtthatós polinomhoz pontosan egy olyan \(\displaystyle s(x)\) és \(\displaystyle r(x)\) ugyancsak valós együtthatós polinom létezik, amelyekre \(\displaystyle p(x)=q(x)\cdot s(x)+r(x)\), ahol \(\displaystyle r(x)\) vagy az azonosan nulla polinom, vagy alacsonyabb a fokszáma, mint \(\displaystyle q(x)\)-é. (Egy polinom foka a legmagasabb fokú tag kitevője, de az azonosan nulla polinom fokszámát – más konstans polinomok fokszámával ellentétben – a maradékos osztás szemszögéből nem tekintjük 0-nak.)
Esetünkben nem valós, hanem egész együtthatós polinomok körében keressük a hányadost és a maradékot, de – mint hamarosan kiderül – ez nem okoz gondot.
A polinomosztás azon alapul, hogy úgy tekinthetünk egy valós együtthatós polinomra, mintha egy \(\displaystyle x\) alapú számrendszerben felírt ,,szám'' lenne, ahol a ,,számjegyek'' – a polinom együtthatói – tetszőleges valós számok lehetnek. Az eljárás a tízes számrendszerben felírt természetes számok körében már ismert maradékos osztáséhoz hasonlítható, ahol helyiértékcsoportról helyiértékcsoportra haladva keresünk olyan egyjegyű hányadost, hogy a maradék az osztónál kisebb nemnegatív szám legyen. A polinomosztáskor az a cél, hogy minden lépésben a maradék vagy a 0 legyen, vagy a fokszáma kisebb legyen az osztó fokszámánál. Bármely valós szám lehet együttható, akár negatív szám is.
Ha például a \(\displaystyle 8x^2+6x+2\) polinomot elosztjuk a \(\displaystyle 2x+6\) polinommal, akkor voltaképpen az \(\displaystyle x\) alapú számrendszerben felírt \(\displaystyle 862_x:26_x\) maradékos osztást végezzük el.
Hasonlítsuk össze a tízes és az \(\displaystyle x\) alapú számrendszerben felírt \(\displaystyle 862:26\), illetve \(\displaystyle 862_x:26_x\) maradékos osztást.
A tízes számrendszerben felírt maradékos osztás szerint 86-ban a 26 megvan 3-szor, mert \(\displaystyle 3\cdot 26=78\), és marad \(\displaystyle 86-78=8\). (Valójában: 860-ban a 26 megvan 30-szor, és marad 80.) \(\displaystyle 80+2=82\), 82-ben a 26 megvan 3-szor, mert \(\displaystyle {3\cdot 26}=78\), és marad \(\displaystyle 82-78=4\). Tehát a hányados 33, a maradék 4.
Ezzel szemben \(\displaystyle {(8x^2+6x)}\)-ben a \(\displaystyle 2x+6\) megvan 4-szer (\(\displaystyle 4x\)-szer), hiszen a lehető legkisebb fokszámú (vagy 0) maradékot kell kapnunk, a maradék \(\displaystyle (8x^2+6x)-{x\cdot(2x+6)}=-18x\). Az osztandóhoz hosszávesszük a következő tagot: \(\displaystyle {(-18x+2)}\)-ben a \(\displaystyle 2x+6\) megvan \(\displaystyle (-9)\)-szer, mert \(\displaystyle (-9)\cdot(2x+6)={-18x-54}\), és marad \(\displaystyle -18x+2+18x+54=56\). Tehát \(\displaystyle s(x)=4x-9\), \(\displaystyle r(x)=56\).
Mielőtt nekilátnánk a B. 5360. feladat polinomosztással történő megoldásának, tisztáznunk kell, miért nem jelent problémát, hogy az osztást valós együtthatójú polinomokon végezzük, a megoldásunkban pedig egész együtthatósak szerepelnek. Mivel \(\displaystyle p(x)\) és \(\displaystyle q(x)\) is egész együtthatós és \(\displaystyle q(x)\) főegyütthatója (vagyis a legmagasabb fokú tag együtthatója) 1, így bármely részosztásban adott polinomot \(\displaystyle q(x)\)-szel osztva a hányados főegyütthatója (a hányados soronkövetkező együtthatója) az osztandó főegyütthatójával egyenlő. Mivel pedig ez minden lépésben egész szám, a maradék (\(\displaystyle r(x)\)) és a hányados (\(\displaystyle s(x)\)) is egész együtthatós polinom lesz.
Lássuk most a feladat megoldását. A kitűzött feladatban nincsenek megadva konkrétan \(\displaystyle p(x)\) együtthatói. Kis próbálkozás és gondolkozás után viszont azt sejthetjük, hogy ilyen együtthatók nem léteznek, és az ellentmondást az együtthatók paritása okozza, ezért megpróbálkozhatunk azzal az ötlettel, hogy a polinomosztás során az együtthatóknak csak a kettes maradékával számolunk. Ez azt jelenti, hogy a páros együtthatók helyére 0-t, a páratlan együtthatók helyére 1-et írunk. A kettes maradékok körében a következő műveleti szabályok érvényesek: \(\displaystyle 0\pm 0=1\pm 1=0\), \(\displaystyle 0\pm 1=1\pm 0=1\); \(\displaystyle 0\cdot 0=0\cdot 1=1\cdot 0=0\), \(\displaystyle 1\cdot 1=1\).
Eszerint tehát \(\displaystyle p(x)\)-et: \(\displaystyle 1\underbrace{00\ldots0}_{\text{\(\displaystyle n\) darab}}{}_x\) alakban írhatjuk fel, míg \(\displaystyle q(x)\) alakja \(\displaystyle 111_x\).
Az osztó ,,háromjegyű'', ezért az osztandót ,,háromjegyű'' részletekben tekintjük. Írjuk fel a kettes maradékos írásbeli polinomosztás első néhány lépését.
Vegyük észre, hogy a maradékok rendre ,,11'', ,,(0)1'', ,,10'', és mivel a harmadik lépésben a kiinduló ,,100'' számot osztjuk tovább, a maradékok ismétlődnek, így az soha nem lehet nulla, vagyis ha az osztandó legalább harmadfokú, akkor eszerint nem lehet \(\displaystyle x^2+x+1\) többszöröse.
Ha viszont az osztandó fokszáma legfeljebb 2, akkor az eredeti polinomnak az együtthatók paritása szerint megfelelő felírás \(\displaystyle 100_x\), \(\displaystyle 10_x\) vagy 1, de ezek egyike sem többszöröse \(\displaystyle 111_x\)-nek, mert \(\displaystyle 100_x=1\cdot 111_x+11_x\), a másik két esetben az osztandó eleve kisebb fokszámú, mint az osztó, így az osztási maradék egyik esetben sem 0.
Tehát nincs a feltételeknek megfelelő \(\displaystyle s(x)\) polinom, vagyis nincsenek olyan páros \(\displaystyle a_i\) (\(\displaystyle 0\leq i<n\)) egész együtthatók, amelyekre \(\displaystyle x_n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\) osztható az \(\displaystyle x^2+x+1\) polinommal.
A KöMaL levelezős versenyei azon kevesek közé tartoznak, amelyek ingyenesek – immár több mint 130 éve! Sajnos azonban a KöMaL állami támogatásának rendszere az elmúlt évben jelentősen átalakult, a következő években az előre látható bevételeink várhatóan nem tudják fedezni a költségeinket.
Ezért kérünk mindenkit, aki szereti a KöMaL-t, létezését fontosnak tartja, hogy lehetőségéhez mérten támogassa a KöMaL-t kiadó MATFUND Alapítványt. Ha teheti, rendelkezzen adója 1%-áról az Alapítvány javára. Ezen kívül pedig, ha saját vagy céges lehetőségei megengedik, támogassa a KöMaL kiadását, a KöMaL tudáskincsének gondozását!
A KöMaL kiadásának, a versenyek teljes lebonyolításának, díjazásának és a díjkiosztóval egybekötött Ifjúsági Ankétok szervezésének költségeit 2007 óta a MATFUND Középiskolai Matematikai és Fizikai Alapítvány fizeti.
Kérjük, személyi jövedelemadója 1%-ának felajánlásával álljon a több, mint 125 éve alapított Középiskolai Matematikai és Fizikai Lapok mellé!
A KöMaL 2025 szeptemberi számában (Tait tétele és a 3-reguláris gráfok – a B. 5403. feladat háttere) kimondtuk Tait alábbi tételét.
Tétel (Tait tétele). Legyen \(\displaystyle G\) egy 3-reguláris, hídélmentes, síkbarajzolt gráf. Ekkor \(\displaystyle G\) tartományai \(\displaystyle 4\)-színezhetők akkor és csak akkor, ha élei \(\displaystyle 3\)-színezhetők.
A tételben \(\displaystyle k\)-színezésen olyan színezést értünk, amely \(\displaystyle k\)-féle színt használ, és az egymással szomszédos tartományok (illetve élszínezés esetén az egy csúcsban találkozó élek) mindig különböző színűek.
A szeptemberi számba nem került be a tétel bizonyítása (azzal a céllal, hogy akinek van kedve, gondolkodhasson rajta), ezt most pótoljuk.
Nem kell túl sokáig keresgélnünk az interneten a fejtörő feladatok között ahhoz, hogy sík vagy tér kitöltésére vonatkozó feladványra bukkanjunk. Ezek egyik fajtája az, amikor néhány síkidom vagy test valamilyen keretben van elhelyezve úgy, hogy látszólag teljesen kitöltik azt, de van még külön egy további eleme a játéknak.
