Konstrukciók és bizonyítások

Számos ilyen halmaz létezik. Egy lehetséges konstrukció a következő halmaz: {6, 19, 30}.

Ellenőrzés:

• \( 6 + 19 = 25 = 5^2 \)
• \( 6 + 30 = 36 = 6^2 \)
• \( 19 + 30 = 49 = 7^2 \)

Hogyan találhatunk ilyet? Legyen a három szám \(a, b, c\). Célunk, hogy \(a+b=x^2\), \(a+c=y^2\), és \(b+c=z^2\). Ekkor a három szám összege \(a+b+c = \frac{x^2+y^2+z^2}{2}\). Ebből visszaszámolhatók az \(a, b, c\) értékek: \(c = (a+b+c) - x^2\), stb. Választva egymást követő pitagoraszi jellegű értékeket (pl. 5, 6, 7), gyorsan eljutunk a megoldásig.

Ha egy gráfban minden csúcs fokszáma pontosan 2, akkor az egy (vagy több) körgráf.

Mivel 5 csúcsunk van, a legegyszerűbb és egyetlen összefüggő megoldás egy 5 hosszúságú körgráf (\(C_5\)) rajzolása. Ez megtehető úgy, hogy egy szabályos ötszög csúcsait összekötjük az oldalain mentén.

A gráf csúcsai legyenek: \(v_1, v_2, v_3, v_4, v_5\). Az élek pedig: \(\{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_4\}, \{v_4,v_5\}, \{v_5,v_1\}\). Itt jól láthatóan minden csúcsból 2 él indul ki.

Igen, létezik. (Ezt nevezzük Lo Shu négyzetnek).

A számok elrendezése a következő lehet:

Miért a középső az 5? A bűvös állandó 15. A középső elemet (legyen \(x\)) a rajta áthaladó 4 vonal (1 sor, 1 oszlop, 2 átló) is tartalmazza. Ezen négy vonal összege \(4 \cdot 15 = 60\). Ezen vonalak tartalmazzák mind a 9 számot egyszer (összegük 45), plusz a középsőt még 3-szor többletként. Tehát \(45 + 3x = 60 \Rightarrow 3x = 15 \Rightarrow x = 5\).

Egy lehetséges megoldás: {1, 1, 2, 6, 10}.

Nézzük meg a statisztikai mutatókat:

• Módusz: A leggyakoribb elem az 1.
• Medián: A sorba rendezett adatok középső eleme (a 3. elem) a 2.
• Átlag: A számok összege osztva a darabszámmal: \(\frac{1+1+2+6+10}{5} = \frac{20}{5} = \) 4.

A három mutató (1, 2, 4) páronként különböző érték, a konstrukció sikeres.

Használjuk a Viète-formulákat, amelyek szerint az \(x^2 + px + q = 0\) egyenlet gyökei esetén felírható, hogy az összegük \(-p\), a szorzatuk pedig \(q\).

• Gyökök összege: \(x_1 + x_2 = (2+\sqrt{3}) + (2-\sqrt{3}) = 4\). Ebből kapjuk, hogy \(-p = 4 \Rightarrow p = -4\).
• Gyökök szorzata: \(x_1 \cdot x_2 = (2+\sqrt{3})(2-\sqrt{3}) = 2^2 - (\sqrt{3})^2 = 4 - 3 = 1\). Ebből kapjuk, hogy \(q = 1\).

Az egyenlet tehát: \(x^2 - 4x + 1 = 0\).

A válasz: Nem lehetséges.

Ezt egy egyszerű színezéses bizonyítással láthatjuk be. A hagyományos 8x8-as sakktábla 32 fehér és 32 fekete mezőből áll.

Két átlósan szemközti sarokmező színe mindig azonos (például mindkettő fehér). Ha ezt a kettőt levágjuk, a táblán 30 fehér és 32 fekete mező marad.

Egy \(2 \times 1\)-es dominó bárhogyan is helyezkedik el a táblán, mindig pontosan 1 fehér és 1 fekete mezőt takar le. Így ahhoz, hogy a dominókkal le tudjuk fedni a területet, ugyanannyi fehér és fekete mezőre lenne szükség. Mivel ez nem teljesül (30 nem egyenlő 32-vel), a lefedés lehetetlen.

A válasz: Nem.

A probléma arra kérdez rá, hogy tartalmaz-e a gráf Euler-vonalat. Euler tétele szerint egy összefüggő gráf pontosan akkor rajzolható meg a ceruza felemelése nélkül, ha a páratlan fokszámú csúcsainak száma pontosan 0 vagy 2.

A feladatban szereplő gráfban (ami lényegében egy tetraéder éleinek hálózata) 4 darab csúcs van, és mind a 4 csúcs fokszáma 3 (ami páratlan szám). Mivel a páratlan fokszámú csúcsok száma 4, ami több mint 2, a gráfot lehetetlen egyetlen vonallal megrajzolni.

A válasz: Nem léteznek. Ezt egy maradékosztályos (moduláris) vizsgálattal bizonyítjuk.

Rendezzük át az egyenletet: \(x^2 = 4y + 2\).

A jobb oldal alapján az egyenlet azt állítja, hogy az \(x^2\) négyzetszám 4-gyel osztva 2 maradékot ad. Vizsgáljuk meg egy egész szám négyzetének lehetséges 4-es maradékait:

• Ha az \(x\) páros, azaz \(x = 2k\), akkor \(x^2 = 4k^2\), ami 4-gyel maradék nélkül osztható (maradéka 0).
• Ha az \(x\) páratlan, azaz \(x = 2k+1\), akkor \(x^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4(k^2+k) + 1\), aminek a 4-gyes maradéka mindig 1.

Láthatjuk, hogy egy egész szám négyzete 4-gyel osztva sosem adhat 2-es maradékot. Így az egyenletnek nincs megoldása az egész számok halmazán.

A válasz: Nem létezik.

Egy \(n\) oldalú konvex sokszög átlóinak számát a következő képlettel számolhatjuk ki: \(\frac{n(n-3)}{2}\).

A feladat kérdése alapján írjuk fel az egyenletet: \(\frac{n(n-3)}{2} = 100\).

Felszorozva és átrendezve: \(n^2 - 3n - 200 = 0\).

Nézzük meg a másodfokú egyenlet diszkriminánsát: \(D = (-3)^2 - 4 \cdot 1 \cdot (-200) = 9 + 800 = 809\).

Mivel a \(809\) nem négyzetszám, a megoldóképletből származó \(n\) érték nem lesz racionális (sőt, nyilván nem lesz egész sem). Mivel a csúcsok száma (\(n\)) csak pozitív egész szám lehet, megállapíthatjuk, hogy ilyen sokszög nem létezik.

A válasz: Nem lehetséges.

Ez a klasszikus "három ház – három kút" probléma a gráfelméletben. A gráf, amit meg akarunk rajzolni, a \(K_{3,3}\) teljes páros gráf.

A kérdés valójában arra irányul, hogy a \(K_{3,3}\) síkgráf-e (megrajzolható-e metszéspontok nélkül). A Kuratowski-tétel kimondja, hogy egy gráf pontosan akkor síkba rajzolható, ha nem tartalmazza részgráfként (vagy topologikusan) a \(K_5\) (teljes 5 csúcsú) vagy a \(K_{3,3}\) gráfokat.

Mivel a mi gráfunk maga a \(K_{3,3}\), bebizonyosodott, hogy lehetetlen síkban metszéspont nélkül megrajzolni.

A válasz: 2 szín elegendő.

Bármilyen, síkban kizárólag végtelen egyenesek (vagy kört metsző hurkolatlan szakaszok) által létrehozott térkép 2-színezhető. Ezt teljes indukcióval is bizonyíthatjuk az egyenesek számára (\(n\)) vonatkozóan.

Bizonyítás lépései (ötlet): Vegyünk egy már színezett ábrát \(n\) egyenessel. Ha behúzunk egy új, \(n+1\)-edik egyenest, az az ábrát két félsíkra osztja. Hagyjuk az egyik félsíkban a színeket változatlanul, a másik félsíkban pedig cseréljük fel (invertáljuk) az összes színt (pl. fehéret feketére, feketét fehérre). Az új egyenes mentén találkozó tartományok így biztosan ellenkező színűek lesznek, míg a régi határvonalak érvényessége (ahol a két szomszéd eddig is eltérő volt) mindkét félsíkon megmarad.

A válasz: Nem lefedhető. (Bár a 100 mező osztható 4-gyel, színezéssel belátható a lehetetlenség).

Színezzük a tábla sorait 4 különböző színnel (pl. 1, 2, 3, 4 számokkal jelölve) ciklikusan ismétlődve: a sorok színe sorban 1, 2, 3, 4, 1, 2, 3, 4, 1, 2.

Ekkor a táblán az 1-es és 2-es színű mezőkből \(3 \times 10 = 30\) darab van, míg a 3-as és 4-es színűből csak \(2 \times 10 = 20\) darab.

Ha leteszünk egy \(1 \times 4\)-es dominót, az vagy vízszintesen helyezkedik el (ekkor csak egyféle színt fed le, méghozzá 4 mezőt, de a 4 szín számának maradéka 4-gyel osztva nem változik), vagy függőlegesen helyezkedik el (ekkor pontosan mind a 4 színből egyet-egyet takar le).

Látható, hogy az 1-es és 3-as színű lefedetlen mezők számának különbsége függőleges letételkor nem változik, vízszintes letételkor 4-gyel változik (tehát mod 4 invariáns). Kezdetben a különbség \(30-20 = 10\), ami nem osztható 4-gyel. Így nem fogyhat el minden mező egyszerre, a lefedés lehetetlen.

A válasz: Nem lehetséges.

Tekintsük a \(3 \times 3 \times 3\)-as kockát térbeli sakktáblának, és színezzük a kiskockákat feketére és fehérre úgy, hogy az élekben érintkező szomszédok mindig eltérő színűek legyenek. Legyenek a sarokkockák (8 db) feketék.

Ebben az esetben, mivel összesen 27 kocka van, a fekete kockák száma 14, a fehér kockáké 13. A nagy kocka kellős közepén lévő kocka paritása a sarkokétól eltér, így az biztosan fehér.

Ha a középső fehér kockát kivesszük, az egérnek \(14\) fekete és \(13-1 = 12\) fehér kockát kell bejárnia (összesen 26 lépésben).

Mivel az egér lépésenként váltakozva lép fehérről feketére és feketéről fehérre, egy 26 hosszú út pontosan 13 fehér és 13 fekete kockát tartalmazna. Minthogy a rágandó sajtban 14 fekete és 12 fehér kocka van, a bejárás lehetetlen.

A válasz: 3 szín.

Kezdjük el színezni a körgráf csúcsait sorban. Próbáljuk meg 2 színnel (pl. Kék és Piros) kiszínezni.

1. csúcs: Kék. (Mivel szomszédos a 2-essel, annak másnak kell lennie).
2. csúcs: Piros.
3. csúcs: Kék.
4. csúcs: Piros.
5. csúcs: Kék.

Elérkeztünk az 5. csúcshoz, amelynek kéknek kellene lennie, hogy a 4. csúcstól különbözzön. Viszont az 5. csúcs össze van kötve az 1. csúccsal is (ami Kék). Így azonos színűek lennének, ami a gráfszínezési szabályok szerint tilos.

Mivel minden páratlan hosszúságú kör (\(C_{2k+1}\)) esetében ugyanez az anomália fellép az utolsó és az első csúcsnál, páratlan körök nem színezhetők 2 színnel. Szükségünk van egy 3. színre (pl. Zöld) az 5. csúcshoz. Tehát a kromatikus szám 3.

Végezzük el a szokásos sakktábla színezést! A \(6 \times 6\)-os táblán 18 fehér és 18 fekete mező van.

Bármely kivágott \(2 \times 2\)-es blokk pontosan 2 fehér és 2 fekete mezőt tartalmaz. Ha két ilyen blokkot vágunk ki, összesen 4 fehér és 4 fekete mezőt távolítunk el.

A maradék alakzatban tehát \(18 - 4 = 14\) fehér és \(18 - 4 = 14\) fekete mező marad. Mivel a fekete és fehér mezők száma egyenlő, a klasszikus színezéses lehetetlenségi bizonyítás itt nem állja meg a helyét.

Ha mélyebben megvizsgáljuk az alakzatot (pl. próbálkozással vagy a Hall-féle házassági tétellel), bebizonyítható, hogy a lefedés ebben a konkrét esetben lehetséges. (Ez egy "csapda" feladat, amely megmutatja, hogy a színezés elsősorban arra jó, hogy a lehetetlenséget bizonyítsuk. Ha az egyenlőség fennáll, abból még nem feltétlenül következik a lefedhetőség, de itt történetesen igen).

Keressünk egy invariáns (változatlan) mennyiséget!

Amikor két szám (\(a\) és \(b\)) helyett felírjuk az \(a+b-1\)-et, a táblán lévő számok összege pont 1-gyel csökken (\(a+b\) helyett \(a+b-1\) lesz). A számok darabszáma szintén pont 1-gyel csökken minden egyes lépésben.

Ez azt jelenti, hogy az (Összeg - Darabszám) értéke invariáns, a lépések során nem változik.

Kezdetben a darabszám 100. Az összeg: \(\frac{100 \cdot 101}{2} = 5050\). Az invariáns érték tehát: \(5050 - 100 = 4950\).

Amikor a folyamat véget ér, 1 darab szám marad a táblán (nevezzük \(X\)-nek). Ekkor az (Összeg - Darabszám) érték: \(X - 1\).

Mivel ez az érték állandó, \(X - 1 = 4950\), amiből következik, hogy a táblán maradó szám 4951.

A válasz: Nem lehetséges.

Jelöljük a színek számát \(P, Z, K\) betűkkel! Vizsgáljuk meg a színek darabszámainak páronkénti különbségét maradékosztályokkal, modulo 3!

Ha egy piros és egy zöld találkozik, kék lesz belőlük. A változás: \(P_{új} = P-1\), \(Z_{új} = Z-1\), \(K_{új} = K+2\).
Vizsgáljuk a különbségeket:
\(P_{új} - Z_{új} = (P-1) - (Z-1) = P - Z\)
A \(P\) és \(Z\) különbsége (és bármely másik kettőé) ha 3-mal osztjuk, ugyanazt a maradékot adja minden lépés után! Tehát a különbségek mod 3 invariánsak.

Kezdetben: \(K - Z = 17 - 15 = 2\), \(Z - P = 15 - 13 = 2\). Egyik sem osztható 3-mal.

Ha egy ponton minden kaméleon azonos színű lenne (mondjuk mind a 45 kék), akkor \(Z=0\) és \(P=0\) lenne. Ebben a célállapotban a különbségük \(Z - P = 0 - 0 = 0\) lenne, ami osztható 3-mal (\(0 \equiv 0 \pmod 3\)).

Mivel az elején a különbség nem volt osztható 3-mal, a célállapot sosem érhető el.

A válasz: Nem lehetséges.

Legyenek a körön lévő számok sorrendben: \(a_1, a_2, a_3, a_4, a_5, a_6\). Képezzük az úgynevezett váltakozó összeget (alternáló összeget):
\(S = a_1 - a_2 + a_3 - a_4 + a_5 - a_6\).

Ha két szomszédos számot – például \(a_i\)-t és \(a_{i+1}\)-et – egyaránt megnövelünk 1-gyel, akkor a váltakozó összegben az egyik \(+1\)-et, a másik \(-1\)-et kap (mert a képletben felváltva vannak a jelek). Így az \(S\) értéke egyáltalán nem változik, vagyis invariáns.

A kezdeti állapotban az invariáns értéke:
\(S_{kezdeti} = 1 - 0 + 1 - 0 + 0 - 0 = 2\).

Ha sikerülne elérni, hogy mind a hat szám egyenlő legyen (legyen ez az érték \(x\)), akkor a váltakozó összeg:
\(S_{cél} = x - x + x - x + x - x = 0\).

Mivel a kezdeti érték (2) nem egyenlő a célállapot értékével (0), az állapot nem érhető el.

A válasz: Nem.

Vizsgáljuk meg az "írással felfelé" lévő érmék számának változását! Ha 2 érmét fordítunk meg, az alábbi három eset fordulhat elő:

• Két írást fordítunk fejre: az írások száma csökken 2-vel.
• Két fejet fordítunk írásra: az írások száma nő 2-vel.
• Egy fejet és egy írást fordítunk meg (az írásból fej lesz, a fejből írás): az írások száma nem változik.

Mint látható, az írásos érmék száma minden lépésben egy páros számmal (+2, -2 vagy 0) változik. Ez azt jelenti, hogy az írások számának paritása (páros/páratlan mivolta) invariáns.

Kezdetben 10 írás van, ami páros szám. A célállapotban 1 írást szeretnénk, ami páratlan szám. Mivel a paritás sosem változhat, a célállapot elérhetetlen.

A válasz: Nem, a sárkány legyőzhetetlen.

Nézzük meg, hogyan változik a sárkány fejeinek a száma az egyes suhintások után (a levágott fejek csökkentik, a visszanövők növelik a számot):

• 1. típus: \(-15 + 24 = +9\) fej.
• 2. típus: \(-17 + 2 = -15\) fej.
• 3. típus: \(-20 + 14 = -6\) fej.
• 4. típus: \(-5 + 17 = +12\) fej.

Mi a közös a fenti számokban (9, -15, -6, 12)? Mindegyik osztható 3-mal! Ebből következik, hogy a sárkány fejeinek száma csak 3 többszörösével tud megváltozni. Tehát a fejek számának 3-mal való osztási maradéka invariáns.

Kezdetben a sárkánynak 100 feje van. \(100 = 33 \cdot 3 + 1\), azaz a maradék 1.

A cél a 0 fej elérése. Mivel a 0 maradék nélkül osztható 3-mal, a célállapot osztási maradéka 0. A maradék nem változhat meg 1-ről 0-ra, így sosem lehet 0 fej a sárkányon.