2013. február 25., hétfő

Grötzschman

Kretén magazin 2004/4 száma:

  • Ön milyen man szeretne lenni, és mit csinálna akkor, ha Ön szuperhős lenne, mi lenne a neve és milyen szuperképességekkel rendelkezne?

  • Én bizony Grötzschman lennék, és ha bárhol a világon valakinek gondjai adódnának a Mycielski-konstrukcióval, illetve a Grötzsch-grágokkal, akkor előtűnnék a semmiből és megoldanám minden problémájukat.



Síkba-rajzolható-e a Grötzsch-gráf?

(azaz le tudjuk-e rajzolni úgy, hogy nincs benne kereszteződés)

Az ábrán látható Grötzsch gráf nem lesz síkbarajzolható. A belátáshoz K5 –öt, K3,3 –at vagy ezek soros bővítését keressük a gráfban. A K5 –öt nem találunk, de a remény még megvan a K3,3 –ra, vagy soros bővítésére. Ezt meg is találjuk. A kutakat jelölhetjük fekete pontokkal, a házakat szürkékkel. A fehéren maradt pontok, pedig  a soros bővítést jelentik. Mivel megtaláltuk a három ház – három kút gráf soros bővítését, nem lesz síkbarajzolható a Grötzsch gráf.




megjegyzés:



Definíció. A K5 és a K3,3 gráfokat Kuratowski-gráfoknak nevezzük. A K5 az 5 pontú teljes gráf. A  K3,3 gráfot szokás  három ház – három kút gráfnak is nevezni. Az elnevezés onnan ered, hogy a gráf csúcsai olyanok, mint három ház és (velük szemben) három kút. Az élei pedig az utak, melyek minden házat összekötnek minden kúttal. Láthatjuk, hogy az utakat kereszteződések nélkül nem lehet lerajzolni. Tehát a gráfban lesznek egymást 

keresztező élek. Azt, hogy a K3,3 és a K5 esetében sem lehet az éleket kereszteződés nélkül lerajzolni a síkba.




Tétel: A Kuratowski-gráfok nem rajzolhatóak síkba.

Tétel: (Kuratowski-tétel). Egy G gráf akkor és csak akkor síkbarajzolható, ha nem  

tartalmazza részgráfként a K5 és a K3,3 gráfokat, sem ezek soros bővítéseit.

2013. február 24., vasárnap

Happy End

Tétel: Bárhogyan veszünk fel öt általános helyzetű pontot a síkban, mindig kiválasztható közülük egy konvex négyszög négy csúcsa.

Az állítás bizonyítása fontos eredmény volt, ez vezetett a kombinatorikus geometria megalkotásához, a Ramsey-elmélethez és Klein Eszter és Szekeres György házasságához.

A problémát először 1932-ben vetette fel Klein Eszter az Anonymus csoport tagjainak. Miután hagyta a többieket gondolkozni, bemutatta az ő megoldását. Később Szekeres György és Erdős Pál általánosították az eredményt. Az eredetei problémát Erdős keresztelte el Happy End-problémának, mivel Szekeres György és Klein Eszter házasságához vezetett.

A házaspár matematikus berkekben ismerkedett meg, 1936-ban házasodtak össze.
"Emlékszem az esküvő napjára egy nappal azután történt, hogy Vinogradov bebizonyította a páratlan Goldbach-sejtést."                                                                       (Erdős Pál)
Szekeres György és Eszter utolsó heteiket egy szanatóriumban, közös szobában töltötték. 69 év házasság után ugyanazon a napon (2005. augusztus 28) fél óra eltéréssel haltak meg.

Életük röviden:
A zsidóüldözés elől Sanghajba menekültek – Szekeres György vegyészként egy gyárban dolgozott –, ott vészelték át a második világháborút, a japán megszállást és a kommunista fordulat kezdetét. Itt született meg Peter fiuk is. Ahogy a háborús helyzet fokozódott, a kisgyermekkel elmenekültek, és Hongkew-ban, lényegében a sanghaji gettóban éltek.1948-ban Szekeres György Adelaide egyetemének matematikai tanszékén kapott adjunktusi állást. Évekig Svéd Márta adelaide-i lakásában éltek. 1954-ben született meg Judy lányuk. 1963-ban a család Sydneybe költözött. Szekeres Eszter itt a Macquarie Egyetemen adott órákat, és a középiskolás diákok matematikatudását fejlesztette. 1984-ben másokkal együtt megalapított egy heti matematikatudás-fejlesztő összejövetelt, ami azóta mintegy 30 csoportot foglal magába, melyek hetente találkozókat tartanak, és inspirálják Ausztrália és Új-Zéland középiskolás diákjait. 2004-ben egészségi okokból visszaköltöztek Adelaide-be. (Wikipédia)

forrás: hvg.hu
          www.wikipedia.hu

2013. február 23., szombat

Párválasztás

Ruzsa Imre: Kinek van a legnagyobb?

(tanmese)



 Hol volt, hol nem volt, az óperenciás tengeren túl, de az üveghegyen azért innen, élt egyszer egy király, volt neki egyetlen egy fia. Ez a király egyszer így szólt a fiához:

    - Édes fiam, én már öreg vagyok, beteges vagyok, csupa nyűg nekem az uralkodás. Átadnám én neked a koronát örömest, csupáncsak egy kívánságom van. Nősülj meg előbb, mert a nép azt szereti, ha megállapodott családapa uralkodik rajta, nem pedig egy duhaj legényember.

    No, beleegyezett a királyfi a kívánságba, noha igencsak kevéssé fűlött a foga a házasodáshoz.

    Hát amint híre ment, hogy a királyfi nősülni készül, és utána a trónt is megkapja, elkeztek áradni a palotába az eladó lányok, mert hát igen nagy és gazdag országról volt szó. Jöttek királylányok, hercegnők, grófkisasszonyok csőstül, ki-ki a rangjához illő kísérettel. Jött mindegyikkel követ is, aki kommendálta; kinek szép arcát dicsérték, kinek híres őseit emlegették, kinek műveltségét vagy erkölcsös életét, vagy apjának hatalmát és gazdagságát, és mindegyik erősítgette, hogy az ő kisasszonyából lenne a legjobb királynő. Bizony megterhelte a sok látogató a királyi konyhát, fényes ruháik a királyi mosodát, nem is beszélve a letaposott hercegnői lábacskákról reggelente a királyi fürdőszobák előtt.

    Nem tudott a királyfi választani a sok szebbnél szebb és mindenféle jó tulajdonságokkal ékes lány között; de azt az egyet biztosan tudta, bármelyiket veszi is el, magára haragítja az összes többit.



    Gondolta hát egyet, és nagy bált rendezett az összes vendég részvételével. Kis idő múltán, amikor már a tánctól felhevültek és a jó hangulat tetőfokára hágott, leintette a zenét és így szólt hozzájuk:
    - Nagyságos kisasszonykáim, nagy öröm és büszkeség, hogy ennyien vagytok, akik készek lennétek a kezeteket nyújtani nekem. Mert mindnyájan nagyon szépek vagytok, származásotok előkelő, hírnevetek makulátlan, viselkedésetek fejedelmi, társalgásotok elbűvölő. Bevallom, erényeitek alapján nem tudok köztetek választani. Ezért úgy döntöttem, azt veszem feleségül, akinek a legnagyobb a segge.
    Igen dicsérte mindenki a királyfi érett bölcsességét, hogy olyasmiben tűzte ki a versengést, amiben lemaradni nem nevezhető szégyennek. Ám a választás nem lett sokkal könnyebb. Mert bár sokan, látva esélytelenségüket, nagy méltatlankodással eltávoztak, még mindig maradtak elegen, akik úgy vélték, őket illeti a királynői korona. A királyfi pedig hiába kért tanácsot akár minisztereitől, akár a festőktől és szobrászoktól, akiknek a modellek kiválasztásához az ilyesmi megítélésében nagy gyakorlatra kellett szert tenniük, akár a nadrág- és szoknyaszabóktól, a sok ellentmondó összevissza tanácstól már azt se tudta, hol áll a feje.
    Belátta végül, hogy ezt a fogós kérdést csak az ország bölcs véneinek együttes tudása képes megoldani, és átadta a kérdést a Királyi Tudományos Akadémiának.
    Az Akadémián - minden precedenstől eltérő módon - több osztály is illetékesnek érezte magát. Az Orvostudományok Osztálya úgy vélte, hogy mivel emberi testről van szó, őket illeti a döntés; a Biológiai Osztály szerint az orvosok foglalkozzanak a betegekkel, és itt nagyon is egészséges testekről van szó, a dolog tehát rájuk tartozik; a Műszaki Osztály szerint, mivel mérésekről is lesz szó, őket semmiképpen sem lehet kihagyni; az Ókortudományi Osztály pedig arra hivatkozott, hogy már Párisznak is hasonló problémát kellett megoldania. A matematikusok átaludták a vitát.

  Végezetül egy interdiszciplináris Proktometriai Bizottság felállítása mellett döntöttek. Ez nyomban felosztotta magát két albizottságra; az Elméleti Bizottság feladata lenne a mérések módszertanának megalapozása és az adatok feldolgozása, míg a Gyakorlati Bizottságra maradna a mérések tényleges elvégzése. Teljesen érthetetlen módon mindenki a Gyakorlati Bizottságba kívánkozott, de végül csak sikerült az Elméleti Bizottságot is felölteni néhány nyolcvan év fölötti, különösen házsártos feleségű akadémikussal.

    Elég hamar kitalálták, mivel jellemezhető a far abszolút nagysága. A vizsgált személy álló helyzetében a fal mellett meghatározzák a test leghátsó pontját (apex clunis), majd, álĺítható magasságú mérőlécekből ügyesen összeeszkábált szerkezet segítségével megmérik ennek távolságát a comb első oldalának azonos magasságú pontjától: ez a domborúság (tomporúság?). Ugyanezen magasságban megmérik a comb bal- és jobbszéle közti távolságot, majd veszik e két mennyiség szorzatát; ez az alapvető jelentőségű area clunis függvény, jele ω, mértékegysége a páros négyzetláb.
    Első pillanattól világos volt, hogy nem lehet egyszerűen a fenti adatot venni, hiszen az a nagydarab lányoknak kedvezne, az pedig mégse lehet, hogy a király felnézzen a feleségére! Ha leosztjuk a testmagassággal, esetleg annak valamilyen hatványával, az egy fokkal jobb, de még mindig nem tökéletes. Meg kell tudni különböztetni azt, ha valakinek tényleg a feneke nagy (essentialis hyperproktia) attól, aki egyszerűen kövér. (Mióta a királyfi megtette nyilatkozatát, a környék cukrászdáinak forgalma többszáz százalékkal emelkedett.) Jó ötletnek látszott a fenti adatot összevetni a csípőcsont méreteivel, hiszen az adottság, ami azon túl van, az viszont már egyéni vívmány, ám történetünk régen játszódik, amikor királykisasszonyok voltak bőségben, de röntgen még nem volt. Vagy a derékbőséggel, az viszont lágy hús, könnyen behúzható, objektív mérése tehát igencsak problematikus.
    Végül, pár hónap alatt, csak sikerült kidolgozni az ideális képletet a "gluteális koefficiens" névvel illetett farossági mérték kiszámítására. Ám eközben történt valami, amitől a vénséges vén anyakirályné már rég tartott, csak nem figyelt rá senki. A királyfi addig forgolódott a menyasszonyjelöltek között, amíg beleszeretett az egyikbe. E szavakkal állt bátran az öreg király elé:
    - Felséges atyám, életem-halálom kezedbe ajánlom, nekem pedig senki sem lesz a feleségem, hacsak nem a Boriska hercegkisasszony.
    - Nem addig van az, édös fiam. Ha már egyszer kihirdetted a szabályt, tartanod kell magad hozzá.
    - No de amikor azt mondtam, nem voltam szerelmes, és mindegy volt nekem, melyiket veszem el a sok ismeretlen lány közül. Nem ez lesz az első ígéret a világon, amit megszegnek.
    - Igazad volna, ha paraszt volnál, vagy polgár, vagy akár nemes. De a király házassága az ország ügye. Ha megszeged a szavad, és mást veszel el, mint akit a bizottság kijelöl, az országnak szerzel megannyi ellenséget.
    - Én pedig inkább lemondok a trónról, mintsem mást vegyek el, mint akit szeretek.
    - Jaj, csak azt ne tedd, - mondta az öreg király igen elszomorodva, - te vagy az egyetlen trónörökös, idegen kézbe jutna a korona, vagy ami még szörnyűbb, köztársaság lenne!
    No, megpróbált a király segíteni a dolgon. Összehívta mindkét proktometriai bizottság együttes ülését, és így szólt hozzájuk:
    - Megkönnyítem a dolgotokat, nagytudományú bölcsek. Megmondom, ki lesz a győztes, nektek csak azt kell kigondolnotok, hogy miért.
    Nagy felzúdulás támadt erre a tudósok között. Boriska elég jól állt a mezőnyben, de semmiképpen se volt az elsők között. Mondott még a király nekik szépet is, csúnyát is; ha sikeresen megoldják a feladatot, ígért nekik kincseket, rangokat, kitüntetéseket, ha meg nem, akkor a Tudományos Akadémiát beolvasztják a Királyi Sóhivatalba. Néhányan azonnal felháborodottan lemondtak a Proktometriai Bizottság tagságáról; mások megpróbálták Boriskát kihozni győztesnek, majd amikor nem sikerült, ők is rájöttek, hogy ez nem fér össze a lelkiismeretükkel.


    Ismét összegyűlt az Akadémia, hogy újraválassza a megfogyott Proktometriai Bizottságot. Ezúttal a szakosztályok sorban zárkóztak el a részvételtől. A Királyi Főmatematikus szunyókált, és arra rezzent fel az ülés végén, hogy már meg is van választva.
    - Miről van szó? Találni kell egy függvényt, aminek adott helyen van a maximuma? De hát mi ebben a nehéz? - kérdezte csodálkozva, és nyomban rá is bízta a feladatot a docensére; a docens azonnal odaadta az adjunktusnak; az adjunktus íziben kiosztotta a doktoranduszának; a doktorandusz pedig dolgozatot íratott belőle az elsőévesekkel. A Főmatematikus közben a biztonság kedvéért újramérte a királykisasszonyok adatait.

    A királyfi - most már király - mérhetetlenül boldog volt, ifjú felesége nemkülönben; a nép éljenzett, az öreg király elégedetten nyugalomba vonult, a hoppon maradt király-, herceg- és grófkisasszonyok pedig kicsit csalódottan, de azért azzal a tudattal tértek haza, hogy eddig is jót mulattak a szomszéd ország költségén.
    A matematikusoktól megkérdezték, milyen jutalmat kérnek.
    - Hát hogy ezután minden ülésen zavartalanul alhassunk -, felelte a Főmatematikus.
    Meg is kapta nyomban az erről szóló királyi adománylevelet, a legfinomabb pergamenre írva cifra arany betűkkel, óriási vörös pecséttel. Ekkor jutott eszükbe, hogy talán kérhettek volna mást is - hatalmas fizetést, rendszeres tanulmányutakat Tündérországba, vagy hogy a bölcsészeket vessék a sárkányok elé -, de akkor már késő volt.



2013. február 22., péntek

Hány évesen házasodjunk?

Ausztrál matematikusok a University of New South Wales's School of Mathematics and Statistics egyetemen megalkották azt az egyenletet, amivel kiszámolható a házasságkötés optimális időpontja. A képlet közel se nevezhető tökéletesnek, alkotói szerint 40% körüli a hatékonysága.


Tudni szeretnéd hány évesen kell (vagy kellett volna) megházasodnod? Nem kell mást tenned, mint elvégezni az alábbi műveleteket - legalább is az ausztrál matematikusok így gondolják.



1. Legyen "n" a legkésőbbi életkor, amikorra már mindenképp házas szeretnél lenni!

2. Legyen "p" az az életkor, amikor elkezdesz gondolkodni a házasságon!

3. Vedd n és p különbségét (n-p), az eredményt szorozd meg 0,368-cal!

4. A hármas pontban kapott eredményed add hozzá a "p"-hez!

Nézzünk egy konkrét példát:


1. n=39, azaz 39 évesen szeretnék már házas lenni.

2. p=20, azaz 20 évesen már eltudnám képzelni, hogy megállapodjak egy végleges partner mellett.

3. (39-20)*0,368 = 6,992  7

4. 20+7 = 27, azaz a fenti adatok alapján 27 évesen kellene, hogy megházasodjak.



források:

2013. február 21., csütörtök

Teljes indukció (?)


Minden nőnek kék a szeme


Bizonyítás:

Elég azt megmutatni, hogy nők bármely halmazában bármely két nőnek egyforma színű a szeme. Ezt alkalmazhatjuk az összes nők halmazára. Tudjuk, hogy van kék szemű nő, és így a többiek szeme is kék.


Az állítást a nők száma szerinti teljes indukcióval bizonyítjuk.

  • Ha csak egy nő van a halmazban, akkor nyilván igaz, hogy a halmazban bármely két nőnek ugyanolyan színű a szeme.
  • Tegyük föl, hogy az állítást már tudjuk minden n elemű halmazra.
  • Tekintsük nők egy tetszőleges n+1 elemű halmazát: {Kati, Sára, Dóra, Anna,...}. 
    Ha Katit kihagyjuk, akkor n elemű halmaz marad, ebben az indukciós feltevés miatt mindenkinek egyforma, mondjuk kék színű a szeme.
    Ugyanígy, ha Annát hagyjuk ki, akkor is azt kapjuk, hogy a megmaradó nők halmazában mindenkinek egyforma színű a szeme. De Dóra szeme kék, így Katié is. Tehát az n+1 elemű halmazban is mindenkinek ugyanolyan (azaz kék) színű a szeme.

2013. február 8., péntek

Mr. Nobody


Ki tudja, mit hoz a jövő?


Az élet ábrázolható lenne egy óriás gráfként, ha tudnánk melyik döntésnek mi lesz a következménye. Illetve ha másképp döntünk, mi történt volna. Ugye, ismerősek a "mi lett volna, ha" kezdetű mondatok?
A gráf pontjai (elágazások) jelölnék a döntéseket. Ám nincs ekkora szerencsénk (?). Így míg mi a "sötétben tapogatózunk", a filmipar megalkotta a filmet, melyben a kisfiú megvizsgálhatja az alternatív döntések kínálta jövőt is. Mr. Nobody...


A történet röviden:

Nemo Nobody hétköznapi életet él feleségével, Elise-vel és három gyermekükkel, mindaddig, amíg egy napon a valóságra ébred idős öregemberként, 2092-ben. Mr Nobody a maga 120 évével a legidősebb ember és egyben az utolsó halandó is a Földet benépesítő új és halhatatlan emberi faj tagjai között. Ám ez úgy tűnik, nem igazán izgatja őt, az egyetlen kérdés, amely foglalkoztatja, hogy valóban azt az életet élte-e, amely számára a legmegfelelőbb volt; valóban azt a nőt szerette-e, akit neki szántak és azokat a gyerekeket nevelte-e, akiket kellett. Most csak az a célja, hogy megtalálja erre a választ.



Nekem négyszer kellett megnéznem a filmet, hogy megértsem, melyik döntésből mi következik. Az első alkalommal elment a kedvem az egésztől. Ám a harmadik alkalommal megértettem miért szeretik ismerőseim. 
Az utolsó két megnézésem alkalmával neki álltam rajzolgatni. Íme az eredmény:


"Elsőre a helyes döntést kell meghoznod. Amíg nem választottál, még minden lehetséges"

2013. február 7., csütörtök

Fibonacci sorozat másképp


A nyulak szaporodása






Fibonacci gondolatkísérlete szerint egy nyúlpár a második hónaptól képes szaporodni, és innentől kezdve a nyúlmama havonta egy hím és egy nőstény nyulat hoz világra. Az érési idő elteltével ezek az utódok is sokasodni kezdenek, és soha nem pusztulnak el, hiszen matematikai nyulak.

A kérdés: Hány pár nyúlra szaporodik a kezdeti nyúl pár?

Megoldás:


  1. A második hónap végén születik 1 pár, így most már 2 pár van.
  1. A harmadik hónap végén az eredeti párnak is születik egy pár nyula, így már 3 pár lesz.
  1. A negyedik hónap végén az eredeti párnak lesz újabb kicsinye, és a második hónapban születettpárnak is születik egy pár nyula, így összesen már 5 pár nyúl van.


A nyúlpárok száma így az egyes hónapokban 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... A sorozat tagjainak rekurzív (ismétlődő lépésekből álló műveletsorozaton alapuló) képzési szabálya nagyon egyszerű (az új tag mindig az előző két tag összege). Az igazsághoz hozzátartozik, hogy indiai matematikusok mintegy 50 évvel megelőzték Fibonaccit e sorozat felismerésében (aki erről nem tudott).




Ám mi van akkor, ha a nyulak nem matematikai nyulak, azaz egy idő után elpusztulnak? 


Egy mezei nőstény nyúl átlagosan évente 2-3-szor ellik. Az első alomnál 1-2, a másodiknál 2-5 kölyköt. Az öreg példányok inkább kevesebbet. Így nem okoz a valós adatoktól nagy eltérést, ha továbbra is alkalmanként két utóddal számolunk. A mezei nyulak átlagosan 6 évig élnek. Itt nem vesszük figyelemben azt a 80-100 ezer szerencsétlen nyulat, akiket évente lelőnek, sem a róka és egyéb támadásokat. Azaz a nyulaink csak természetes halált halnak. 
Kezdjük az egészet az "Ádám és Éva" nyulaktól. Ekkor a 7. év elején elpusztul az első pár, 7. év második ellési időszakában pedig a második pár. A harmadik ellési időszakban viszont már két pár.



Tehát a "nyúl szám növekedését egy év alatt" a következő függvény írja le: 
, ahol F(n) az n-edik Fibonacci szám (a sorozat n-edik tagja)


azaz:        


A nyúl szám egy adott n évben pedig nem más, mint:
A Fibonacci-sorozat első n tagjának az összegének és az első (n-18) tagjának az összegének a különbsége, ami pont megegyezik az ((n+2)-edik tag - 1) és az ((n-16)-odik tag - 1) különbségével. 



Tehát az aratásnak, fertőzéseknek, rókáknak, nagyobb ragadozómadaraknak, kóbor kutyáknak, nyesteknek, menyétféléknek, farkasoknak és a vadászoknak köszönhetjük, hogy a nyulak nem vették át a hatalmat Bolygónk felett.