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

12. A feladatok megoldásai

12. A feladatok megoldásai

1. feladat. Tekintsünk egy tetszőleges futamot (jele A ), és egy motorost ( b 1 ), aki nem vett részt ebben a futamban. Alkalmazzuk a 2. szabályt A -ra és b 1 -re. Eszerint van egy olyan futam, amely tartalmazza b 1 -et, de A egyik tagját sem. Legyen ennek a futamnak a jele B , tagjai pedig legyenek b 1 , b 2 , , b k . Legyen továbbá egy sem A -ban, sem B -ben nem szereplő versenyző c 1 . A 2. szabály szerint van egy olyan futam, amely tartalmazza c 1 -et, de A egyik tagját sem. Legyen ez C = { c 1 , c 2 , , c k } . Ha lenne közös versenyző B -ben és C -ben, akkor az két A -t „elkerülő” futamban is szerepelne, tudniillik B -ben és C -ben. Ez ellentmondana, a 2. szabálynak. Tehát az A , B és C futamok közül semelyik kettőben sincs közös versenyző. Így haladhatunk tovább, míg k olyan futamot nem találunk, amelyek összesen minden versenyzőt tartalmaznak, de mindegyik versenyzőt csak az egyik futam tartalmazza. Ez a k futam lesz az egyik teljes forduló. Egy teljes forduló tehát egy tetszőleges futamból és az összes azzal közös versenyzőt nem tartalmazó futamból áll.

Így bármelyik futamból kiindulva fölépíthetünk egy teljes ( k futamból álló) fordulót. Különböző teljes fordulókban nem lehet közös futam, hiszen bármelyik futam egyértelműen megadja az őt tartalmazó teljes fordulót. Ez azt jelenti, hogy az összes futam teljes furdulókba csoportosítható.

2. feladat. Tekintsünk ismét egy tetszőleges A futamot, és egy b 1 motorost, aki nem vett részt A -ban. Legyenek az A -ban szereplő motorosok a 1 , a 2 , , a k . Az 1. szabály szerint van pontosan egy olyan futam, amelyben b 1 és a 1 együtt szerepel; van továbbá pontosan egy olyan, amelyben b 1 és a 2 együtt szerepel…és így tovább, végül van pontosan egy olyan, amelyben b 1 és a k együtt szerepel. Ez a k futam egymástól különböző, hiszen a 1 és a j közös futama csak az A futam lehet. Mármost azt könnyű belátni, hogy b 1 összesen ( k + 1 ) futamban vesz részt: minden futamban k - 1 ellenfelével találkozik, összesen k 2 - 1 ellenfele van, és az 1. szabály szerint minden ellenfelével pontosan egy futamban találkozik, vagyis az őt szerepeltető futamok száma ( k 2 - 1 ) / ( k - 1 ) = k + 1 . Tehát b 1 -nek van egy és csak egy olyan futama, amely az A futamban nem szereplő versenyzőkből áll. Ez tetszőleges A futamra és azon kívüli b 1 versenyzőre igaz, tehát teljesül a 2. szabály.

3. feladat. Tekintsünk egy tetszőleges P pontot, és tegyük fel, hogy az őt tartalmazó egyenesek száma k + 1 . Ha egy l egyenes nem tartalmazza P -t, akkor A2 szerint a k + 1 darab P -n átmenő egyenes közül pontosan egy párhuzamos l -lel. Tehát k ilyen egyenes metszi l -t, és A1 miatt mindegyikük különböző pontban; másrészt ugyancsak A1 miatt l mindegyik pontja rajta van a k egyenes valamelyikén. Tehát ha l nem tartalmazza P -t, akkor pontosan k pontja van.

Most tegyük fel, hogy l tartalmazza P -t. A3 miatt van olyan pont, ami nincs l -en; legyen Q egy ilyen pont. Ha belátjuk, hogy Q -n keresztül is pontosan k + 1 egyenes megy át, akkor az előbbiek szerint következik, hogy l -nek k pontja van. Mármost P -n pontosan k olyan egyenes megy át, ami nem tartalmazza Q -t. Legyenek ezek l 1 , l 2 , , l k . Minden 1 ? i ? k -ra legyen l i ' az az A2 szerint létező és egyetlen egyenes, amely átmegy Q -n és párhuzamos l i -vel. Ezek mind különbözők, mert ha l i ' = l j ' valamely i ? j -re, akkor l i és l j egyaránt P -n átmenő és l i ' -vel párhuzamos egyenes lenne, ami ellentmondana A2-nek. Továbbá ez az összes, Q -n átmenő és P -t nem tartalmazó egyenes, mert ha volna rajtuk kívül is ilyen, akkor ehhez nem találnánk vele nem párhuzamos, P -n átmenő egyenest. Tehát Q -n k egyenes megy át az őt P -vel összekötő egyenesen kívül, azaz összesen k + 1 egyenes megy át rajta. Mint már láttuk, ezek szerint l -nek k pontja van.

Hátra van még, hogy a sík összes pontjainak száma éppen k 2 . Tekintsük ismét p -t és a rajta átmenő k + 1 darab egyenest. Mint láttuk, mindegyikükön k pont van, vagyis P -n kívül k - 1 . A1 szerint ez a ( k + 1 ) ( k - 1 ) = k 2 - 1 pont mind különböző, és ismét A1 miatt rajtuk és P -n kívül nem is lehet más pont. Ezzel a bizonyítást befejeztük.

4. feladat. Ha egy testben 0 = 1 , akkor bármely a elemére a = a · 1 = a · 0 = a · 0 + a · a + ( - ( a · a ) ) = a · ( 0 + a ) + ( - ( a · a ) ) = a · a + ( - ( a · a ) ) = 0 .

5. feladat. Igen. Ugyanis az n tagból álló a + a + + a összeg megegyezik a és az n tagból álló 1 + 1 + + 1 összeg szorzatával. Miután a ? 0 , a nullosztómentesség miatt ez a szorzat pontosan akkor 0, ha az 1-esekből álló összeg 0.

6. feladat. F 3 -ban 0 2 = 0 , 1 2 = 1 és 2 2 = 1 , tehát semmilyen x -re sem teljesül, hogy x 2 = 2 = - 1 , azaz hogy x 2 + 1 = 0 .

A négyelemű testről mondottakhoz hasonlóan látható, illetve kiszámolható, hogy ha F 3 -at az x 2 + 1 = 0 polinom egy gyökével bővítjük (jelöljük ezt a gyököt a -val), akkor egy kilencelemű testet kapunk, az alábbi összeadó-, illetve szorzótáblával:

+ 0 1 2 a a + 1 a + 2 2 a 2 a + 1 2 a + 2 0 0 1 2 a a + 1 a + 2 2 a 2 a + 1 2 a + 2 1 1 2 0 a + 1 a + 2 a 2 a + 1 2 a + 2 2 a 2 2 0 1 a + 2 a a + 1 2 a + 2 2 a 2 a + 1 a a a + 1 a + 2 2 a 2 a + 1 2 a + 2 0 1 2 a + 1 a + 1 a + 2 a 2 a + 1 2 a + 2 2 a 1 2 0 a + 2 a + 2 a a + 1 2 a + 2 2 a 2 a + 1 2 0 1 2 a 2 a 2 a + 1 2 a + 2 0 1 2 a a + 1 a + 2 2 a + 1 2 a + 1 2 a + 2 2 a 1 2 0 a + 1 a + 2 a 2 a + 2 2 a + 2 2 a 2 a + 1 2 0 1 a + 2 a a + 1

0 1 2 a a + 1 a + 2 2 a 2 a + 1 2 a + 2 0 0 0 0 0 0 0 0 0 0 1 0 1 2 a a + 1 a + 2 2 a 2 a + 1 2 a + 2 2 0 2 1 2 a 2 a + 2 2 a + 1 a a + 2 a + 1 a 0 a 2 a 2 a + 2 2 a + 2 1 a + 1 2 a + 1 a + 1 0 a + 1 2 a + 2 a + 2 2 a 1 2 a + 1 2 a a + 2 0 a + 2 2 a + 1 2 a + 2 1 a a + 1 2 a 2 2 a 0 2 a a 1 2 a + 1 a + 1 2 2 a + 2 a + 2 2 a + 1 0 2 a + 1 a + 2 a + 1 2 2 a 2 a + 2 a 1 2 a + 2 0 2 a + 2 a + 1 2 a + 1 a 2 a + 2 1 2 a

7. feladat. 2 × 2 -es görög-latin négyzet nem létezik. A többi esetre alább látható egy-egy megoldás:

d ? c ß b ? a ? c ? d ? a ß b ? b ß a ? d ? c ? a ? b ? c ? d ß , e ? d ? c ? b ? a ß d ? c ß b ? a ? e ? c ? b ? a ? e ß d ? b ß a ? e ? d ? c ? a ? e ? d ß c ? b ? .

8. feladat. Mindegyik konkrét esetben ( k - 1 ) latin négyzet adható meg. Alább példát adunk erre a k = 4 és k = 5 esetekben. A következő feladatból kiderül, hogy miért nem lehet több.

4 3 2 1 3 4 1 2 2 1 4 3 1 2 3 4 4 2 1 3 3 1 2 4 2 4 3 1 1 3 4 2 4 1 3 2 3 2 4 1 2 3 1 4 1 4 2 3

5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 1 2 3 4 5 5 2 4 1 3 4 1 3 5 2 3 5 2 4 1 2 4 1 3 5 1 3 5 2 4 5 3 1 4 2 4 2 5 3 1 3 1 4 2 5 2 5 3 1 4 1 4 2 5 3 5 4 3 2 1 4 3 2 1 5 3 2 1 5 4 2 1 5 4 3 1 5 4 3 2

9. feladat. Ha egy latin négyzetben minden 1-est 2-esre, és ugyanakkor minden 2-est 1-esre cserélünk, akkor latin négyzet marad, és ha eddig ortogonális volt egy másik latin négyzetre, akkor ezután is ortogonális lesz rá. Ilyen cserékkel elérhető, hogy mindegyik latin négyzet bal alsó sarkában 1-es legyen. A következő oszlopban az 1-es nem lehet az alsó sorban, csak a ( k - 1 ) másikban, így a k négyzet között lesz kettő, amelyekben ugyanott lesz az 1-es a második oszlopban és az elsőben is.

10. feladat. I. megoldás (vázlat): Hozzunk létre egy olyan ábrát, amelynek térbeli vetülete az adott síkbeli ábra! Ez tetszőleges test fölötti sík esetén is megvalósítható. A teret úgy hozzuk létre, hogy felveszünk egy harmadik koordinátát. A bizonyításhoz szükséges egyenesek, síkok tulajdonságai egyenleteikből, tehát a csak alapműveleteket használó algebrából következnek.

II. megoldás (vázlat): Dolgozzunk vektorokkal: D A = ? D A , D B ' = ? D B , D C ' = ? D C . Felhasználva, hogy az X pont pontosan akkor van az U V egyenesen, ha vannak olyan µ , ? valós számok, amelyekre

µ + ? = 1 , és µ D U + ? D V = D X ,

fejezzük ki a D C * vektort D A és D B , D B * -t D C és D A , D A * -t D B és D C segítségével, végül mutassuk meg ugyanezen az elven, hogy A * , B * , C * egy egyenesen vannak.

11. feladat. Azért, mert ez a struktúra megegyezik a valós számok testével! Csak az elemek kaptak bennük más „neveket”: ha minden a valós számot a 2 · a szorzat értékével jelölünk, akkor ezekre az új „nevekre” alkalmazva * -ot, éppen a régi nevekre alkalmazott régi szorzat értékének új nevét kapjuk. Ugyanez igaz természetesen az összeadásra is. Matematikai nyelven: ha f ( a ) = 2 · a minden a -ra, akkor f ( a · b ) = f ( a ) * f ( b ) és f ( a + b ) = f ( a ) + f ( b ) .

12. feladat. A feladatot meg lehet oldani az x 1 - x 2 és y 1 - y 2 előjelei szerinti esetek módszeres ellenőrzésével. A különböző esetekben azonban egyaránt az a tény a döntő, hogy (mint az könnyen végiggondolható) m * x 1 - m * x 2 akkor és csak akkor pozitív, ha m és x 1 - x 2 előjele megegyezik. Ezért ha y 1 - y 2 és x 1 - x 2 előjele megegyezik, akkor az y 1 - y 2 = m * x 1 - m * x 2 egyenlet megoldását elegendő a pozitív m -ek körében keresni, ellenkező esetben pedig a negatív m -ek körében. Mármost pozitív m -ekre m * x 1 - m * x 2 = m ( x 1 - x 2 ) , azaz ha y 1 - y 2 és x 1 - x 2 előjele megegyezik, akkor m = y 1 - y 2 x 1 - x 2 az egyetlen megoldás. Ha pedig y 1 - y 2 és x 1 - x 2 előjele különbözik, azaz ha egy m megoldás csak negatív lehet, akkor látszólag meg kellene különböztetnünk négy esetet az x 1 és x 2 előjele szerint, de ezek lényegében egyformák. Pl. ha x 1 pozitív és x 2 negatív, akkor m * x 1 - m * x 2 = m x 1 - x 2 2 . Tehát egyrészt nem lehet más megoldás, mint m = y 1 - y 2 x 1 - x 2 2 , másrészt ez valóban megoldás, ha negatív. Márpedig az, mert x 1 - x 2 2 ebben az esetben éppúgy pozitív, mint x 1 - x 2 , azaz y 1 - y 2 x 1 - x 2 2 éppúgy negatív, mint y 1 - y 2 x 1 - x 2 . A többi eset azon múlik, hogy ha x 1 negatív és x 2 pozitív, akkor x 1 2 - x 2 éppúgy negatív, mint x 1 - x 2 , ha pedig x 1 és x 2 is negatív, akkor x 1 2 - x 2 2 előjele megegyezik x 1 - x 2 -ével.

13. feladat Ha a = ? 2 és b = ß 2 , akkor a · b = ? 2 · ß 2 = ( ? · ß ) 2 . Tehát két pozitív testelem szorzata pozitív. Továbbá b / a = ( ß / ? ) 2 , tehát a pozitív a -t csak pozitív testelemmel szorozva kaphatjuk meg a pozitív b -t; ez azt jelenti, hogy negatívval szorozva negatív szorzatot kapnánk, tehát két különböző testelem szorzata negatív.

14. feladat. Tegyük fel, hogy a 2 = b 2 = c 2 három különböző a , b , c elemre. Ekkor például a 2 - b 2 = 0 . Miután a véges testekre is igaz, hogy hogy a 2 - b 2 = ( a + b ) ( a - b ) , ezért ( a + b ) ( a - b ) = 0 . Mivel pedig a és b különböző, ez csak úgy lehetséges, ha a + b = 0 , azaz b = - a . De ugyanez szórul szóra igaz, ha b -t kicseréljük c -re! Tehát c = - a = b , ami ellentmond annak a feltevésnek, hogy b és c különböző.

Ami a p = 2 esetet illeti, ekkor is ha a 2 = b 2 lenne két különböző a , b elemre, akkor b = - a teljesülne. Csakhogy ha p = 2 , akkor minden a -ra a + a = 0 , azaz - a = a . Mindezek pedig ellentmondanak annak a feltevésnek, hogy a ? b .

15. feladat. Ha egy 0 -tól különböző a testelemet megszorzunk külön-külön az összes elemmel, akkor csupa különböző elemet kapunk, minden 0-tól különböző testelemet pontosan egyszer. Mármost az előző feladat szerint ha a negatív, akkor a pozitív elemekkel való szorzatai negatívak. Ha tehát valamely negatív elemmel való szorzata is negatív lenne, akkor a testben több negatív elem lenne, mint pozitív. Vagyis a pozitív elemek száma az összes 0-tól különböző elemek számának kevesebb mint a fele volna, és így lenne olyan pozitív elem, ami több mint két elem négyzeteként előáll – de ez ellentmond a 13. feladatnak. (Valójában egyébként abból a feladatból könnyen látható, hogy p //>// 2 esetén ugyanannyi negatív elem van, mint pozitív, de erre most nem volt szükségünk.)

16. feladat. a) Ha p = 2 , akkor az állítás nyilvánvaló, hiszen akkor a 14. feladat szerint minden 0-tó különböző elem pozitív. Ha p //>// 2 , akkor p k páratlan, és a 15. feladatból azonnal következik, hogy a páratlan kitevőjű hatványozások megtartják az előjelet. A 0-nak pedig nyilván minden hatványa 0.

b) Az összefüggés a szorzás kommutativitása miatt teljesül.

c) A (7) és (8) tulajdonságok miatt a véges testekben is igaz a binomiális tétel, vagyis ( a + b ) p k = a p k + ( 1 + 1 + ? + 1 ) a p k - 1 b + ( 1 + 1 + ? + 1 ) a p k - 2 b 2 + ? + ( 1 + 1 + ? + 1 ) a b p k - 1 + b p k , ahol minden i -re a p k - i b i szorzója éppen p k i darab 1-es összege. Mint láttuk, a testben p darab 1-es összege 0, tehát arra van csak szükségünk, hogy minden 1 ? i ? p k - 1 -re – a megszokott, egész számok közti értelemben – p k i osztható p -vel. Ez pl. azért igaz, mert p k i = p k i p k - 1 i - 1 , tehát p k i egy olyan egész szám, ami egy másik egész szám p k i -szerese. Miután i prímfelbontásában p a k -adiknál alacsonyabb fokú hatványon szerepel, a számelmélet alaptétele szerint p k i osztható p -vel.

d) A c) részhez hasonlóan igazolható.

17. feladat. Jelölje a test 0-tól különböző elemeit a 1 , a 2 , , a q - 1 . Legyen a tetszőleges 0-tól különböző elem, és képezzük az

a · a 1 , a · a 2 , , a · a q - 1

szorzatokat. Ezek mind különbözőek, azért kiadják az összes 0-tól különböző elemet, azaz a 1 -et, a 2 -t, , a q - 1 -et, valamilyen sorrendben. Így fennáll az

( a · a 1 ) · ( a · a 2 ) · · ( a · a q - 1 ) = a 1 · a 2 · a q - 1

összefüggés, hiszen a két oldalon ugyanazok a tényezők vannak, csak a sorrendjük jehet más. A zárójeleket felbontva és egyszerűsítve kapjuk, hogy a q - 1 = 1 , tehát a q = a . A legutóbbi összefüggés már a = 0 -ra is nyilvánvalóan teljesül.

18. feladat. (7) és (4) szerint m * x 2 + m * ( - x 2 ) = m * 0 . Tehát ha m * 0 = 0 , akkor m * x 2 + m * ( - x 2 ) = 0 . A - előjel (4)-ben szereplő definíciója szerint ez éppen azt jelenti, hogy - ( m * x 2 ) = m * ( - x 2 ) .

19. feladat. Tegyük fel, hogy a * x 1 = a * x 2 valamely x 1 ? x 2 -re és a ? 0 -ra. Ha (4) teljesül, akkor ezek szerint a * x 1 - ( a * x 2 ) = 0 . De az előző feladat szerint - a * ( x 2 ) = a * ( - x 2 ) Tehát 0 = a * x 1 - ( a * x 2 ) = a * x 1 + a * ( - x 2 ) = a * ( x 1 - x 2 ) . Másrészt a kvázitestek 0-ra vonatkozó szabályai miatt 0 = 0 * ( x 1 - x 2 ) . Mivel x 1 ? x 2 és a ? 0 , ez azt jelenti, hogy (9) nem teljesül.

20. feladat. k szerinti teljes indukciót fogunk alkalmazni. k = 1 -re nyilván igaz az állítás. Legyen f ( x ) egy k + 1 -edfokú polinom,

f ( x ) = a k + 1 · x k + 1 + a k · x k + + a 2 · x 2 + a 1 · x + a 0 ,

és tegyük fel, hogy az állítás igaz k -ra. Ha f ( x ) -nek egyáltalán nincs gyöke, akkor igaz rá az állítás. Ha van, akkor legyen egy ilyen gyök x 0 :

a k + 1 · x 0 k + 1 + a k · x 0 k + + a 2 · x 0 2 + a 1 · x 0 + a 0 = 0 .

f ( x ) = f ( x ) - 0 így írható:

a k + 1 · ( x k + 1 - x 0 k + 1 ) + a k · ( x k - x 0 k ) + + a 2 · ( x 2 - x 0 2 ) + a 1 · ( x - x 0 ) .

Az x i - x 0 i = ( x - x 0 ) · ( x i - 1 + x i - 2 · x 0 + x i - 3 · x 0 2 + + x · x 0 i - 2 + x 0 i - 1 ) azonosságot mindegyik zárójeles kifejezésre alkalmazhatjuk, így

f ( x ) = ( x - x 0 ) · g ( x ) ,

ahol g ( x ) legfeljebb k -adfokú polinom. Az indukciós feltevés miatt g ( x ) -nek legfeljebb k gyöke van, így f ( x ) -nek legfeljebb ( k + 1 ) .

21. feladat. Az x p k - x egyenletnek legfeljebb p k megoldása van, de az adott feltételek mellett p k //<// p n = q , így a nullosztómentesség miatt F q -ban van olyan elem, amelyre x p k ? x .

22. feladat A feladatot nem csak mechanikusan lehet megoldani. Mivel a köbre emelés összegtartó, ezért bármely p , q ? F p -re ( p a + q ) 3 = p a 3 + q . Továbbá mivel a 2 = 2 , ezért ( a 3 ) 2 = ( a 2 ) 3 = 2 3 = 2 = a 2 , tehát a 3 szükségképpen az a -tól különböző gyöke x 2 + 1 -nek. ( 2 3 = 2 nem véletlenszerű, hanem szükségszerű a kis Fermat-tétel miatt.) Tehát a 3 = - a = 2 a , és bármely p , q ? F p -re f ( p a + q ) = ( p a + q ) 3 = - p a + q . Ebből könnyen adódik a szorzótábla:

* 0 1 2 a a + 1 a + 2 2 a 2 a + 1 2 a + 2 0 0 0 0 0 0 0 0 0 0 1 0 1 2 a a + 1 a + 2 2 a 2 a + 1 2 a + 2 2 0 2 1 2 a 2 a + 2 2 a + 1 a a + 2 a + 1 a 0 a 2 a 2 a + 2 2 a + 2 1 a + 1 2 a + 1 a + 1 0 a + 1 2 a + 2 2 a + 1 2 a a + 2 2 a 1 a + 2 0 a + 2 2 a + 1 a + 1 2 a 2 2 a + 2 1 a 2 a 0 2 a a 1 2 a + 1 a + 1 2 2 a + 2 a + 2 2 a + 1 0 2 a + 1 a + 2 2 a + 2 a 1 a + 1 2 2 a 2 a + 2 0 2 a + 2 a + 1 a + 2 1 2 a 2 a + 1 2 2 a

A fenti módszerhez teljesen hasonlóan lehet előallítani egy-egy p 2 elemű André-kvázitestet, ha x 2 + 1 irreducibilis, ami a kis Fermat-tétel egy következménye szerint pontosan akkor igaz, ha p 4-gyel osztva 3-at ad maradékul. A 4 k + 1 alakú prímekre is nagyon hasonló a helyzet, csak azoknál a -t nem választhatjuk x 2 + 1 gyökének, hanem valamely irreducibilis x 2 + c alakú polinom gyökének; ilyen c minden p //>// 2 -re létezik.