Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

4. A feladatok megoldása

4. A feladatok megoldása

3. Megmutatjuk, hogy a tsz. rész- ( k + 1 ) -szög k ? 4 -re tartalmazza a kör középpontját. Ez azzal ekvivalens, hogy nincs a szabályos ( k 2 + k + 1 ) -szögnek olyan szimmetriatengelye, melynek egyik oldalán nincs csúcsa ( k + 1 ) -szögünknek. Azt, hogy k = 2 és 3 esetén még van, a fejezetben megadott és lényegében egyértelmű két példán könnyű ellenőrizni. Tegyük fel, hogy k ? 4 és K olyan tsz. rész- ( k + 1 ) -szög, mely nem tartalmazza a kör középpontját. Mivel K -nak tartalmaznia kell két olyan csúcsot, melyek távolsága a lehető legnagyobb, elforgatás és tükrözés után feltehető, hogy K csúcsai 1 = x 1 //<// x 2 //<// //<// x k + 1 = k 2 + k + 2 2 (vegyük észre, hogy k 2 + k + 1 minden k -ra páratlan). Keressük meg azon két K -beli csúcsot, melyek távolsága k 2 + k 2 - 1 . Könnyen ellenőrizhető, hogy ez csak 1 és k 2 + k 2 vagy 2 és k 2 + k + 2 2 lehet. Tükrözés, elforgatás és átindexelés után feltehető, hogy x 2 = 2 . Most keressük azon két csúcsot, melyek távolsága k 2 + k 2 - 2 . Erre már három lehetőségünk van: 1 és k 2 + k 2 - 1 , 2 és k 2 + k 2 vagy 3 és k 2 + k 2 + 1 . Csakhogy ahhoz, hogy ne szerepeljen a K -beli csúcsok közt kétszer ugyanaz a távolság, ez csak úgy lehet, ha x k = k 2 + k 2 - 1 . Ezzel automatikusan van két olyan csúcsunk is, melyek távolsága k 2 + k 2 - 3 : a 2 és a k 2 + k 2 - 1 . Végül vegyük észre, hogy a k 2 + k 2 - 4 távolság már reménytelen: elvben ez lehetne 1 és k 2 + k 2 - 3 , 2 és k 2 + k 2 - 2 , 3 és k 2 + k 2 - 1 , 4 és k 2 + k 2 vagy 5 és k 2 + k 2 + 1 között. Ezek azonban mind olyan új csúcsot jelentenének, amelynek hozzávételével K -ban fellépne kétszer ugyanaz a távolság. A gondolatmenet működéséhez persze kell, hogy k 2 + k 2 - 4 több legyen, mint a már megtalált „kicsi” távolságok, azaz k 2 + k 2 - 4 //>// 2 . Ez éppen k ? 4 -től teljesül.

5. Két esetet különböztetünk meg aszerint, hogy van-e olyan oszlop, melyben minden mező egyszínű. Ha van ilyen, akkor a maradék 6 oszlopban már csak egyszer-egyszer fordulhat elő a kérdéses szín, különben találnánk egyszínű téglalapot. Ilyen színezés viszont csak 4 féle lehet, tehát van két teljesen egyforma oszlop. Ha nincs egyszínű oszlop, akkor összesen 6 féle oszlopszínezés lehetséges, így megint kell legyen két egyforma oszlop.

6. Először megmutatjuk, hogy m = n 2 esetén a maximum n ( n - 1 ) , ez a kiválasztott rácspontok száma abban az esetben, ha minden oszlopban pontosan két rácspontot választunk. Tegyük fel, hogy találtunk egy jobb elrendezést. Az összes ilyenből vegyük azt, amelyben a lehető legtöbb pontosan két kiválasztott rácspontot tartalmazó oszlop van. Indirekt tegyük fel, hogy nem minden oszlop ilyen, könnyű végiggondolni, hogy ekkor lesz több mint kettő kiválasztott rácspontot tartalmazó oszlop is, mondjuk az i ., és pontosan egyet tartalmazó is, mondjuk a j . oszlop. Ha most a j . oszlop rácspontját áttesszük ugyanebben az oszlopban egy olyan sorba, ahol az i . oszlopban is volt elem, másrészt az i . oszlop egy másik sorbeli elemét áttesszük a j . oszlopba (ugyanebben a sorban), akkor szintén helyes kiválasztást kapunk ugyanennyi rácsponttal, de több pontosan két kiválasztott rácspontot tartalmazó oszloppal, ellentmondás. Ha most m = n 2 + s , akkor könnyű végiggondolni, hogy legfeljebb n 2 olyan oszlop lehet amelyben legalább két rácspont van kiválasztva, így egy maximális rácspontot tartalmazó kiválasztásnál legalább s oszlopban pontosan egy rácspontot választunk ki. s ilyen oszlopot törölve megismételhető az előzőgondolatmenet.

8. Jelölje R a tsz. részsokszöget, R ' pedig ennek elforgatottját. A forgatás szöge legyen s 360 ° / ( k 2 + k + 1 ) . Mivel R -nek van két olyan pontja, mondjuk x és y , amelyek távolsága a körön mérve s , ezek valamelyike közös pontja lesz R -nek és R ' -nek. Két metszéspont viszont nem lehet, hiszen az két olyan pontpárt adna R -ben, amelyek távolsága azonos.

9. A 10. feladatban kapott képletbe n = k 2 + k -t és m = k 2 -et helyettesítve éppen ( k + 1 ) k 2 -et kapunk.

10. Jelölje d i az i . sorban kiválasztott rácspontok számát ( i = 1 , , n ). Ekkor pontosan ? i d i 2 egy sorban lévő kiválasztott rácspontpár van, másrészt ez a szám legfeljebb m 2 , hiszen bármely két oszlophoz legfeljebb egy olyan sor lehet, mely ezen két pozíciójában van kiválasztott rácspont. Így a

? d i 2 - ? d i ? m ( m - 1 )

egyenlőtlenséghez jutunk. Másrészt a számtani és négyzetes közepek közti egyenlőtlenség miatt ? d i 2 ? ( ? d i ) 2 / n , így az E = ? i d i jelöléssel az

E 2 / n - E ? m ( m - 1 )

egyenlőtlenséget kapjuk, ahonnan

E ? 1 2 n + n 2 + 4 n m ( m - 1 ) .

Milyen feltételei vannak az egyenlőségnek? A számtani és négyzetes közepek összehasonlítása miatt egyenlőség esetén a d i -k mind egyenlők, azaz minden sorban ugyanannyi kiválasztott rácspont van. ? d i 2 = m 2 -höz pedig az kell, hogy bármely két oszlophoz pontosan egy olyan sor legyen, hogy ebben a sorban mindkét oszlopban kiválasztott rácspont van.

11.a) A (Z)24-et ad a kiválasztható rácspontok számára. Induljunk ki a 7 × 7 -es megoldásából (4. ábra), ebben már 21 kiválasztott rácspont szerepel. Válasszuk ki a nyolcadik sorból az első és a nyolcadik rácspontot! Ekkor a nyolcadik oszlopban például a negyedik sorban még kijelölhetünk rácspontot, amivel elérjük a 24-es felső becslést.

11.b) Ekkor a felsőbecslés 16, amelyet elérhetünk a 4. ábrából a felső sor és a bal szélső oszlop törlésével.

13. Bontsuk a bizonyítást az alábbi részállítások igazolására:

I. Projektívsíkon két egyenes nem tartalmazhatja az összes pontot.

II. Legyen P olyan pont, amely nincs rajta az l egyenesen. Mutassuk meg, hogy a P -n átmenő egyenesek száma megegyezik l pontjainak számával. (Ehhez adjunk kölcsönösen egyértelmű megfeleltetést a P -n átmenő egyenesek és l pontjai között.)

III. Ha van k + 1 pontú egyenes, akkor minden egyenesen k + 1 pont van, és minden ponton k + 1 egyenes megy át.

IV. Mind a pontok, mind az egyenesek száma k 2 + k + 1 .

A részállítások bizonyítása:

I. Indirekt tegyük fel, hogy az l és m egyenesek tartalmazzák a sík összes pontját és legyen P illetve Q a metszésponttól különböző pont l -en illetve m -en. A P és Q által meghatározott egyenesnek van még legalább egy pontja, ez azonban nincs rajta sem l -en, sem m -en, ellentmondás.

II. Egy P -n átmenő egyenesnek feleltessük meg az (egyértelműen létező) metszéspontját l -lel. Ekkor P1 miatt l minden pontja pontosan egy P -n átmenő egyeneshez fogtartozni.

III. Legyen l k + 1 pontú, m pedig tetszőleges egyenes. Az I. rész szerint találhatunk olyan P pontot, mely nincs rajta sem l -en, sem m -en. A II. részből pedig az következik, hogy m pontjainak száma megegyezik a P -n átmenő egyenesek számával, mely megint a II. rész szerint egyenlő l pontjainak számával. Mivel m tetszőleges volt, ezzel beláttuk, hogy az egyenesek mérete k + 1 . Mivel találtunk olyan pontot, melyen k + 1 egyenes megy, most ugyanezt a gondolatmenetet elismételve a pontok és egyenesek szerepét felcserélve kapjuk, hogy minden ponton ugyanennyi egyenesnek kell mennie.

IV. Legyen P tetszőleges pont. A P -n átmenő egyenesek egyrétűen lefedik a P -től különböző pontokat (P1 miatt), így(használva az előző két feladatot) a pontok száma 1 + ( k + 1 ) k = k 2 + k + 1 . Az egyenesek számát úgy kaphatjuk meg, hogy ugyanezt a számolást megismételjük a pontok és egyenesek szerepének felcserélésével.

14. P 1 - P 4 ? P 5 : legyenek l és l ' metsző egyenesek, A 1 , A 2 illetve A 1 ' , A 2 ' pedig ezeknek a metszéspontoktól különböző két-két pontja (ezek P3 miatt léteznek). Az A 1 , A 2 , A 1 ' , A 2 ' pontok közül semelyik három nincs egy egyenesen, azaz teljesül P5.

P 1 , P 2 , P 5 ? P 3 , P 4 : P5 szerint legalább 6olyan l egyenes van, amelynek legalább három pontja van (nevezetesen a négyszög bármely pontpárját összekötő egyenes). Ha volna két pontú egyenes is, mondjuk l ' , akkor l és l ' együtt a sík összes pontját le kell fedje, különben a 13. feladatmegoldásának II. részében látott módon l -et rávetíthetnénk l ' -re. Ez viszont lehetetlen, hiszen l -nek hat egyenes bármelyikét választhatjuk. Ez igazolja P3-at. P4 igazolása teljesen hasonló.

15. Az axiómákat kell ellenőriznünk, ezt itt csak vázoljuk. P1: ha a két pont egyike a középpont, másika csúcs vagy oldalfelező pont, akkor a kívánt egyenes a megfelelő magasságvonal. Két csúcs esetén a megfelelő oldal, két felezőpont esetén a beírt kör az összekötő egyenes. Egy csúcs és egy felezőpont esetén a magasságvonal vagy az oldal az összekötő egyenes aszerint, hogy a felezőpont szemköztes-e a csúccsal. P2 teljesülése nyilvánvaló. P3 és P4 pedig azért teljesül, mert minden egyenesen pontosan három pont van, minden ponton pontosan három egyenes megy át.

16. Azt láthatjuk be,hogy a sorok és oszlopok alkalmas permutációjával tetszőleges projektív sík illeszkedési mátrixa a 4. ábrán látható alakra hozható (ahol · helyett 1, különben 0 áll). Valóban, az első sorbeli illetve oszlopbeli egyeseket a bal felső sarokba tömöríthetjük sorok és oszlopok felcserélésével. Ezután elérhetjük, hogy a 2-3. sorok és oszlopok a 4. ábrán látható módon helyezkedjenek el. Ezután már csak a táblázat jobb alsó 4 × 4 -es részének kitöltése maradt. Nem nehéz látni, hogy a sorok és oszlopok felcserélésével elérhetjük, hogy ezekben az egyesek a 4. ábra szerint helyezkedjenek el.