A 2024-es MEMO néhány feladatának részletes megoldása

A 2024-es MEMO-n (Közép-Európai Matematikai Diákolimpián) az egyéni versenyen négy, a csapatversenyen nyolc feladat került kitűzésre. E feladatok közül adunk közre egy válogatást részletes megoldásokkal. A megoldásokat a magyar csapat tagjai írták le.

A csapat beszámolója a versenyről itt olvasható: 1. rész, 2. rész.

A teljes feladatsor és az angol nyelvű megoldások a MEMO hivatalos honlapján érhetők el.

I-1. feladat

Határozd meg az összes olyan $k\in \mathbb{N}_0$ számot, amelyre létezik olyan $f\colon \mathbb{N}_0\rightarrow\mathbb{N}_0$ függvény, hogy $f(2024)=k$ és

$\displaystyle f(f(n))\leq f(n+1)-f(n)$

teljesül minden $n\in\mathbb{N}_0$ számra.

Megjegyzés. A feladatban $\mathbb{N}_0$ a nemnegatív egész számok halmazát jelöli.

Prohászka Bulcsú megoldása

A válasz az, hogy pontosan azok a $k$ -k teljesítik a feltételt, amelyekre $0\leq k\leq 2023$ . Ezekre gyorsan mutatunk is egy megfelelő függvényt: $f(n)$ legyen 0, ha $n\leq k$ , és legyen $k$ , ha $n>k$ . Vegyük észre, hogy ebben az esetben $f(f(n))=0$ minden $n$ -re, hisz $f(n)\leq k$ , továbbá, hogy ez a függvény (kicsit furcsán, de) monoton nő, vagyis $f(n)\leq f(n+1)$ minden $n$ -re. Viszont így tudjuk, hogy $f(f(n))=0\leq f(n+1)-f(n)$ , vagyis a függvényünk tényleg teljesíti a feltételt.

Lássuk, hogy miért nem teljesülhet $f(2024)\geq2024$ . Azt az erősebb állítást fogjuk belátni, hogy semmilyen $n\geq 2$ egészre nem lehet $f(n)\geq n$ .

Az első fontos észrevétel, hogy $f$ monoton nő, hiszen bármely $n$ -re $f(n+1)-f(n)=f(f(n))\geq0$ , vagyis tényleg $f(n)\leq f(n+1)$ .

Először csak azt látjuk be, hogy semmilyen $n\in\mathbb{N}_0$ -ra nem teljesülhet $f(n)>n$ . Legyen az indirekt feltevés az, hogy mégis van egy olyan $n$ szám, amelyre , vagyis $f(n)\geq n+1$ . Ebből a monotonitás miatt következik, hogy $f(f(n))\geq f(n+1)$ , vagyis $0\geq f(n+1)-f(f(n))$ . Viszont ekkor az alapfeltételt átrendezve kapjuk, hogy

$\displaystyle n<f(n)=f(n+1)-f(f(n))\leq 0,$

ami $n>0$ -ra ellentmondás.

Most már tudjuk, hogy $f(n)\leq n$ , már csak azt kell belátnunk, hogy ha $n>1$ , akkor $f(n)\neq n$ . Indirekt módon tegyük fel, hogy $f(n)=n$ valamely egynél nagyobb $n$ egész számra. Természetesen most is a feltételt fogjuk kihasználni: ha , akkor

$\displaystyle n=f(n)=f(f(n))\leq f(n+1)-f(n) = f(n+1)-n$ .

Ezt átrendezve kapjuk, hogy $2n\leq f(n+1)$ . Ez viszont ellentmondás, hiszen azt már tudjuk, hogy $f(n+1)\leq n+1$ , tehát $2n\leq n+1$ -ből $n\leq1$ következne. Ezzel készen lettünk.

I-4. feladat

Egy $n$ pozitív egészre $\sigma(n)$ jelölje $n$ pozitív osztóinak összegét. Határozd meg az összes egész együtthatós $P$ polinomot, amelyre $P(k)$ osztható $\sigma(k)$ -val minden $k$ pozitív egészre.

Keresztély Zsófia megoldása

A válasz az, hogy az egyedüli ilyen polinom a nullpolinom, vagyis $P(x) \equiv 0$ . A bizonyítás során jelölje $v_p(b)$ a $b$ egész szám prímtényezős felbontásában a $p$ prím kitevőjét. Először belátunk egy lemmát.

Lemma: Tetszőleges $n\geq 0$ -ra létezik $m>0$ , amelyre $3^m\equiv1 \pmod{2^n}$ .

Bizonyítás: Ez az Euler–Fermat-tétel egyenes következménye, hiszen 3 és $2^n$ relatív prímek, vagyis $3^{\varphi\left(2^n\right)}\equiv 1 \pmod{2^n}$ . $\qed$

Legyen $P(x) = \sum_{i=0}^n a_ix^i$ . Indirekt módon tegyük fel, hogy létezik olyan $a_i$ érték, amely nemnulla, legyen a legkisebb ilyen $i$ az $L$ .

A lemma alapján tudjuk, hogy tetszőleges $N$ természetes szám esetén létezik olyan $M$ , amelyre $2^{N(L+1)+1} \mid 3^M-1$ , vagyis $2^{N(L+1)} \mid \frac{3^M-1}{2}$ . Ekkor legyen $K = 2^N \cdot 3^{M-1}$ , amelyre a híres osztóösszegképlet ( $n = \prod_{i=1}^k p_i^{\alpha_i}$ esetén $\sigma (n) = \prod_{i=1}^k \frac{p_i^{\alpha_i+1}-1}{p_i-1}$ ) alapján tudjuk, hogy $\sigma (K) = \left( 2^{N+1}-1 \right) \cdot \frac{3^M-1}{2}$ . Vagyis tudjuk, hogy

$\displaystyle 2^{N(L+1)} \mid \frac12(3^M-1) \mid \sigma (K) \mid P(K).$

Tekintsük $P(K)$ monomjait. Mivel minden $i<L$ -re $a_i = 0$ , így $2^{N(L+1)} \mid a_iK^i$ teljesül minden $i<L$ -re. Továbbá minden $i>L$ -re $2^{N(L+1)} \mid \left(2^{N}\right)^i \mid K^i \mid a_iK^i$ (itt használjuk, hogy a polinom egész együtthatós). Mivel $2^{N(L+1)} \mid P(K)$ , és beláttuk, hogy $2^{N(L+1)}$ osztja $P(K)$ minden $a_LK^L$ -en kívüli monomját, így $2^{N(L+1)} \mid a_LK^L$ . Vagyis $N(L+1) \leq v_2(a_LK^L) = v_2(a_L) + NL$ , tehát $N \leq v_2(a_L)$ , vagyis $2^N \mid a_L$ . Azonban $N$ tetszőleges természetes szám lehet, ami azt jelenti, hogy $a_L$ -nek van tetszőlegesen nagy pozitív osztója. Ebből következik, hogy $a_L$ csak 0 lehet, ami ellentmondáshoz vezet, hiszen $a_L$ a legkisebb indexű nemnulla együttható.

Tehát az indirekt feltevésünk hamis volt, vagyis minden $a_i$ együtthatója 0 a $P$ polinomnak, vagyis $P$ valóban csak a nullpolinom lehet.

T-3. feladat

A Tisza partján 2024 matematikus ül egy sorban. Mindegyikük pontosan egy kutatási témán dolgozik, és ha két matematikus azonos témán dolgozik, akkor az összes közöttük ülő matematikus is ugyanezen a témán dolgozik.

Marvin az összes, két matematikusból álló párra ki szeretné deríteni, hogy azonos témán dolgoznak-e vagy sem. Ehhez bármely matematikustól megkérdezheti az alábbi kérdést: „A 2024 matematikus közül hányan dolgoznak a témádon?” A kérdéseket egyesével teszi fel, így mielőtt feltesz egy kérdést, már tudja az összes előzőre kapott választ.

Határozzátok meg a legkisebb $k$ pozitív egészt, amelyre Marvin mindenképpen teljesíteni tudja a célját legfeljebb $k$ kérdéssel.

Molnár István Ádám megoldása

Először megmutatjuk, hogy 2023 kérdéssel teljesíteni tudja a feladatot. Kérdezze meg az első 2023 matematikust. Az első matematikus válaszából tudni fogja, hogy az első hány matematikus dolgozik ugyanazon a témán. Őket figyelmen kívül hagyva (hiszen más már nem dolgozhat ugyanazon a kutatási témán), megkérdezi az újonnan első matematikust és ezt a folyamatot folytatja. Az utolsó matematikust nem kell megkérdeznie, hiszen, ha már csak ő maradt, akkor ő az egyetlen, aki azon a kutatási témán dolgozik.

A matematikusok viszont meg tudják oldani, hogy Marvinnak legalább 2023-szor kelljen kérdeznie a következő csalfa stratégiával. Hívjuk partnak a már válaszolt matematikusok egybefüggő részhalmazát, amelynek az egyik széle után nincs matematikus, másik széle után egy olyan matematikus van, aki még nem válaszolt. A szigetet definiáljuk hasonlóan, de ennek mindkét széle után egy még nem válaszolt matematikus legyen. Példa:

Válaszok számként, ismeretlenek kérdőjellel. Balról jobbra: egy part (piros), két sziget (sárga, zöld) és egy part (kék).

Hívjuk csoportnak az azonos témán dolgozó matematikusok halmazát. A matematikusok célja, hogy a parthatár csoporthatár legyen, továbbá a szigetek csak 2-esekből álljanak. (Intuitívan a parti válaszok ne adjanak információt a nem parti részekről.)

$\bullet$ Ha a válasz egy szigetet hozna létre, szigetet bővítene vagy két szigetet csatolna össze, a matematikusok 2-vel válaszolnak.

$\bullet$ Ha a válasz partot bővítene vagy hozna létre, a matematikusok 1-gyel válaszolnak, így a part ezen egyes csoporttal végződik.

$\bullet$ Ha a válasz a parthoz egy szigetet kötne, akkor a matematikusok 1-essel válaszolnak, ha a sziget páros sok 2-esből áll, és 2-essel különben. Így a parthoz hozzácsatolt válaszokban egy csoport vagy teljesen benne van, vagy egyáltalán nincs benne.

Ha Marvin legfeljebb 2022 kérdést tenne fel, akkor kell lennie legalább két matematikusnak, aki még nem válaszolt.

$\bullet$ Ha a nem válaszolt matematikusok összefüggőek, akkor nincs sziget. Nem tudhatjuk, hogy minden nem válaszolt matematikus ugyanazon témán dolgozik-e vagy különbözőn (és mivel legalább két matematikus van, ezen esetek különbözők), hiszen a partok erről nem árulnak el információt.

$\bullet$ Különben tekintsük az első és az utolsó matematikust, aki nem válaszolt. Ha az ő általuk meghatározott zárt intervallumban páros sok matematikus van, akkor nem tudjuk megkülönböztetni az eseteket, ahol a csoportok méretek rendre 2, 2, 2, …, 2, 2, illetve 1, 2, 2, …, 2, 1; ha páratlan, akkor az 1, 2, 2, …, 2, 2, és 2, 2, 2, …, 2, 1 eseteket. Ezen két matematikus között csak szigetek lehetnek, ahol minden matematikus 2-vel válaszolt, így ezen esetek lehetségesek.

Ezzel tehát beláttuk, hogy 2023 kérdés biztosan elég Marvinnak, de 2022 kérdés nem elég biztosan.

T-5. feladat

Legyen $ABC$ egy olyan háromszög, amelyben $BAC\sphericalangle = 60^{\circ}$ . Legyen $D$ az $AC$ egyenes egy pontja, amelyre $AB = AD$ és az $A$ pont $C$ és $D$ között fekszik. Tegyük fel, hogy $E \neq F$ két olyan pont a $DBC$ háromszög köréírt körén, amelyekre $AE = AF = BC$ . Bizonyítsátok be, hogy az $EF$ egyenes áthalad az $ABC$ háromszög köréírt körének középpontján.

Kovács Benedek Noel megoldása

Készítsünk ábrát, és használjuk az alábbi jelölésrendszert!

Mivel $DAB\sphericalangle=180^{\circ}-BAC\sphericalangle=120^{\circ}$ , így az $ABD$ egyenlő szárú háromszögben $ABD\sphericalangle=ADB\sphericalangle=\frac{180^{\circ}-DAB\sphericalangle}{2}=30^{\circ}$ lesz. A középponti és kerületi szögek tételéből következik, hogy a $BCD$ háromszög köréírt körének $N$ középpontjára $BNC\sphericalangle=2\cdot BDC\sphericalangle=60^{\circ}$ teljesül.

Innen látható, hogy mivel $BNC\sphericalangle=BAC\sphericalangle=60^{\circ}$ , így a kerületi szögek tételének megfordításából következik, hogy $N$ az $ABC$ háromszög körülírt körén helyezkedik el.

Azt is tudjuk, hogy mivel $BN=CN$ , így $NBC\sphericalangle=NCB\sphericalangle=\frac{180^{\circ}-BNC\sphericalangle}{2}=60^{\circ}$ lesz, azaz az $NBC$ háromszög szabályos, amelynek eredményeképpen $BC=BN=CN$ lesz.

Mivel $E$ és $F$ pontok is rajta vannak az $N$ középpontú körön ( $BCD$ háromszög köréírt körén), így $EN=NF=BC$ lesz. Ezen kívül a feladat szövege alapján $AE = AF = BC$ . Ebből az következik, hogy $AE=AF=EN=EF$ , tehát $AENF$ egy rombusz lesz. Ennek alapján látható, hogy az $EF$ egyenes az $AN$ szakasz felezőmerőlegese lesz.

Azonban ismert, ahogy az $A$ és $N$ pontok egyaránt rajta vannak az $ABC$ háromszög $O$ középpontú köréírt körén, úgy az $O$ pont rajta lesz az $AN$ szakasz felezőmerőlegesén.

Mindezekből az következik, hogy az $E$ , $F$ , $O$ pontok kollineárisak lesznek, vagyis az $EF$ egyenes valóban áthalad az $ABC$ háromszög köréírt körének $O$ középpontján.

T-6. feladat

Legyen $ABC$ egy hegyesszögű háromszög. Legyen a $BC$ szakasz felezőpontja $M$ . Legyen $I$ , $J$ , $K$ rendre az $ABC$ , $ABM$ , $ACM$ háromszögek beírt körének középpontja. Legyenek $P$ , $Q$ rendre az $MK$ , $MJ$ egyeneseken olyan pontok, hogy $AJP\sphericalangle=ABC\sphericalangle$ és $AKQ\sphericalangle =BCA\sphericalangle$ . Legyen a $CP$ és $BQ$ egyenesek metszéspontja $R$ . Bizonyítsátok be, hogy az $IR$ és $BC$ egyenesek merőlegesek egymásra.

Vigh Zalán megoldása

Ha megmutatjuk, hogy $BI \perp CP$ , akkor hasonlóan $CI \perp BQ$ , így azt kapjuk, hogy $I$ a $BCR\triangle$ magasságpontja, így $RI \perp BC$ . Tehát a célunk, hogy belássuk, $BI \perp CP$ .

$I$ , $J$ és $K$ mindegyike $A$ -ból, $C$ -ből, $B$ -ből és $M$ -ből induló szögfelezők metszete, így kapjuk, hogy $MJ \perp MK$ . Megnézve az $AJM$ háromszög belső szögeit, kapjuk, hogy $AJM\sphericalangle = 90^\circ + \frac{ABC\sphericalangle}{2}$ . Mivel $AJP\sphericalangle=ABC\sphericalangle$ , így $PJM\sphericalangle = 90^\circ - \frac{ABC\sphericalangle}{2}$ . Továbbá megnézve a $JMP$ háromszög szögeit, kapjuk, hogy $JPM\sphericalangle = \frac{ABC\sphericalangle}{2}$ .

Legyen $J'$ a $J$ pont tükörképe $M$ -re!

Ekkor a tükrözés miatt $BJC\triangle \cong CJ'B\triangle$ , valamint $JMP\triangle \cong J'MP\triangle$ , így azt kapjuk, hogy $J'CM\sphericalangle = JBM\sphericalangle = \frac{ABC\sphericalangle}{2} = JPM\sphericalangle = J'PM\sphericalangle$ .

Így $P$ és $C$ ugyanakkora szögben lát rá a $J'M$ szakaszra, tehát $J'MPC$ egy húrnégyszög. A kerületi szögek tétele alapján $MCP\sphericalangle = MJ'P\sphericalangle = MJP\sphericalangle = 90^\circ - \frac{ABC\sphericalangle}{2}$ . Legyen $BI$ metszete $CP$ -vel $X$ . Ekkor megnézve $BXC\triangle$ szögeit, kapjuk, hogy $BXC\sphericalangle = 90^\circ$ , tehát $BI \perp CP$ .

T-7. feladat

Nevezzük pozitív egészek összeragasztásának a tízes számrendszerbeli alakjuk egymás után írását, majd a kapott eredmény leolvasását egyetlen, tízes számrendszerben írt pozitív egészként.

Adjátok meg az összes olyan pozitív egész $k$ számot, amelyre létezik $N_k$ egész az alábbi tulajdonsággal: minden $n\geq N_k$ -ra az 1, 2, …, $n$ számok összeragaszthatók valamilyen sorrendben úgy, hogy az eredmény osztható legyen $k$ -val.

Megjegyzés. A tízes számrendszerbeli alakja egy pozitív egésznek sosem kezdődik 0-val.

Példa. A 15, 14, 7 számok ilyen sorrendbeli összeragasztása 15147.

Holló Martin megoldása

Megmutatjuk, hogy pontosan a 3-mal nem osztható számok rendelkeznek ezzel a tulajdonsággal.

Először megmutatjuk, hogy a 3-mal osztható $k$ -k nem rendelkeznek ezzel a tulajdonsággal, ehhez elég megmutatni, hogy a 3 nem rendelkezik ezzel a tulajdonsággal. Hiszen $k=3$ esetén az oszthatóság csak a számok számjegyeinek összegétől függ, de minden $N_3$ szám esetén van nála nagyobb $n$ , ami 10-hatvány, ami 1-gyel változtatja az addigi számok számjegyösszegét. Így akkor az oszthatóság biztosan megváltozik, tehát vagy addig nem teljesült, vagy mostantól nem fog. Így ezt beláttuk.

Most megmutatjuk, hogy a 3-mal nem osztható számokra teljesül az állítás.

Ekkor $k$ -t írjuk fel $k'\cdot 2^m\cdot 5^{\ell}$ alakban, ahol $k'$ egész és nem osztható sem 2-vel, sem 5-tel. Világos, hogy ezt mindig megtehetjük.

Az lesz a stratégia, hogy egy bizonyos $N_k$ szám esetén elérjük, hogy az első $N_k$ számot össze tudjuk ragasztani tetszőleges $k'$ -vel vett maradékot adó számmá úgy, hogy az utolsónak ragasztott szám egy olyan nagy 10-hatvány legyen, ami többszöröse $2^m\cdot 5^{\ell}$ -nek.

Belátjuk, hogy ez a stratégia valóban működik. Vegyük az $N_k$ -nál nagyobb számok egy tetszőleges összeragasztását, és írjunk a szám végére annyi 0-t, amennyi számjegyből az első $N_k$ szám összesen áll. Nézzük meg az így kapott szám maradékát $k'$ -vel osztva. Ekkor ha a szám után odaragasztjuk azt az első $N_k$ számból álló számot, ahol a maradék ennek az ellentettje, akkor egy $k'$ -vel osztható számot kapunk, ami a nagy 10-hatvánnyal való végződés miatt $2^m\cdot 5^{\ell}$ -lel is osztható lesz. Így a relatív prímség miatt a szám osztható lesz $k$ -val is.

Most térjünk rá a konstrukcióra: először kezdjük azzal, hogy az elég nagy 10-hatványt a szám végére rakjuk. Ezek után úgy fogjuk elé ragasztani a számokat, hogy az tartalmazzon $k'$ db különböző párt, ahol a pár két olyan egymás mellé ragasztott $A$ és $B$ számot jelöl, amelyekre $A$ és $B$ felcserélése 1-gyel növeli a szám $k'$ -vel való maradékát. Ekkor $k'$ ilyen pár esetén összesen $k'$ helyen tudjuk egyesével növelni a maradékot, így tetszőleges értéket elérve. Most kezdjük el a szám végétől indulva egyesével létrehozni ezeket a párokat.

Induktívan tegyük fel, hogy már létrehoztunk valamennyi ilyen párt; most megmutatjuk, hogy tudunk csinálni még egyet. Ha eddig $i$ számjegyből áll a szám, akkor ha $N_k$ elég nagy, akkor biztos van még nem felhasznált számunk úgy, hogy annak a számnak a számjegyeinek száma tetszőleges maradékot adjon $\varphi(k')$ -vel osztva. Ezt megfelelően választva elérhető, hogy a szám elé írva a jelenlegi szám számjegyeinek száma $\varphi(k')$ -vel osztható legyen. Így ezt a számot írjuk is a szám elé. Illetve ha $N_k$ elég nagy, akkor biztos van még $k'$ egymást követő fel nem használt szám, amelyek számjegyeinek száma mind azonos, és $\varphi(k')$ -vel osztva 1-et ad maradékul. Ekkor a $k'$ szám közül legyen $B$ az, amelyik osztható $k'$ -vel, és legyen $A$ az, aminek a $k'$ -s maradéka a 9 inverze. (Ilyen $A$ van, hisz a 9 és $k'$ relatív prímek, ahogy $k$ nem osztható 3-mal.)

Ekkor ha a jelenlegi szám elejére írjuk $A$ -t, majd utána az elé $B$ -t, akkor egy jó párt kapunk, hiszen ha $A$ -nak $j$ számjegye van, és utána még $c$ számjegy van, akkor a két szám megcserélésével a maradék változása

$\displaystyle A\cdot 10^c\cdot 10^j+B\cdot 10^c-(A\cdot 10^c+B\cdot 10^c \cdot 10^j)$ .

De mivel $B$ osztható $k'$ -vel, a $B$ -s tagokat elhagyhatjuk, így a változás

$\displaystyle A\cdot 10^c\cdot (10^j-1)$ .

De mivel $c$ a $\varphi(k')$ többszöröse és a $k'$ és 10 relatív prímek, így az Euler–Fermat-tétel miatt a $10^c$ szám 1 maradékot ad $k'$ -vel osztva, így azzal leoszthatunk, és a változás $A\cdot (10^j-1)$ lesz. De mivel $10^{j-1}$ maradéka 1 az Euler–Fermat-tétel miatt, így $10^j$ maradéka 10, tehát $10^j-1$ maradéka $k'$ -vel osztva 9. Ekkor $A\cdot (10^j-1)$ az 1-et ad maradékul, tehát csináltunk egy párt, aminek felcserélése 1-gyel növeli a maradékot. Ez az algoritmus folytatható a következő pár létrehozásánál is, amivel kész lettünk. A megmaradó számokat pedig a szám elejére ragasztjuk.