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