Ramseyn ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. heinäkuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Ramseyn ongelma [1] [2] [3] , kuuden henkilön päivämääräongelma [4] on Ramseyn teorian matemaattinen lause , Ramseyn teoreeman erikoistapaus .

Lausunto

Olkoon juhlissa 6 henkilöä. Jos kaksi ihmistä ovat tavanneet toisensa vähintään kerran aiemmin, heitä kutsutaan tutuiksi, jos eivät - tuntemattomiksi. Ramseyn ongelman mukaan:

Missä tahansa kuuden hengen seurassa joko kolme henkilöä tuntee toisensa pareittain tai kolme henkilöä ei tunne toisiaan pareittain.

Ehdon muuntaminen kaavioksi

Todistus voidaan suorittaa käyttämällä graafia, kirjoittamalla lauseen ehto tähän muotoon.

Graafissa on 6 kärkeä , joista jokainen on yhdistetty reunalla . Tällaista graafia kutsutaan täydelliseksi graafiksi (sille on mahdotonta piirtää uusia reunoja, koska kaikki mahdolliset yhteydet on jo tehty). Täydellinen graafi, jossa on pisteitä, on merkitty .

Tässä esimerkissä voit rakentaa kaavion . Tässä kaaviossa on 15 reunaa. 6 kärkeä edustaa 6:ta ongelmalausekkeessa mainittua henkilöä.

Lisäksi todisteeksi on tarpeen värittää reunat. Reuna väritetään punaiseksi, jos kaksi ihmistä eivät tunne toisiaan, tai siniseksi, jos he tuntevat toisensa. Nämä muunnokset huomioon ottaen lauseen lause voidaan muotoilla uudelleen:

Reunojen värjäyksestä riippumatta kaaviossa on joko punainen kolmio (kolmio, jossa kaikki reunat ovat punaisia) tai sininen kolmio (jonka kaikki reunat ovat sinisiä). Punainen kolmio tarkoittaa, että 3 henkilöä on pareittain tuntemattomia, ja sininen kolmio tarkoittaa, että 3 henkilöä on pareittain tuttuja. Jos tämä väite on todella totta, niin alkuperäinen väite on myös totta.

Todistuksen loppu

Seuraavaksi todistukseksi valitaan mielivaltainen kärki P. Huipusta tulee viisi reunaa. Dirichlet-periaatteen mukaan vähintään kolme samanväristä reunaa (jos yhden värin reunat ovat alle 3, toisen värin reunat ovat enemmän kuin 3).

A , B , C - kärjet, edellä mainittujen reunojen muut päät. Jos ainakin yksi reunoista AC, BC, AB on sininen, saadaan yksivärinen kolmio (käyttäen kahta P:n ja juuri mainitun kärjen reunaa). Jos mikään näistä reunoista ei ole sininen, ne ovat kaikki punaisia, ja niistä saat punaisen kolmion ABC jne .

Ramseyn muistiinpanot

Vuonna 1930 artikkelissa "On a Problem in Formal Logic" Ramsey osoitti yleisemmän lauseen (tunnetaan nimellä Ramseyn teoreema ), tämä lause on sen erikoistapaus. Ramseyn teoria , yksi kombinatoriikan haaroista, perustuu Ramseyn lauseeseen .

Muut tapaukset

Jos yrityksessä ei ole 6 henkilöä, vaan vain 5, Ramseyn ongelmassa mainittua seurausta ei välttämättä toteuteta.

Sellaisen tapauksen mahdollisuuden osoittamiseksi on tarpeen rakentaa vastaesimerkki . Vastaesimerkki on viisikulmio , joka ympäröi viisisakaraista tähteä . Viisikulmion tulee olla punainen ja tähden sininen. Näin ollen minimimäärä pisteitä, joille tehtävässä määritetty ominaisuus on tosi, on 6.

Ramseyn teoriassa tämä tosiasia on kirjoitettu seuraavasti:

Kirjallisuus

Visvanatha Krishnamurthy. Matematiikan kulttuuri, jännitys ja relevanssi . - Wiley Eastern, 1.1.1990. — 348 s. — ISBN 9788122402728 .

Muistiinpanot

  1. ↑ Jevgeni Vectomov. Matematiikan filosofia, 2. painos. Oppikirja perustutkinto- ja jatko-opintoja varten . Litraa, 20.12.2018. — 318 s. — ISBN 9785041182014 .
  2. ↑ Novikov Fedor Aleksandrovich. Diskreetti matematiikka: oppikirja lukioille. 2. painos Kolmannen sukupolven standardi . - Kustantaja "Peter", 10.9.2012. - 400 s. — ISBN 9785496000154 .
  3. ↑ Irina Leonidovna Babinskaja. Matemaattisten olympialaisten tehtävät . - Nauka, 1975. - 120 s.
  4. ↑ Zhukovsky M.E., A.A. Glibichuk, A.M. Raygorodsky, Shkredov I.D., A.B. Dainyak, DG. Iljinski, D.V. Musatov, A.V. Savvateev http://ru.discrete-mathematics.org/fall2017/magistracy_online_program.pdf Arkistoitu 5. helmikuuta 2018 Wayback Machinessa

Linkit