 |
Az A. 704. feladat (2017. október) |
A. 704. Egy \(\displaystyle n\) hosszú oldalakkal rendelkező szabályos háromszög oldalainak \(\displaystyle n\)-edelőpontjain át behúztuk az oldalakkal párhuzamos egyenesek háromszögbe eső szakaszait. Tekintsük az így létrejövő \(\displaystyle 1+2+\ldots+(n+1)\) darab metszéspont alkotta pontrácsot. Melyek azok az \(\displaystyle n\) pozitív egészek, melyekre ez a pontrács olyan ponthármasokba partícionálható, melyek egy-egy egységnyi oldalú szabályos háromszög csúcsai?
Javasolta: Alexander Gunning (Cambridge, Egyesült Királyság)
(5 pont)
A beküldési határidő 2017. november 10-én LEJÁRT.
Válasz. Pontosan akkor létezik konstrukció, ha \(\displaystyle n\equiv -1,1,8,10\pmod{12}\).
1. megoldás (Alexander Gunning megoldása). Nyilvánvaló konstrukció létezik \(\displaystyle n=-1\) és \(\displaystyle n=1\) esetén. (Az \(\displaystyle n=-1\) eset, vagyis egy üres rács, szintén megfelel indukciós alapesetnek.) Továbbá, mint az ábráról leolvasható,
\(\displaystyle \bullet\) ha \(\displaystyle n\equiv -1\pmod{3}\), a konstrukció \(\displaystyle n\)-re kiegészíthető egy \(\displaystyle n+2\)-re vonatkozó konstrukcióra,
\(\displaystyle \bullet\) ha \(\displaystyle n\equiv 0\pmod{2}\), az \(\displaystyle n\)-es konstrukció egy \(\displaystyle n+3\)-asra egészíthető ki,
\(\displaystyle \bullet\) ha \(\displaystyle n\equiv 1\pmod{2}\), az \(\displaystyle n\)-es konstrukció egy \(\displaystyle n+9\)-esre egészíthető ki.
Tehát rekurzív módon minden \(\displaystyle n=12k-1\), \(\displaystyle n=12k+1\), \(\displaystyle n=12k+8\), illetve \(\displaystyle n=12k+10\) alakú \(\displaystyle n\)-re adható konstrukció (\(\displaystyle k\ge 0\)).
Más \(\displaystyle n\) értékekre azonban nem létezik a kívánt partíció. Először is, mivel \(\displaystyle 3\) osztója \(\displaystyle 1+2+\dots+(n+1)=\frac{(n+1)(n+2)}{2}\)-nek, kiszínezhetjük a rácsot a piros, kék, zöld színek segítségével úgy, hogy egységnyi távol rácspontok eltérő színt kapjanak, és mindhárom szín éppen \(\displaystyle \frac{(n+1)(n+2)}{6}\)-szor forduljon elő. (Nevezetesen, a rácspontjaink baricentrikus koordinátái \(\displaystyle (x:y:z)\) alakúak, ahol \(\displaystyle x,y,z\) nemnegatív egészek és \(\displaystyle x+y+z=n\), és az \(\displaystyle (x:y:z)\) ponthoz az \(\displaystyle y+2z\) színt rendelhetjük.)
A partíció struktúrájáról további információt nyerhetünk ki, ha csak a piros és kék pontokat és az őket összekötő olyan egységszakaszokat figyeljük, melyek nem oldalai semely partícióbeli háromszögnek sem.
Megsejthető, hogy ezek a szakaszok mindig utak egy halmazát alkotják. Amennyiben igen, ezeket az utakat egymás után fűzhetjük, ha a rácsot minden oldalon egy-egy pontsorral bővítjük. Ezért inkább vizsgáljuk az alábbi bővítést:
Lemma. Tekintsük azt a \(\displaystyle G\) gráfot, melynek csúcsai a kibővített pontrács piros és kék csúcsai, valamint élei az azokat összekötő olyan egységszakaszok, melyek egyik háromszögnek sem élei. Ekkor
(a) ez a gráf egy út, és
(b) az út \(\displaystyle n=3k-1\) esetén \(\displaystyle 4x\), míg \(\displaystyle n=3k+1\) esetén \(\displaystyle 4x+2\) csúcsból áll, ahol \(\displaystyle x\) egész.
Bizonyítás. (a) \(\displaystyle G\)-nek két darab \(\displaystyle 1\) fokú csúcsa van, nevezetesen a kibővített háromszög kék csúcsa ill. piros csúcsa, \(\displaystyle v_k\) ill. \(\displaystyle v_p\). Minden más csúcs foka \(\displaystyle 2\). Minden ilyen tulajdonságú gráf felbontható egy útnak és néhány körnek diszjunkt uniójára. Jelen esetben az út mindenképp \(\displaystyle v_k\)-t és \(\displaystyle v_p\)-t köti össze: elég tehát belátni, hogy \(\displaystyle G\)-ben nincsen kör.
Indirekt módon feltéve, hogy van \(\displaystyle G\)-ben kör, tekintsük azt az \(\displaystyle \mathcal{S}\) síkidomot, amit a kör határol. (Igényes matematikusok kedvéért: itt használtuk a Jordan-tételt, legalábbis annak speciális esetét.) Ekkor \(\displaystyle \mathcal{S}\) azon egységoldalú szabályos hatszögeknek az uniója, melyeknek egy \(\displaystyle \mathcal{S}\)-beli zöld pont a középpontja (ezentúl: hatszögek). Mivel minden ilyen zöld pont valamely partícióbeli háromszögnek csúcsa, így az \(\displaystyle \mathcal{S}\)-be eső háromszögek száma egyezik az \(\displaystyle \mathcal{S}\)-et alkotó hatszögek számával.
Most induljunk ki egy \(\displaystyle \mathcal{S}\)-et alkotó hatszögből. A benne lévő zöld ponthoz tartozó háromszög piros-kék oldala mentén ez egy további hatszögnek szomszédja. Az új hatszögből a zöld középpontjához tartozó háromszög piros-kék oldala mentén egy még újabb hatszögbe léphetünk, és így tovább. Véges sok hatszög miatt ezzel az eljárással idővel egy ciklusba fogunk lépni. Ha összekötjük a ciklus szomszédos zöld csúcsait, a kapott sokszög belseje zöld csúcsú \(\displaystyle \sqrt 3\) oldalú háromszögek uniója, melyek közül bármelyik zöld háromszög valamely élszomszédja is a sokszög belsejében van. Ezért van a sokszög belsejében \(\displaystyle G\)-nek éle, s így egy \(\displaystyle G\)-beli ciklus is, ami kisebb területe ölel körül.
Ez ellentmondáshoz vezet, ha olyan \(\displaystyle G\)-beli körből indulunk ki, melyhez minimális területű \(\displaystyle \mathcal{S}\) tartozik.
(b) Induljunk ki az alábbi \(\displaystyle v_k\) és \(\displaystyle v_p\)-t összekötő útból (ami nincs feltétlenül \(\displaystyle G\)-ben), melynek \(\displaystyle n=3k-1\)-re \(\displaystyle 4k\), \(\displaystyle n=3k+1\)-re \(\displaystyle 4k+2\) a hossza.
Amíg a teljes \(\displaystyle G\) utat meg nem kapjuk, az utat alkotó élek közül mindig kicserélhetünk egyet, mely valamely partícióbeli háromszög éle, \(\displaystyle 5\) további élre úgy, hogy "átléptetünk az úton egy hatszöget". , addig, amíg a teljes \(\displaystyle G\) utat meg nem kapjuk. Valóban, egy eljárás közben adódó út \(\displaystyle v_k\)-t és \(\displaystyle v_p\)-t köti össze, így az (a) rész miatt valamely partícióbeli háromszög piros-kék oldalát tartalmazza, ha még \(\displaystyle G\)-t nem értük el. Ennek a háromszögnek a zöld csúcsa olyan hatszögnek a középpontja, melyet még nem "léptettünk át", így az eljárás folytatható. Mivel lépésenként \(\displaystyle 4\)-gyel növelve az út hosszát, \(\displaystyle G\)-hez jutunk, így a Lemma (b) részét is igazoltuk. \(\displaystyle \blacksquare\)
Mivel azonban \(\displaystyle G\)-nek éppen \(\displaystyle \frac23\cdot \frac{(n+4)(n+5)}{2}\) csúcsa van, és \(\displaystyle \frac{m(m+1)}{2}\) páros, ha \(\displaystyle m\equiv -1,0\pmod 4\) ill. páratlan, ha \(\displaystyle m\equiv 2,3\pmod 4\), ezért
\(\displaystyle \bullet\) \(\displaystyle n=3k-1\) esetén \(\displaystyle n\equiv -1,0\pmod 4\), vagyis \(\displaystyle n\equiv -1,8\pmod{12}\),
\(\displaystyle \bullet\) \(\displaystyle n=3k+1\) esetén \(\displaystyle n\equiv 1,2\pmod 4\), vagyis \(\displaystyle n\equiv 1,10\pmod{12}\).
Ezzel teljes a bizonyítás.
2. megoldás (Schrettner Jakab megoldása, Conway és Lagarias nyomán): letölthető pdf, tex forrás.
Statisztika:
15 dolgozat érkezett. 5 pontot kapott: Schrettner Jakab. 2 pontot kapott: 3 versenyző. 1 pontot kapott: 4 versenyző. 0 pontot kapott: 7 versenyző.
A KöMaL 2017. októberi matematika feladatai