Ramsey probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 21-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A Ramsey-probléma [1] [2] [3] , a hatszemélyes randevúzási probléma [4] a Ramsey-elmélet matematikai tétele , a Ramsey-tétel speciális esete .

Nyilatkozat

Legyen 6 ember a buliban. Ha két ember korábban legalább egyszer találkozott egymással, akkor ismerősnek nevezik őket, ha nem - ismeretlennek. A Ramsey-probléma szerint:

Bármely hatfős társaságban vagy hárman ismerik egymást párban, vagy hárman nem ismerik egymást párban.

Feltétel konvertálása grafikonná

A bizonyítást gráf segítségével is elvégezhetjük, a tétel feltételét ebben a formában írva.

A gráfnak 6 csúcsa lesz , mindegyik csúcspárt egy él köti össze . Az ilyen gráfot teljes gráfnak nevezzük (lehetetlen új éleket rajzolni hozzá, mivel már minden lehetséges kapcsolat létrejött). A csúcsokkal rendelkező teljes gráfot jelöli .

Ebben a példában grafikont készíthet . Ennek a gráfnak 15 éle van. 6 csúcs a problémafelvetésben említett 6 embert képviseli.

Továbbá a bizonyításhoz szükséges a szélek színezése. A széle piros lesz, ha a két ember nem ismeri egymást, vagy kék, ha ismerik egymást. Ezen transzformációk figyelembevételével a tétel állítása újrafogalmazható:

Az élek színétől függetlenül a gráfnak vagy piros háromszöge (egy olyan háromszög, amelyben minden él piros) vagy kék háromszöge (amelynek minden éle kék) lesz. A piros háromszög azt jelenti, hogy 3 ember páronként idegen, a kék háromszög pedig azt, hogy 3 ember páronként ismerős. Ha ez az állítás valóban igaz, akkor az eredeti állítás is igaz lesz.

A bizonyítás vége

Ezután a bizonyításhoz egy tetszőleges P csúcsot választunk , a csúcsból öt él emelkedik ki. A Dirichlet-elv szerint legalább három azonos színű él (ha az egyik szín éle kisebb, mint 3, akkor a másik színé több mint 3).

A , B , C - csúcsok, a fent említett élek többi vége. Ha az AC, BC, AB élek legalább egyike kék, akkor egy egyszínű háromszöget kaphat (a P két élét és az imént említett csúcsot használva). Ha egyik él sem kék, akkor mindegyik piros, és belőlük kaphat egy piros ABC háromszöget stb .

Ramsey feljegyzései

1930-ban az "On a Problem in Formal Logic" című cikkében Ramsey egy általánosabb tételt bizonyított ( Ramsey-tételként ismert ), ez a tétel ennek egy speciális esete. A Ramsey- elmélet , a kombinatorika egyik ága , a Ramsey-tételen alapul .

Egyéb esetek

Ha a cégnek nem 6, hanem csak 5 fője van, előfordulhat, hogy a Ramsey-problémában említett következmény nem valósul meg.

Egy ilyen eset lehetőségének bemutatásához egy ellenpéldát kell alkotni . Ellenpélda egy ötágú csillagot körülvevő ötszög . Az ötszöget pirosra, a csillagot kékre kell festeni. Így a csúcsok minimális száma, amelyre igaz a feladatban megadott tulajdonság, 6.

Ramsey elméletében ezt a tényt a következőképpen írják le:

Irodalom

Visvanatha Krishnamurthy. A matematika kultúrája, izgalma és relevanciája . - Wiley Eastern, 1990. 01. 01. — 348 p. — ISBN 9788122402728 .

Jegyzetek

  1. ↑ Jevgenyij Vectomov. Matematikafilozófia 2. kiadás. Tankönyv alap- és posztgraduális tanulmányokhoz . Liter, 2018-12-20. — 318 p. — ISBN 9785041182014 .
  2. ↑ Novikov Fedor Alekszandrovics. Diszkrét matematika: Tankönyv középiskolák számára. 2. kiadás Harmadik generációs szabvány . - "Peter" kiadó, 2012-09-10. — 400 s. — ISBN 9785496000154 .
  3. ↑ Irina Leonidovna Babinskaya. Matematikai olimpiák feladatai . - Nauka, 1975. - 120 p.
  4. ↑ Zsukovszkij M.E., A.A. Glibichuk, A.M. Raygorodsky, Shkredov I.D., A.B. Dainyak, DG. Iljinszkij, D.V. Musatov, A.V. Savvateev http://ru.discrete-mathematics.org/fall2017/magistracy_online_program.pdf Archiválva : 2018. február 5. a Wayback Machine -nél

Linkek