Feladat: Gy.2919 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Burcsi Péter ,  Elek Péter ,  Koblinger Egmont ,  Torma Péter ,  Tóth Gábor Zsolt 
Füzet: 1994/december, 493 - 494. oldal  PDF  |  MathML 
Témakör(ök): Másodfokú (és arra visszavezethető) egyenletek, Gráfok összefüggősége, Fagráfok, erdők, faváz, Gyakorlat
Hivatkozás(ok):Feladatok: 1994/május: Gy.2919

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Legyen az eredeti négyzet n×n-es. Ekkor n2 ,,egységnégyzetből'' áll. Kössük össze képzeletben mindegyik kis négyzet középpontját az élszomszédaiéval. Összesen n(n-1) vízszintes és ugyanennyi függőleges irányú összeköttetést létesítettünk ezáltal (feltéve, hogy a papíron a négyzetek oldala vízszintes, illetve függőleges). Gábor minden egyes vonal behúzásakor ezek egyikét megszakítja, természetesen mindig másikat. A kezdeti 2n(n-1) összeköttetésből tehát 2n(n-1)-400 marad.
Ha elképzelünk egy gráfot, amelynek csúcsai a kis négyzetek középpontjai, élei pedig a megmaradt összeköttetések, akkor ennek a gráfnak n2 csúcsa és 2n(n-1)-400 éle van. Ugyanakkor tudjuk róla, hogy bármelyik csúcsából bármelyik másikba el lehet jutni, azaz összefüggő; ám csak egyféleképpen lehet eljutni, vagyis körmentes (ha volna benne kör, akkor annak két csúcsát kiválasztva, köztük többféle út is lenne). Tehát a gráfunk úgynevezett fa-gráf (erről részletesebben például Andrásfai Béla: Ismerkedés a gráfelmélettel c. könyvében lehet olvasni), s így igaz rá, hogy eggyel több csúcsa van, mint éle; azaz

n2=2n(n-1)-400+1.

Ennek az egyenletnek két gyöke van: -19 és 21. Mivel negatív oldalhosszúságnak nincs értelme, az elsőnek megrajzolt négyzet oldala 21 egység.
Koblinger Egmont (Budapest, Fazekas M. Főv. Gyak. Gimn., III. o. t.) dolgozata alapján