Problema Ramsey

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 21 iulie 2021; verificările necesită 2 modificări .

Problema Ramsey [1] [2] [3] , problema întâlnirii cu șase persoane [4] este o teoremă matematică în teoria Ramsey , un caz special al teoremei Ramsey .

Declarație

Să fie 6 persoane la petrecere. Dacă două persoane s-au întâlnit cel puțin o dată înainte, atunci se numesc cunoștințe, dacă nu - necunoscute. Conform problemei Ramsey:

În orice companie de șase persoane, fie trei persoane se cunosc în perechi, fie trei persoane nu se cunosc în perechi.

Convertirea unei condiții într-un grafic

Demonstrarea poate fi efectuată folosind un grafic, scriind condiția teoremei în această formă.

Graficul va avea 6 vârfuri , fiecare pereche de vârfuri fiind conectată printr-o muchie . Un astfel de grafic se numește grafic complet (este imposibil să se deseneze noi muchii pentru el, deoarece toate conexiunile posibile au fost deja făcute). Un grafic complet cu vârfuri este notat cu .

În acest exemplu, puteți construi un grafic . Acest grafic are 15 muchii. 6 vârfuri reprezintă 6 persoane menționate în enunțul problemei.

În plus, pentru dovadă, este necesară colorarea marginilor. Marginea va fi colorată în roșu dacă cele două persoane nu se cunosc, sau albastră dacă se cunosc. Ținând cont de aceste transformări, enunțul teoremei poate fi reformulat:

Indiferent de colorarea marginilor, graficul va avea fie un triunghi roșu (un triunghi în care toate marginile sunt roșii) fie un triunghi albastru (în care toate marginile sunt albastre). Triunghiul roșu va însemna că 3 persoane sunt străini în perechi, iar triunghiul albastru va însemna că 3 persoane sunt familiare. Dacă această afirmație este într-adevăr adevărată, atunci afirmația originală va fi și adevărată.

Sfârșitul probei

În continuare, pentru demonstrație, se alege un vârf arbitrar P. Din vârf ies cinci muchii. Conform principiului Dirichlet , cel puțin trei margini ale aceleiași culori (dacă marginile uneia dintre culori sunt mai mici de 3, marginile celeilalte culori sunt mai mari de 3).

A , B , C - vârfuri, alte capete ale muchiilor menționate mai sus. Dacă cel puțin una dintre muchiile AC, BC, AB este albastră, atunci puteți obține un triunghi cu o singură culoare (folosind două muchii de la P și vârful tocmai menționat). Dacă niciuna dintre aceste margini nu este albastră, atunci toate sunt roșii și din ele puteți obține un triunghi roșu ABC etc.

Notele lui Ramsey

În 1930, în articolul „On a Problem in Formal Logic”, Ramsey a demonstrat o teoremă mai generală (cunoscută ca teorema Ramsey ), această teoremă este un caz special al acesteia. Teoria Ramsey , una dintre ramurile combinatoriei , se bazează pe teorema Ramsey .

Alte cazuri

Dacă firma nu are 6 persoane, ci doar 5, consecința menționată în problema Ramsey s-ar putea să nu fie realizată.

Pentru a arăta posibilitatea unui astfel de caz, este necesar să construim un contraexemplu . Un contraexemplu este un pentagon care înconjoară o stea cu cinci colțuri . Pentagonul trebuie să fie colorat în roșu, iar steaua albastră. Astfel, numărul minim de vârfuri pentru care proprietatea specificată în sarcină este adevărată este 6.

În teoria lui Ramsey, acest fapt este scris după cum urmează:

Literatură

Visvanatha Krishnamurthy. Cultura, entuziasmul și relevanța matematicii . — Wiley Eastern, 1990-01-01. — 348 p. — ISBN 9788122402728 .

Note

  1. ↑ Evgheni Vechtomov. Filosofia Matematicii ed. a II-a. Manual pentru studii universitare de licență și licență . Litri, 20-12-2018. — 318 p. — ISBN 9785041182014 .
  2. ↑ Novikov Fedor Alexandrovici. Matematică discretă: manual pentru licee. a 2-a ed. Standard de a treia generație . - Editura „Petru”, 10-09-2012. — 400 s. — ISBN 9785496000154 .
  3. ↑ Irina Leonidovna Babinskaya. Probleme ale olimpiadelor de matematică . - Nauka, 1975. - 120 p.
  4. ↑ Jukovski M.E., A.A. Glibichuk, A.M. Raygorodsky, Shkredov I.D., A.B. Dainyak, D.G. Ilyinsky, D.V. Musatov, A.V. Savvateev http://ru.discrete-mathematics.org/fall2017/magistracy_online_program.pdf Arhivat 5 februarie 2018 la Wayback Machine

Link -uri