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:

A B. 5448. feladat értékelése még nem fejeződött be.

A KöMaL 2025. márciusi matematika feladatai