Ramseyho problém

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 21. července 2021; kontroly vyžadují 2 úpravy .

Ramseyho problém [1] [2] [3] , problém datování šesti osob [4] je matematický teorém v Ramseyově teorii , speciální případ Ramseyho teorému .

Prohlášení

Ať je na večírku 6 lidí. Pokud se dva lidé setkali alespoň jednou předtím, pak se nazývají známí, pokud ne - neznámí. Podle Ramseyho problému:

V každé společnosti o šesti lidech se buď znají tři lidé ve dvojicích, nebo se tři lidé neznají ve dvojicích.

Převod podmínky na graf

Důkaz lze provést pomocí grafu, kdy podmínku věty zapíšeme v tomto tvaru.

Graf bude mít 6 vrcholů , každá dvojice vrcholů je spojena hranou . Takový graf se nazývá úplný graf (nelze pro něj kreslit nové hrany, protože všechna možná spojení již byla vytvořena). Kompletní graf s vrcholy je označen .

V tomto příkladu můžete vytvořit graf . Tento graf má 15 hran. 6 vrcholů představuje 6 osob uvedených v prohlášení o problému.

Dále je pro nátisk nutné obarvit okraje. Okraj bude zbarven červeně, pokud se dva lidé neznají, nebo modrý, pokud se znají. S přihlédnutím k těmto transformacím lze výrok věty přeformulovat:

Bez ohledu na obarvení hran bude mít graf buď červený trojúhelník (trojúhelník, ve kterém jsou všechny hrany červené), nebo modrý trojúhelník (ve kterém jsou všechny hrany modré). Červený trojúhelník bude znamenat, že 3 lidé jsou v páru cizinci, a modrý trojúhelník bude znamenat, že 3 lidé znají páry. Pokud je toto tvrzení skutečně pravdivé, pak bude pravdivé i původní tvrzení.

Konec důkazu

Dále je pro důkaz zvolen libovolný vrchol P. Z vrcholu vychází pět hran. Podle Dirichletova principu alespoň tři okraje stejné barvy (pokud jsou okraje jedné z barev menší než 3, okraje druhé barvy jsou větší než 3).

A , B , C - vrcholy, ostatní konce výše zmíněných hran. Pokud je alespoň jedna z hran AC, BC, AB modrá, pak můžete získat jednobarevný trojúhelník (pomocí dvou hran z P a právě zmíněného vrcholu). Pokud žádná z těchto hran není modrá, pak jsou všechny červené a z nich můžete získat červený trojúhelník ABC atd .

Ramseyho poznámky

V roce 1930 v článku „On a Problem in Formal Logic“ Ramsey dokázal obecnější větu (známou jako Ramseyova věta ), tato věta je jejím speciálním případem. Ramseyova teorie , jedna z větví kombinatoriky , je založena na Ramseyově teorému .

Jiné případy

Pokud společnost nemá 6 lidí, ale pouze 5, nemusí být důsledek zmíněný v Ramseyho problému proveden.

Abychom ukázali možnost takového případu, je nutné sestavit protipříklad . Protipříkladem je pětiúhelník obklopující pěticípou hvězdu . Pětiúhelník musí být zbarven červeně a hvězda modře. Minimální počet vrcholů, pro které platí vlastnost zadaná v úloze, je tedy 6.

V Ramseyho teorii je tato skutečnost napsána následovně:

Literatura

Visvanatha Krishnamurthy. Kultura, vzrušení a význam matematiky . — Wiley Eastern, 1990-01-01. — 348 s. — ISBN 9788122402728 .

Poznámky

  1. ↑ Jevgenij Vechtomov. Filosofie matematiky 2. vyd. Učebnice pro pregraduální a postgraduální studium . Litr, 2018-12-20. — 318 s. — ISBN 9785041182014 .
  2. ↑ Novikov Fedor Alexandrovič. Diskrétní matematika: učebnice pro střední školy. 2. vyd. Standard třetí generace . - Nakladatelství "Peter", 2012-09-10. — 400 s. — ISBN 9785496000154 .
  3. ↑ Irina Leonidovna Babinskaya. Problémy matematických olympiád . - Nauka, 1975. - 120 s.
  4. ↑ Zhukovsky M.E., A.A. Glibichuk, A.M. Raygorodsky, Shkredov I.D., A.B. Dainyak, D.G. Iljinský, D.V. Musatov, A.V. Savvateev http://ru.discrete-mathematics.org/fall2017/magistracy_online_program.pdf Archivováno 5. února 2018 na Wayback Machine

Odkazy