Egy OKTV feladat margójára

A 2020-21-es tanév Országos Középiskolai Tanulmányi versenye is hasonlóan alakult a pandémia miatt, mint az előtte levő évben. Mindkét esetben a matematika OKTV gimnáziumi (II-es) kategória első és második fordulóját meg lehetett rendezni, de a tavaszi terminusra eső döntőre már nem került sor. Az alábbiakban az említett kategória második fordulójának negyedik feladatát vesszük alaposabban szemügyre.

A versenyt kevésbé ismerők kedvéért nézzük meg, hogy is épül fel az OKTV verseny a II-es kategóriában. Általában az őszi szünet és a Mikulás között zajlik az első, iskolai forduló, január második felében a második forduló, majd márciusban a döntő. Az első fordulóban résztvettek 10 százaléka, de legfeljebb 300 diák juthat a másodikba, majd a döntőbe a legjobb 50 kerülhet. Minden fordulóban öt óra áll a versenyzők rendelkezésére, hogy megírják dolgozatukat. Az érettségihez hasonlóan zsebszámológép használható. Az egyes fordulókban szereplő feladatokat igyekeznek úgy összeállítani az Oktatási Hivatal által felkért bizottság tagjai, hogy minden fordulóban legyen nehezebb és könnyebb feladat is, lehetőleg változatos témák szerepeljenek. Hagyományosan az elsőben öt, a másodikban négy, a harmadikban három feladat kerül kitűzésre.

A bevezetőben említett feladat kapcsán a dolgozatok javításánál már kiderült, hogy a javítási útmutatóban szereplő viszonylag rövid megoldást nagyon kevesen találták meg és jóval hosszadalmasabb úton jutottak el a válaszhoz. Dr. Horváth Eszter tanárnő is felhívta erre a figyelmemet és ő javasolta, hogy érdemes lenne a feladatot egy Érintő-cikk keretében kicsit körbejárni. Erre invitálom most az Olvasót. A feladat szövege a következő:

Legyen pozitív egész. Vegyünk darab különböző prímszámot, jelölje szorzatukat . Tekintsük azon pozitív egész számokat, amelyekre osztója -nek és osztója -nek. Igazoljuk, hogy ezen párok száma 5-tel osztható.

A feladat a számelmélet témakörébe vezet, oszthatóság szerepel benne. A továbbiakban nem hangsúlyozzuk minden alkalommal, hogy csak a pozitív egészek körében fogunk dolgozni. Mielőtt teljes megoldást adnánk, először ismerkedjünk, barátkozzunk a feladat szövegével. Nézzük meg egy kicsi, konkrét számon, miket kell megszámolni. Az $n=1$ a lehető legkisebb eset, válasszük a két legkisebb prímet, a 2-őt és a 3-at. Ekkor $L=6$ , ennek osztói az 1, 2, 3, 6 számok, ezek lehetnek az $a$ és $b$ értékek. Ezek után egyszerű felsorolással megkereshetjük a megfelelő $(a;b)$ párokat: (1;2), (1;3), (1;6), (2;6), (3;6). A megfelelő párok száma öt, ami osztható 5-tel, így ekkor valóban teljesülnek a feladat feltételei. Miközben ezt kiszámoltuk, azonnal tehetünk két észrevételt:

(i) Egy $S$ szám osztóinak számát a prímtényezős felbontás ismeretében meghatározhatjuk. Legyen

$\displaystyle S=p_1^{k_1} \cdot p_2^{k_2} \cdot\ldots \cdot p_t^{k_t},$

jelölje $S$ osztóinak számát $d(S)$ . Ekkor

$\displaystyle d(S)=(k_1+1)(k_2+1)\ldots (k_t+1),$

ezt a versenyzőknek nem kellett külön bebizonyítani, nyugodtan hivatkozhattak rá a tananyag részeként.

(ii) A feladat szövegében szerepel az oszthatósági feltételen kívül az $a<b$ feltétel. Kényelmesebb először az összes oszthatósági feltételnek megfelelő $(a;b)$ számpárt megkeresni, majd ezek számából levonni az $a=b$ eseteket. Ez az $L=6$ -nál azt jelenti, hogy összesen 9 számpár van, de ezek közül négyet nem kell számolni, amikor $a$ és $b$ egyaránt egyenlő az 1, 2, 3, 6 számok valamelyikével.

Első (kicsit hosszabb) megoldás:

Az (ii) megjegyzés alapján a megfelelő $(a;b)$ számpárok leszámolását úgy végezzük, hogy először megengedjük az $a=b$ esetet, majd az így kapott számból levonjuk a végén ezeket. Mivel $L$ prímtényezős felbontásában $2n$ darab különböző prím szerepel, továbbá mindegyik az első hatványon van, ezért a lehetséges $b$ osztókat úgy kapjuk, hogy a $2n$ prím közül néhányat beleteszünk $b$ -be. Ha $k$ darabot választunk, akkor az ilyen $b$ -k száma $2n \choose k$ . Amennyiben $b$ -ben $k$ darab különböző prím van, mindegyik a feladat szövege szerint nyilván első hatványon, akkor a $k$ darab prím mindegyikéről egymástól függetlenül eldönthatjük, hogy beletesszük $a$ prímtényezős felbontásába vagy sem. Ezért $2^k$ féleképpen válaszhatjuk ki az $a$ értékét. Most már ki is számolhatjuk az $(a;b)$ számpárok számát:

$\displaystyle {2n \choose 0} \cdot 2^0+{2n \choose 1} \cdot 2^1+{2n \choose 2} \cdot 2^2+\ldots +{2n \choose 2n} \cdot 2^{2n}.$

Ez az összeg kissé ijesztő lehet (pláne, ha az ember életében először egy ötórás verseny közepén találkozik vele). Alaposabban megnézve azonban azt láthatjuk, hogy a binomiális tétel segítségével a hosszú összeg megszelidíthető, hiszen értéke éppen $(1+2)^{2n}=3^{2n}$ .

Most nézzük meg, mit kell ebből kivonni. Ha $a=b$ , akkor az ilyen számpárok száma éppen az összes lehetséges $b$ érték száma, tehát $2^{2n}$ . Most felírhatjuk a feladat szövegében keresett számpárok számát, ez $3^{2n}-2^{2n}$ . Azt kell bebizonyítani, hogy ez minden $n$ esetén osztható 5-tel. A középiskolai tananyagban szerepel, hogyan lehet szorzattá alakítani az $x^n-y^n$ alakú kifejezéseket. Ennek segítségével

$\displaystyle 3^{2n}-2^{2n}=(3^2)^n-(2^2)^n=(3^2-2^2)(3^{2(n-1)}+3^{2(n-2)} \cdot 2^2+\ldots +3^2 \cdot 2^{2(n-2)}+2^{2(n-1)}).$

A szorzat első tényezője $3^2-2^2=5$ , ezzel az állítást beláttuk.

Azok a versenyzők, akik a binomiális tétel alkalmazhatóságát nem vették észre, bizony gyakran jóval hosszadalmasabb érvelésre kényszerültek. Most, hogy egy megoldást már végignéztünk, érdemes kicsit visszatekinteni. Ezt ajánlom mind tanároknak, mind diákoknak! Ne hagyjuk ott a feladatot, amint kész a megoldás! Járjuk végig újra az utat, elemezzük, mit is csináltunk! A feladat szövegének megértése, a feltételek szerinti számpár keresése oszthatósági probléma. A megfelelő számpárok leszámolása kombinatorikus lépést igényel. Végül következik a számpárok számának öttel való oszthatósági vizsgálata, melyet így is elvégezhetünk: $3^{2n}-2^{2n}=9^n-4^n$ . Mivel 9 és 4 ötös maradéka megegyezik, ezért azonos hatványaiknak az ötös maradéka is megegyezik, tehát különbségük osztható öttel. A kongruenciák nyelvén: $9\equiv 4$ (mod 5), tehát $9^n\equiv 4^n$ (mod5), azaz $5\vert 9^n-4^n$ . Az alábbi, második megoldás a kombinatorikus lépést másként kezeli.

Második megoldás (ez szerepelt a javítási útmutatóban):

Legyen $L=p_1 \cdot \ldots \cdot p_{2n}$ , a $p_i$ prím kitevője legyen $a$ -ban $\alpha_i$ , $b$ -ben $\beta_i$ . Amennyiben az $a=b$ eseteket is megszámoljuk, akkor minden prím esetén a feladat feltétele miatt a lehetséges $(\alpha_i,\beta_i)$ párok: (0,0), (0,1) és (1,1). Tehát három lehetőség van. Mivel $2n$ prím van és a kitevőket egymástól függetlenül választhatjuk, ekkor az $(a,b)$ párok száma $3^{2n}$ . Ebből ki kell vonni azon párok számát, ahol $a=b$ . Minden $i$ -re $\alpha_i=\beta_i$ és értéke 0, vagy 1. Tehát két lehetőség van. Most is a kitevőket egymástól függetlenül választhatjuk, így az $a=b$ párok száma $2^{2n}$ . Már meg is kaptuk a keresett számpárok számát: $3^{2n}-2^{2n}$ . Innen a befejezés az első megoldás végén található szorzattá alakítással adódik.

Az egyik versenyző ezt a gondolatmenetet a következő módon szemléltette. Tekintsük $L$ összes prímosztójának $H$ halmazát. Ennek egy $B$ részhalmaza lesz a $b$ -ben szereplő prímek, majd ezen $B$ halmazon belül, $B$ -nek részhalmazaként kapjuk az $A$ halmazt. Ez utóbbiban legyenek az $a$ -ban szereplő prímek. Ábránk így néz ki:

Ha $a=b$ is lehet, akkor minden egyes prímről eldönthetjük, hogy az ábrán szereplő három rész melyikébe kerül, a legbelső körbe, a középső gyűrűbe vagy a szélső gyűrűbe. Ebből adódik a $3^{2n}$ . Azon számpárok esetében, ahol $a=b$ , a prím a középsőbe nem kerülhet, így ezek száma $2^{2n}$ .

Harmadik megoldás:

A gyakorlott problémamegoldó számára a feladat szövegének első mondata egy meghívást jelenthet arra, oldjuk meg indukcióval a feladatot. A kezdő lépést már korábban elvégeztük, $n=1$ esetén igazoltuk az állítást. Most következhet az indukciós lépés. Feltesszük, hogy az állítás igaz $2n$ -re és ennek segítségével bebizonyítjuk $2n+2$ -re. Tekintsünk egy olyan $L$ számot, aminek $2n+2$ különböző prímosztója van, ezek küzöl legyen a két legnagyobb $p$ és $q$ . Tekintsük az $L'=L:(pq)$ számot, ennek $2n$ prímosztója van, alkalmazható rá az indukciós feltétel. Soroljuk fel $L'$ összes megfelelő $a$ és $b$ számpárját, legyen ezek száma $5k$ . Az $L$ megfelelő számpárjait úgy vizsgáljuk, hogy az $a<b$ feltétel már az $L'$ -ben szereplő prímeket tekintve teljesül vagy nem. Az első esetben megnézzük, hogy $L'$ számpárjait megszorozzuk-e a két legnagyobb prímmel. Jó párok lesznek $(a;b)$ , $(a;pb)$ , $(pa;pb)$ ; $(a;qb)$ , $(qa;qb)$ , $(a;pqb)$ , $(pa;pqb)$ , $(qa;pqb)$ , $(pqa,pqb)$ számpárok, ezek száma $9 \cdot 5k$ , ami osztható öttel. A második esetben meg kell számolnunk azokat a párokat, ahol $a=b$ . $L'$ -nek egy tetszőleges osztóját választjuk, legyen ez $d$ . Ebből $p$ és $q$ segítségével a következő számpárok készíthetők: $(d, pd)$ , $(d,qd)$ , $(d;pqd)$ , $(pd;pqd)$ , $(qd;pqd)$ . Mivel minden $d$ esetén ötféle új számpár készíthető, ezért itt is öttel osztható lesz a megfelelő számpárok száma. Megszámoltuk $L$ összes megfelelő számpárját és ez két öttel osztható szám összegeként adódótt, tehát az idukciós állítást bizonyítottuk.

Megjegyzésként hozzáfűzném, hogy a feladat megoldására „rímel” egy korábbi OKTV példa. Az 1995-ös év II. kategóriás döntőjének első feladata a következő volt:

Adott a $H=\{1, 2, 3, 4, 5\}$ halmaz. Készítsük el ennek összes részhalmazát. Vegyük egyenként az így kapott halmazokat, és mindegyiknek minden részhalmazát írjuk fel külön-külön egy-egy piros cédulára. Így a piros cédulák között lehetnek olyanok, amelyekre ugyanaz a részhalmaz van felírva, de mindet megtartjuk. Vegyük most sorra egyesével a piros cédulákat, és a rajtuk levő halmaz minden részhalmazát külön-külön felírjuk egy-egy fehér cédulára. Vegyük végül sorra a fehér cédulákat, és a rajtuk levő halmaz minden részhalmazát külön-külön felírjuk egy-egy zöld cédulára. Hány zöld cédulát kell így felhasználnunk?

A két feladat hasonló vonása az, hogyan számoljuk meg egy $H_0$ halmaz olyan $H_1$ , $H_2$ , ..., $H_i$ részhalmazláncainak számát, amelyekre $j=1,2,\ldots ,i$ esetén a $H_j$ halmaz részhalmaza $H_{j-1}$ -nek. Az idei feladatban $i=2$ , a 95-ös példában $i=4$ szerepelt. A részhalmazláncok száma $H_0=n$ esetén $(i+1)^n$ , hiszen $H_0$ mind az $n$ darab eleménél egymástól függetlenül eldönthetjük, melyik a legnagyobb $j$ index, amely $H_j$ -ben az elem még szerepel. Itt most $j$ értéke 0 és $i$ közt bármi lehet, azaz $i+1$ lehetőség van.

Remélem a tehetséggondozásban munkálkodó kollégáknak és az érdeklődő diákoknak egyaránt hasznos dolgokra sikerült rávilágítani ezzel a kis összeállítással.

Dobos Sándor

Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium