Levelezős csapatverseny – 3. feladatsor – megoldások

I. feladat – 13 pont

Jancsika az accrai Kotoka Nemzetközi Reptérre érve tudta meg, hogy a járatot amire a jegye szólt törölték, így csak New Yorkon keresztül tud hazautazni frankfurti átszállással. A következő 16 órát, vagyis az indulásig tartó időt, a reptéri magazinban talált fejtörő megoldásának szentelte.

I. Az alábbi listában igaz, hamis, és megoldatlan (2012. dec. 31-ig nincs a matematikus társadalom által elfogadott megoldásuk) állítások szerepelnek. Találjátok ki minél többről, melyik csoportba tartozik. Pontozzuk az igaz állításokra adott bizonyításokat, a hamisakra adott cáfolatokat, és a lista alapján levont egyéb következtetéseket.

Segítség: a feladatsoron belüli hivatkozások egy kivételével igazak.

  1. Minden hármagasságpontja a háromszögön belülre esik.
  2. Létezik olyan szám, amelynek a 7. hatványa 7777777-re végződik.
  3. Minden páros pozitív egész előáll legfeljebb két prím összegeként.
  4. Az ötödik és a második állítás közül pontosan egy igaz.
  5. A harmadik állításra széles körben ismert csak középiskolás eszközöket használó bizonyítás.
  6. Ha hétszer egymás után dobunk egy dobókockával, ugyanannyi az esélye annak, hogy {a dobott számok összege páratlan}, mint annak, hogy {hamarabb dobunk kettest, mint ötöst, feltéve, hogy kettest és ötöst is dobunk}.
  7. Minden 22k+1 alakú szám prím.
  8. Ha van három ház, és három kút, és minden háztól minden kútig vezet egy út, akkor van az utak között kettő olyan, amik keresztezik egymást.
  9. A hetedik állítás pontosan akkor igaz, ha az első nyolc állításból legalább kettő megoldatlan probléma.
  10. Egy n csúcsú fagráf csúcsait megcímkézhetjük az {1, 2, ..., n} számokkal (mindegyiket pontosan egyszer használva) úgy, hogy az élekre a végpontjaik címkéinek különbségét írva pontosan az {1, 2, ..., n-1} számokat kapjuk.
  11. Ha egy kockát egy síkkal elmetszve egy szabályos sokszöget kapunk, akkor az egy szabályos háromszög vagy egy négyzet.
  12. 9 ember között mindig van 3, akik közül mindenki mindenkinek barátja, vagy 4, akik közül senki senkinek sem barátja.
  13. Az első tizenkét kérdésben a megoldatlanok száma, a hamisak száma és az igazak száma egy háromtagú számtani sorozatot alkot.
  14. Végtelen sok 2p-1 alakú prímszám van.
  15. A kakaó és az alkoholmentes sör közül pontosan az egyiket szeretem.
  16. Minden nemnulla természetes számhoz létezik a Fibonacci sorozatnak olyan eleme, ami osztható az adott számmal.
  17. Egy üres rácstetraéder térfogata mindig azonos. (3 dimenzióban az a síkbeli tétel, hogy minden üres rácsháromszög területe 1/2)
  18. Ha adott egy véges halmaz, és a részhalmazainak egy nemüres, és nem csak az üres halmazt tartalmazó rendszere, amely zárt az unióképzésre (a halmazrendszer bármely kettő elemének az uniója is eleme a halmazrendszernek), akkor a halmaznak biztosan van olyan eleme, ami a halmazrendszer elemeinek legalább a felében benne van.
  19. A 13-14-15-16-17-18 kérdések között különböző paritású darab megoldatlan és hamis állítás van, de az igaz és hamis állítások számának paritása megegyezik.
  20. Egy Artin-gyűrű Jacobson-radikálja szerinti faktora véges sok, ferdetest feletti mátrixgyűrű direkt szorzatával izomorf.

Megoldások:

  1. Hamis, bármilyen tompaszögű háromszög ellenpélda.
  2. Igaz, a 895633 hetedik hatványa például a 462285858958416113703970936961650987777777.
    (A modulo 10000000 maradékosztályok csoportot alkotnak a szorzásra nézve, ennek elemszáma a 10000000-nél kisebb, 10000000-hez relatív prím számok száma, ami nem osztható héttel. Mivel egy csoportban a k-adik hatványra emelés automorfizmus lesz, ha k nem osztja a csoport elemszámát, így minden elem előáll egy másik elem k-adik hatványaként.)
  3. Megoldatlan, a páros Goldbach-sejtés állítása: minden 2-nél nagyobb páros szám előáll két prímszám összegeként.
  4. Igaz, mert 2. igaz, 5. hamis.
  5. Hamis. Semmilyen sem ismert.
  6. Igaz. Mindkettőnek 1/2.
    Egy lehetséges indoklás vázlata: párosítsuk össze a lehetséges 7-hosszú dobássorozatokat úgy, hogy a mind a hét dobásnál az egy sorozatban és a párjában dobott számok összege 7 legyen (ez egy egyértelmű párosítás). Ekkor egy sorozat és a párja közül pontosan az egyikben lesz páros a dobott számok összege. Illetve, ha egy sorozatban van 2 és 5 is, akkor a párjában is, és az egyikben a 2, a másikban pedig az 5 szerepel előbb.
  7. Hamis. Az első 5 ilyen szám (3, 5, 17, 257, 65537) valóban prím, megoldatlan sejtés, van-e több.
    Megj.: az ilyen alakú számokat Fermat-prímeknek nevezik, és a szerkeszthető szabályos sokszögek leírásánál fontosak.
  8. Igaz. Ezt a gráfot három-ház-három-kút gráfnak vagy Kuratowski-gráfnak hívják, és nem síkbarajzolható (ez egyszerű esetszétválasztással bizonyítható). Sőt, igaz az a tétel (Kuratowski-tétel), mely szerint egy gráf pontosan akkor rajzolható síkba, ha „valamilyen módon” nem tartalmaz teljes ötszöggráfot, vagy három-ház-három-kút gráfot.
  9. Igaz, mivel a 7. állítás hamis, és az első 8 közül csak a 3. megoldatlan. (A 7. nem megoldatlan, mert az adott számok között van több, amiről ismert, hogy nem prím. Ha valaki az 5.-et megoldatlannak vette, nem vontunk le pontot)
  10. Megoldatlan. „Graceful Tree Conjecture” vagy „Ringel–Kotzig conjecture” néven ismert.
  11. Hamis, egy testátlót felező síkkal való metszet szabályos hatszög.
  12. Igaz. Először bebizonyítjuk, hogy 6 ember között mindig van 3, akik kölcsönösen barátok, vagy 3, akik kölcsönösen nem szeretik egymást. Válasszunk egy embert találomra! Neki az 5 másik ember között vagy van 3 barátja, vagy van 3 nem-barátja. Ha 3 barátja van, akkor ha azok között van kettő, akik barátok, akkor ez a két barát és az elején kiválasztott ember 3 kölcsönösen barát. Ha az elején kiválasztott embernek a 3 barátja között semelyik 2 sem barátja egymásnak, akkor ez a 3 ember jó lesz, mert kölcsönösen nem szeretik egymást. Ha az elején kiválasztott embernek 3 nem-barátja van, akkor is elmondható gyakorlatilag ugyanez. 9 emberre: lesz olyan ember, akinek van vagy 6 nem-barátja, vagy 4 barátja (ellenkező esetben mindenkinek 3 barátja és 5 nem-barátja kellene legyen, de ekkor 3*9/2=13,5 barát-él és 5*9/2=22,5 nem-barát-él kellene legyen a gráfban, ami nyilván nem lehet). Ha 4 barátja van, akkor ha ezek közül bármely kettő barátja egymásnak, akkor a kiindulási emberrel együtt megvan a 3 barát, ha semelyik kettő sem barátja egymásnak, akkor pedig megvan a keresett 4 nem-barát. Ha a kiindulási embernek 6 nem-barátja van, akkor ezek között mindenképpen lesz 3 kölcsönösen barát vagy 3 kölcsönösen nem-barát. Első esetben az a 3 ember, másodikban az a 3 ember + a kiindulási ember jó lesz.
  13. Igaz, 2; 4; 6.
  14. Megoldatlan, ezeket hívják Mersenne-prímeknek.
  15. Természetesen igaz, a 19.-ből lehetett visszakövetkeztetni.
  16. Igaz. Trükk: a szokásos Fibonacci-sorozat: 1, 1, 2, 3 ... De ezt ki lehet egészíteni 0. elemként a 0-val, ami minden pozitív egésszel osztható. Belátható, hogy a Fibonacci-sorozat ciklikus, ha maradékosan elosztva nézzük valamilyen számmal. Így a 0 is fog benne újra szerepelni, tehát lesz benne minden n-re azzal osztható szám.
  17. Hamis. Vágjunk fel egy egységkockát 5 tetraéderre úgy, hogy levágjuk négy sarkát (minden másodikat): négy darab tetraédert, melyek a kocka sarkából kiinduló élei a kocka 3 éle, a másik három éle pedig a kocka 3 db lapátlója, melyek egy szabályos háromszöget alkotnak. Az ötödik tetraéder ami marad még a kockából, egy szabályos tetraéder, minden éle a kocka lapátlója volt valamikor. Egy saroktetraéder térfogata: 1*1*(1/2)=A; 1=m; 1*1*(1/2)*1*(1/3)=1/6=V. Így az ötödik tetraéderé: 1-4*(1/6)=1/3. Tehát a kétféle tetraéder térfogata különbözik.
  18. Megoldatlan. „Frankl's union closed set conjecture”
  19. Igaz.
  20. Igaz, Wedderburn-Artin tétel.

    21. Vissza a feladatsorhoz | I. feladat | II. feladat | III. feladat | IV. feladat | V. feladat | VI. feladat | VII. feladat | VIII. feladat | IX. feladat | X. feladat | XI. feladat

     

     

    A verseny kereteit a TÁMOP - 4.2.2/B-10/1-2010-0030
    „Önálló lépések a tudomány területén” pályázat biztosította.