[Kombinatoryka] wśród osób i miast

anorian · Post autor: **anorian** » 22 sty 2009, o 18:53

1.Dowieść, że wśród dowolnych 18 osób istnieją cztery, z których każde dwie się znają lub cztery, z których żadne dwie się nie znają.

2.W państwie znajduje się 66 miast, a przewozy między każdymi dwoma obsługuje jeden z czterech przewoźników. Udowodnić, że istnieją takie trzy miasta, że drogi między nimi są obsługiwane przez tego samego przewoźnika.

pawelsuz · Post autor: **pawelsuz** » 22 sty 2009, o 19:42

2) \(\displaystyle{ 4^{3}=64=66-2}\)
i z ZS widzimy teze:)

anorian · Post autor: **anorian** » 22 sty 2009, o 21:03

Mógłbyś przybliżyć?

Dumel · Post autor: **Dumel** » 22 sty 2009, o 21:32

to zadanie jest strasznie oklepane. wybieramy dowolne miasto. do pewnych 22 miast przewozy obsluguje pewien przewoźnik (A). rozwazamy jedno z tych 22 miast- jesli prowadzi z niego droga do jednego z pozostalych 21 miast to mamy teze, jesli nie, rozumujemy analogicznie jak poprzednio.

szablewskil · Post autor: **szablewskil** » 24 sty 2009, o 13:39

Dumel pisze:to zadanie jest strasznie oklepane. wybieramy dowolne miasto. do pewnych 22 miast przewozy obsluguje pewien przewoźnik (A).

Chyba sie Dumel pomyliles Powinno byc raczej do 17, a zadanie to faktycznie oklepane. Jest m.in w kolku pawlwoskiego i bylo na jakims om