Barion Pixel Az indirekt bizonyítás | mateking
 

Hogyan működik az indirekt bizonyítás? Milyen esetekben érdemes használni? Skatulya elv és az indirekt bizonyítás. Indirekt bizonyítással megoldható feladatok.

A képsor tartalma

Ha van öt darab labda és négy doboz…

Akkor a labdákat nem tudjuk úgy betenni a dobozokba, hogy mindegyikben csak egy labda legyen.

Valamelyik dobozban biztosan legalább két labda lesz.

Röviden összefoglalva erről szól a skatulya-elv.

Most pedig lássuk, mi ez az indirekt bizonyítás.

Egy 5 kocsiból álló vonaton 460-an utaznak. Bizonyítsuk be, hogy van olyan kocsi, amiben legalább 80 utas van.

Az indirekt bizonyítás lényege, hogy elképzeljük, mi történne, hogyha az állítás nem lenne igaz.

Vagyis tegyük föl, hogy mindegyik kocsiban 80-nál kevesebb utas van.

Ha minden kocsiban 80-nál kevesebb utas van, akkor lássuk csak, tehát az egész vonaton 400-nál kevesebben lennének.

De ez lehetetlen, hiszen a vonaton 460-an vannak.

Vagyis lennie kell olyan kocsinak, ahol legalább 80-an vannak.

Egy másik vonat szintén öt kocsiból áll. Legalább hányan utaznak a vonaton, ha tudjuk, hogy biztosan van olyan kocsi, amiben legalább 40-en utaznak?

Hát, ez is valami skatulya-elvnek tűnik…

Csak most valahogy fordítva.

Hogyha mondjuk 100-an utaznak a vonaton, az valószínű kevés, mert simán lehet kocsinként 20 ember.

A 200 már határozottan biztatóbb.

Ha 200-an utaznak a vonaton, akkor biztosan van olyan kocsi, amiben legalább 40-en vannak.

Mert ha nem lenne, tehát minden kocsiban 40-nél kevesebben lennének, akkor az egész vonaton is 200-nál kevesebben lennének.

A 200 utas tehát már elég.

De a kérdés úgy szólt, hogy legalább hányan utaznak a vonaton, és előfordulhat, hogy már 200-nál kevesebb utas is jó lehet.

Ha 195-en utaznak a vonaton, akkor még előfordulhat, hogy minden kocsiban csak 39-en vannak.

De ha 196-an…

Akkor már kell lennie olyan kocsinak, amiben legalább 40-en vannak.

Hiszen, ha minden kocsiba csak 39-en lennének, akkor az egész vonaton is csak 195-en.

Tehát a válasz…

A vonaton legalább 196-an kell, hogy utazzanak.

Az egyik kocsiban egy 10 tagú társaság utazik. Mindenki a társaságból legalább 7 másik embert ismer. Bizonyítsuk be, hogy bármely 3 embernek van közös ismerőse.

Na, ez már egy izgalmasabb ügy.

Megint indirekten bizonyítunk, vagyis tegyük föl, hogy van 3 olyan ember, akiknek nincs közös ismerőse.

Hát, ha nincs közös ismerős, akkor itt bizony csak két ismertség lehet…

Sőt az is lehet, hogy kevesebb…

De az biztos, hogy legfeljebb kettő.

És itt is legfeljebb kettő…

Meg mindenhol.

Ebből a 7 emberből így legfeljebb 14 ismertség indulhat ki.

Mivel a társaságban mindenki legalább 7 másik embert ismer, hogyha embereink egymást ismerik...

akkor is még fejenként legalább 5 ismerősre van szükségük.

Így aztán legalább 15 ismertség indul ki innen.

Ez lehetetlen, mert azok ott heten legfeljebb 14 ismertséggel rendelkeznek.

Tehát ellentmondásra jutottunk.

Nem fordulhat elő, hogy van 3 ember, akinek nincs közös ismerőse.

Vagyis bármely 3 embernek van közös ismerőse.

Most, hogy ezt is megtudtuk, már csak egyetlen nyugtalanító kérdésre keressük a választ.

Arra, hogy mégis mit keres itt ez a rengeteg darázs?

Nem, valójában mégsem ez a kérdés…

Ez túlzottan életszerű lenne.

A kérdés úgy szól, hogy van itt ez a 7x7-es sakktábla és mindegyik mezőn egy darázs.

Egy adott pillanatban minden darázs átmászik valamelyik szomszédos mezőre.

A sarkuknál találkozó mezők nem számítanak szomszédosnak.

Lehetséges-e, hogy ekkor megint mindegyik mezőn pontosan egy darázs álljon?

Tegyük fel, hogy ez lehetséges.

Ez azt jelenti, hogy minden fekete mezőn álló darázsnak át kell másznia egy szomszédos fehér mezőre.

Fekete mezőből 25 darab van, fehérből meg csak 24 darab.

Nem tud a 25 darab fekete mezőn álló darázs átmászni a 24 fehér mezőre, csak úgy, ha lesz olyan mező, amin több darázs is van.

A nagy darázscserélő akció tehát lehetetlen.

BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez