A B. 4882. feladat (2017. május)

B. 4882. Legfeljebb hány lapja lehet egy olyan konvex poliédernek, amelynek kiválasztható három lapja úgy, hogy a poliéder minden éle illeszkedik a kiválasztott lapok valamelyikére?

(5 pont)

A beküldési határidő 2017. június 12-én LEJÁRT.

I. megoldás. Legyenek a kiválasztott lapok \(\displaystyle F_1, F_2, F_3\). Tekintsünk egy tetszőleges nem kiválasztott \(\displaystyle F\) lapot. \(\displaystyle F\)-nek \(\displaystyle F_1, F_2, F_3\) mindegyikével legfeljebb egy közös éle van, ezért \(\displaystyle F\) szükségképpen háromszög, és \(\displaystyle F_1, F_2, F_3\) mindegyikével pontosan egy közös éle van.

Rögzítsünk egy nem kiválasztott \(\displaystyle F_0\) lapot, aminek csúcsai \(\displaystyle A, B\) és \(\displaystyle C\), legyen \(\displaystyle A=F_0\cap F_1 \cap F_3\), \(\displaystyle B=F_0\cap F_1\cap F_2\), \(\displaystyle C=F_0\cap F_2\cap F_3\).

I.eset Ha \(\displaystyle F_1\cap F_2\), \(\displaystyle F_2\cap F_3\) és \(\displaystyle F_3 \cap F_1\) mindegyike közös él. Ekkor ezek \(\displaystyle A\)-tól, \(\displaystyle B\)-től és \(\displaystyle C\)-től különböző végpontjaik rendre legyenek \(\displaystyle A'\), \(\displaystyle B'\) és \(\displaystyle C'\).

Először vizsgáljuk azt a lehetőséget, amikor \(\displaystyle A'\), \(\displaystyle B'\) és \(\displaystyle C'\) páronként különbözőek. Tegyük fel, hogy ekkor (például) \(\displaystyle A'B'\) nem éle \(\displaystyle P\)-nek. Ekkor létezik \(\displaystyle F_1\)-nek egy \(\displaystyle X\) csúcsa, amely sem \(\displaystyle F_2\)-nek, sem \(\displaystyle F_3\)-nak nem csúcsa. De ekkor egy \(\displaystyle X\)-re illeszkedő nem kiválasztott háromszöglapnak nem lehet egyszerre \(\displaystyle F_2\)-vel és \(\displaystyle F_3\)-mal is közös éle, ami ellentmond a kezdeti megállapításunknak. Így \(\displaystyle A'B'\), s hasonlóan \(\displaystyle A'C'\) és \(\displaystyle B'C'\) is éle \(\displaystyle P\)-nek, s ekkor szükségképpen \(\displaystyle A', B'\) és \(\displaystyle C'\) egy további háromszöglapot határoznak meg. \(\displaystyle P\) ekkor egy 5 lapú test, amelynek élgráfja megegyezik egy háromszög alapú hasáb élgráfjával.

Most tegyük fel, hogy (mondjuk) \(\displaystyle A'=B'\). Ekkor \(\displaystyle F_1\) háromszöglap, amelynek három szomszédja \(\displaystyle F_0, F_2\) és \(\displaystyle F_3\). A kezdeti megállapításunk miatt \(\displaystyle P\)-nek további lapja már nem lehet (mert az szomszédos kellene legyen \(\displaystyle F_1\)-gyel), így ekkor \(\displaystyle A'\), \(\displaystyle B'\) és \(\displaystyle C'\) egybeesnek, és \(\displaystyle P\) tetraéder.

II. eset Valamely két kiválasztott lapnak nincs közös éle, (mondjuk) \(\displaystyle F_1\cap F_3=A\). Ekkor \(\displaystyle A\)-ra illeszkedik egy \(\displaystyle F_4=ADE\triangle\) háromszöglap, és \(\displaystyle F_1\cap F_4\) az \(\displaystyle AD\) él, \(\displaystyle F_3\cap F_4\) pedig \(\displaystyle AE\) él. A fentiek miatt \(\displaystyle DE\) él illeszkedik \(\displaystyle F_2\)-re, így \(\displaystyle B\) és \(\displaystyle D\) is \(\displaystyle F_1\) és \(\displaystyle F_2\) lapok közös csúcsai, vagyis \(\displaystyle F_1\cap F_2=BD\), és hasonlóan \(\displaystyle F_2\cap F_3=EC\), és a test egy négyszög alapú gúla.

Más lehetőség nincs, tehát egy a kívánalmaknak megfelelő poliédernek legfeljebb \(\displaystyle 5\) lapja van.

II. megoldás (vázlat) Ahogy az első megoldásban, megállapítjuk, hogy minden nem kiválasztott \(\displaystyle F\) lap szükségképpen háromszög, és a kiválasztott \(\displaystyle F_1, F_2, F_3\) lapok mindegyikével pontosan egy közös éle van.

Tegyük fel, hogy \(\displaystyle L_1\), \(\displaystyle L_2\), \(\displaystyle L_3\) különböző nem kiválasztott lapok. Tekintsük \(\displaystyle P\) poliéder \(\displaystyle G\) élgráfját. Ismert, hogy \(\displaystyle G\) egyszerű síkgráf. Legyen \(\displaystyle G'\) a \(\displaystyle G\) duálisa, ami szintén egyszerű síkgráf. A \(\displaystyle G'\)-ben \(\displaystyle F_1, F_2, F_3\) valamint \(\displaystyle L_1, L_2,L_3\) lapoknak egy-egy csúcs felel meg. Valamint az \(\displaystyle F_i\) és \(\displaystyle L_j\) lapok közös élei a \(\displaystyle G'\)-ben a megfelelő csúcsokat összekötő élek lesznek. Ebből, és a kiindulási megállapításunkból következik, hogy \(\displaystyle G'\) részgráfként tartalmaz egy három ház, három kút gráfot, így nem lehet síkgráf. Ellentmondásra jutottunk, így \(\displaystyle P\)-nek legfeljebb \(\displaystyle 5\) lapja lehet. Ez elő is fordulhat, pl. megfelelő, ha egy háromszög alapú hasáb oldallapjait választjuk ki.

Statisztika:

36 dolgozat érkezett.
5 pontot kapott:	Baran Zsuzsanna, Beke Csongor, Borbényi Márton, Busa 423 Máté, Csahók Tímea, Csiszár Zoltán, Daróczi Sándor, Döbröntei Dávid Bence, Füredi Erik Benjámin, Gáspár Attila, Győrffy Ágoston, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Kocsis Júlia, Lakatos Ádám, Marshall Tamás, Nagy Nándor, Szabó 417 Dávid, Szakály Marcell, Tiderenczl Dániel, Tóth 827 Balázs, Tóth Viktor, Weisz Máté, Zólomy Kristóf.
4 pontot kapott:	Kővári Péter Viktor, Németh 123 Balázs, Saár Patrik, Szabó Kristóf.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	4 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2017. májusi matematika feladatai