Ramsey problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 juli 2021; kontroller kräver 2 redigeringar .

Ramsey-problemet [1] [2] [3] , sex-personers dateringsproblem [4] är en matematisk sats i Ramsey-teorem , ett specialfall av Ramsey-satsen .

Uttalande

Låt det vara 6 personer på festen. Om två personer har träffat varandra minst en gång tidigare, kallas de bekanta, om inte - obekanta. Enligt Ramsey-problemet:

I alla sällskap med sex personer känner antingen tre personer varandra i par, eller så känner tre personer inte varandra i par.

Konvertera ett villkor till en graf

Beviset kan utföras med hjälp av en graf som skriver tillståndet för satsen i denna form.

Grafen kommer att ha 6 hörn , varje par hörn är förbundna med en kant . En sådan graf kallas en komplett graf (det är omöjligt att rita nya kanter för det, eftersom alla möjliga anslutningar redan har gjorts). En komplett graf med hörn betecknas med .

I det här exemplet kan du bygga en graf . Denna graf har 15 kanter. 6 hörn representerar 6 personer som nämns i problemformuleringen.

Vidare, för beviset, är det nödvändigt att färga kanterna. Kanten kommer att färgas röd om de två personerna inte känner varandra, eller blå om de känner varandra. Med hänsyn till dessa transformationer kan satsens uttalande omformuleras:

Oavsett färgen på kanterna kommer grafen antingen ha en röd triangel (en triangel där alla kanter är röda) eller en blå triangel (där alla kanter är blå). Den röda triangeln kommer att betyda att 3 personer är parvis främlingar, och den blå triangeln kommer att betyda att 3 personer är parvis bekanta. Om detta påstående verkligen är sant, kommer det ursprungliga påståendet också att vara sant.

Slutet på beviset

Därefter, för beviset, väljs ett godtyckligt vertex P. Fem kanter kommer fram från vertexet. Enligt Dirichlet-principen , minst tre kanter av samma färg (om kanterna på en av färgerna är mindre än 3 är kanterna på den andra färgen fler än 3).

A , B , C - hörn, andra ändar av kanterna som nämns ovan. Om åtminstone en av kanterna AC, BC, AB är blå, så kan du få en enfärgad triangel (med två kanter från P och det nyss nämnda hörnet). Om ingen av dessa kanter är blå, är de alla röda, och från dem kan du få en röd triangel ABC , etc.

Ramseys anteckningar

År 1930, i artikeln "On a Problem in Formal Logic", bevisade Ramsey en mer allmän sats (känd som Ramsey-satsen ), denna sats är ett specialfall av det. Ramsey- teorin , en av kombinatorikens grenar , bygger på Ramsey-teoremet .

Andra fall

Om företaget inte har 6 personer, utan endast 5, får den konsekvens som nämns i Ramsey-problemet inte genomföras.

För att visa möjligheten av ett sådant fall är det nödvändigt att konstruera ett motexempel . Ett motexempel är en femhörning som omger en femuddig stjärna . Pentagonen ska vara röd och stjärnan blå. Således är det minsta antalet hörn för vilka egenskapen som anges i uppgiften är sann 6.

I Ramseys teori är detta faktum skrivet på följande sätt:

Litteratur

Visvanatha Krishnamurthy. Matematiks kultur, spänning och relevans . — Wiley Eastern, 1990-01-01. — 348 sid. — ISBN 9788122402728 .

Anteckningar

  1. ↑ Evgeny Vechtomov. Mathematics Philosophy 2nd ed. Lärobok för grund- och forskarstudier . Liter, 2018-12-20. — 318 sid. — ISBN 9785041182014 .
  2. ↑ Novikov Fedor Alexandrovich. Diskret matematik: Lärobok för gymnasieskolor. 2:a uppl. Tredje generationens standard . - Förlaget "Peter", 2012-09-10. — 400 s. — ISBN 9785496000154 .
  3. ↑ Irina Leonidovna Babinskaya. Problem med matematiska olympiader . - Nauka, 1975. - 120 sid.
  4. ↑ Zjukovsky 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 Arkiverad 5 februari 2018 på Wayback Machine

Länkar