A B. 5448. feladat (2025. március)

B. 5448. Van két egybevágó, szabályos \(\displaystyle n\)-szög alapú gúlánk. Mindkét gúla oldallapjaira felírjuk véletlenszerű sorrendben az \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle \ldots\), \(\displaystyle n\) számokat. Milyen \(\displaystyle n\)-ek esetén lehetünk biztosak benne, hogy a két gúlát össze tudjuk úgy ragasztani az alaplapjuk mentén, hogy a kapott \(\displaystyle 2n\)-lapú kettős gúla legalább két élére teljesül, hogy mindkét oldalán ugyanaz a szám áll?

Javasolta: Lovas Márton (Budakalász)

(4 pont)

A beküldési határidő 2025. április 10-én LEJÁRT.

Megoldás. Mivel gúlákról van szó \(\displaystyle n \geq 3\). Legyenek Piroska gúlájának oldallapjain a számok (valamely körüljárásnak megfelelő sorrendben, egy tetszőlegesen kiválasztott oldallaptól kezdve) \(\displaystyle a_0, a_1, ... ,a_{n-1}\), míg Farkasén a megfelelő számok \(\displaystyle b_0, b_1, ..., b_{n-1}\) úgy, hogy az \(\displaystyle n\) lehetséges összeragasztás egyikénél minden \(\displaystyle i\)-re az \(\displaystyle a_i\) és a \(\displaystyle b_i\) számokat tartalmazó oldalapoknak legyen közös éle. (Ha Piroska és Farkas \(\displaystyle a_i\), illetve \(\displaystyle b_i\) számsorozatait a saját gúlájuk alaplapja felől nézzük, akkor természetesen az egyik sorozat pozitív, a másik negatív körüljárási irány szerint van felsorolva, de ez a leírásunk során semmiféle gondot nem fog okozni.)

Fixáljuk le Piroska gúláját, ekkor Farkas gúlája \(\displaystyle n\)-féle (a feladat szempontjából) lényegesen különböző ,,állapotba'' forgatva ragasztható hozzá. A \(\displaystyle k\)-dik állapotban (ahol \(\displaystyle 0 \leq k \leq n-1\)) Piroska \(\displaystyle a_i\) számával Farkas \(\displaystyle b_{i+k}\) számának van közös éle. (Itt az \(\displaystyle i+k\) indexet \(\displaystyle \pmod{n}\) értjük – ezért indexeltünk Piroska és Farkas sorozatait eleve \(\displaystyle 0\) és \(\displaystyle n-1\) között).

Farkas gúlájának \(\displaystyle k\)-dik állapotát tekintsünk ,,jónak'', ha (legalább) két különböző \(\displaystyle 0 \leq i,j \leq n-1\) index esetén teljesül \(\displaystyle a_i = b_{i+k}\) és \(\displaystyle a_j = b_{j+k}\).

Definiáljuk a \(\displaystyle c_0, c_1, ...,c_{n-1}\) számokat a következő módon: adott \(\displaystyle 0 \leq i,k \leq n-1\) esetén nevezzük az \(\displaystyle (a_i;b_{i+k})\) párt fixpontnak, ha \(\displaystyle a_i=b_{i+k}\), és ebben az esetben legyen \(\displaystyle c_i=k\), vagyis \(\displaystyle c_i=k\) azt jelenti, hogy a \(\displaystyle k\)-dik állapotban Piroska \(\displaystyle a_i\) száma ,,fölé'' (azaz vele közös élű oldallapra) a vele megegyező szám került Farkas gúláján.

Miközben Farkas gúláját az \(\displaystyle n\) különböző állapotba forgatjuk, Piroska bármelyik \(\displaystyle a_i\) száma fölött nyilvánvalóan pontosan egy állapotban fordul elő olyan \(\displaystyle b_{i+k}\) szám, amely megegyezik vele, vagyis bármely \(\displaystyle i\) indexre a \(\displaystyle c_i\) szám egyértelműen definiált, továbbá az \(\displaystyle n\) állapot esetén összesen \(\displaystyle n\) darab fixpont lesz.

Nyilván akkor jó számunkra egy állapot, ha abban legalább két fixpont van. Emiatt a skatulyaelv alapján, ha az \(\displaystyle n\) lehetséges állapot bármelyike olyan, hogy benne nincs fixpont, akkor kell lennie a többi állapot esetén jó állapotnak is; illetve pontosan akkor nincs a lehetséges állapotok között jó, ha bármely állapotban pontosan egy darab fixpont van.

Az eddigiek alapján ahhoz, hogy a lehetséges állapotok egyike se legyen jó (vagyis, hogy különböző fixpontok mind különböző állapotokhoz tartozzanak) az kell, hogy a \(\displaystyle c_i\) számok mind különbözzenek egymástól, vagyis az, hogy \(\displaystyle c_0 - 0; c_1 - 1;... ;c_{n-1} -(n-1)\) számok teljes maradékrendszert képezzenek \(\displaystyle \pmod{n}\).

Tegyük fel, hogy \(\displaystyle n=2k\) alakú páros szám. Ekkor bármely teljes maradékrendszer esetén a benne lévő számok \(\displaystyle S\) összegére: \(\displaystyle S \equiv 0+1+...+(n-1) = \dfrac{n(n-1)}{2} = \dfrac{2k(2k-1)}{2} =2k^2-k \equiv -k \equiv k \not\equiv 0 \pmod{n}\), holott nyilván \(\displaystyle (c_0 -0)+ (c_1-1)+...+(c_{n-1} -(n-1)) = (c_0+c_1+...+c_{n-1})-(0 + 1+2+...+(n-1))=0 \equiv 0 \pmod{n}\). Azaz ha \(\displaystyle n\) páros, akkor mindig forgatható Farkas gúlája úgy, hogy legalább két fixpont legyen.

Ha viszont \(\displaystyle n=2k+1\) alakú páratlan szám, akkor ha Piroska \(\displaystyle a_i\) számai a \(\displaystyle 0,1,2,3,...,2k-1,2k\) számok, Farkas \(\displaystyle b_i\) számai pedig a \(\displaystyle 0,2,4,6,...,2k,1,3,5,...,2k-3,2k-1\) számok, akkor a megfelelő \(\displaystyle c_i\) számok könnyen ellenőrizhetően \(\displaystyle 0,1,2,3,...,k,k+1,k+2,k+3,...,2k\), azaz ekkor a lehetséges állapotok mindegyikében pontosan egy fixpont van, vagyis a két gúla nem ragasztható jól össze.

Válasz: összefoglalva ha \(\displaystyle n\) páros, akkor a két gúla mindig összeragasztható a feladat feltételeinek megfelelően, míg ha \(\displaystyle n\) páratlan, akkor mindig meg tudják címkézni Piroska és Farkas a saját gúlájuk oldallapjait úgy, hogy ne lehessen a két gúlát jól összeragasztani.

Statisztika:

46 dolgozat érkezett.
4 pontot kapott:	Ali Richárd, Aravin Peter, Balla Ignác , Bencze Mátyás, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Gyenes Károly, Hajszter Dóra, Hideg János, Hodossy Réka, Holló Martin, Nagy 707 Botond, Pázmándi József Áron, Péter Hanna, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Sárdinecz Dóra, Szabó 721 Sámuel, Vályi Nagy Ádám András, Varga 511 Vivien, Wiener Marcell, Zhai Yu Fan.
3 pontot kapott:	Görömbey Tamás, Kun Zsófia, Li Mingdao, Sha Jingyuan, Sun Wen Ze, Török Eszter Júlia, Vámosi Bendegúz Péter.
2 pontot kapott:	10 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2025. márciusi matematika feladatai