Zasada szufladkowa Dirichleta i kombinacje

[antek_k]

Witam, proszę o pomoc w rozwiązaniu dwóch zadań:

1) W pewnym regionie jest 66 miast. Każde dwa połączone są jednym z czterech środków komunikacji (kolej,autobus,statek,samolot). Wykaż że istnieją takie trzy miasta, że można odbyć podróż pomiędzy nimi po trójkącie używając tylko jednego środka komunikacji.

2)Ile jest różnych całkowitoliczbowych dodatnich potęg liczby 10 dzielących 1000!.

[kerajs]

2)
Dwójek jest więcej niż piątek więc na największą potęgę \(\displaystyle{ 10^n}\) wpływa ilość piątek w iloczynie \(\displaystyle{ 1000!}\)
\(\displaystyle{ n=\left[ \frac{1000}{5} \right]+ \left[ \frac{1000}{25} \right]+\left[ \frac{1000}{125} \right]+ \left[ \frac{1000}{625} \right]=200+40+8+1=249}\)
i tyleż jest potęg liczby 10 : \(\displaystyle{ 10,10^2,10^3,....,10^{249}}\)

[antek_k]

2)

\(\displaystyle{ n=\left[ \frac{1000}{5} \right]+ \left[ \frac{1000}{25} \right]+\left[ \frac{1000}{125} \right]+ \left[ \frac{1000}{625} \right]=200+40+8+1=249}\)

a nie jest tak że teraz policzyliśmy tylko te piątki które budują liczbę 1000? a co z pozostałymi liczbami z 1000! 995? ...900? itd

[arek1357]

Co do pierwszego to zróbmy to tak:

\(\displaystyle{ 66}\) miast i połączenia między nimi wyobraź sobie jako graf pełny V, którego krawędzie są pokolorowane czterema kolorami. Należy udowodnić, że istnieje klika monochromatyczna (jednokolorowa) trójkątna.

Wybierzmy jeden wierzchołek \(\displaystyle{ \left\{ 1\right\}}\)

Ten wierzchołek jest incydentny z 65 wierzchołkami grafu \(\displaystyle{ V}\) i teraz z zasady szufladkowej wynika że z wierzchołkiem \(\displaystyle{ \left\{ 1\right\}}\) jest połączonych minimum \(\displaystyle{ 17}\) wierzchołków o tym samym kolorze - c krawędzi. Niech te wierzchołki należą do zbioru \(\displaystyle{ \left\{ 17\right\}}\) wierzchołków.
jeśli jest choć jedna krawędź o tym samym kolorze c to te trzy wierzchołki tworzą trójkąt monochromatyczny o kolorze c. I zadanie rozwiązane.

Ale może się zdarzyć, że wszystkie wierzchołki ze zbioru \(\displaystyle{ \left\{ 17\right\}}\) są połączone jednym z pozostałych trzech kolorów, czyli sytuacja się powtarza i szukamy kliki monochromatycznej w grafie pełnym \(\displaystyle{ \left\{ 17\right\}}\) ale już przy trójkolorowym malowaniu.

Rozumowanie powtórzmy:

w grafie \(\displaystyle{ \left\{ 17\right\}}\) wybieramy punkt \(\displaystyle{ 1'}\) i mamy z nim incydentnych 16 innych wierzchołków, przy czym z zasady szufladkowej Dirichleta mamy że musi istnieć minimum \(\displaystyle{ 6}\) wierzchołków połączonych z wierzchołkiem \(\displaystyle{ 1'}\) za pomocą koloru np d
jeśli teraz w zbiorze \(\displaystyle{ \left\{ 6\right\}}\) istnieje choć jeden odcinek o kolorze d to sprawa załatwiona.

Ale jeśli nie ma takiego odcinka to rozumowanie zawężamy do grafu pełnego o sześciu wierzchołkach ale malowanego już dwoma kolorami.

I rozumowanie powtórzmy:
w grafie 6-elementowym wybierzmy wierzchołek \(\displaystyle{ 1''}\), który jest incydentny z pięcioma innymi wierzchołkami, z zasady szufladkowej mamy, że wierzchołek \(\displaystyle{ 1''}\) jest połączony
z trzema wierzchołkami o tym samym kolorze krawędzi e. Jeśli teraz dwa wierzchołki w zbiorze
wierzchołków \(\displaystyle{ \left\{ 3\right\}}\) jest połączone tym samym kolorem to zadanie rozwiązane, ale jeśli
są połączone innym kolorem to niestety został tylko jeden kolor, którym są połączone trzy punkty, które tworzą trójkąt monochromatyczny czyli jednokolorowy.

Uff przy grafach więcej się pisze niż liczy dlatego nie przepadam, ale rozumowanie indukcyjne całkiem poprawne.

Zresztą wiadomo, że w dwukolorowym kolorowaniu grafu pełnego o sześciu wierzchołkach istnieje trójkąt jednokolorowy a w grafie o pięciu wierzchołkach już być tak nie musi.
Wszystko to zalatuje liczbami Ramseya.

To tyle w tym temacie. A co do pierwszego to się nie bój bo masz tam wyliczone wszystkie piątki .

[antek_k]

Dziękuję serdecznie!
Oczywiście wierzę że rozwiązanie z piątkami jest poprawne,ale mógłbym jeszcze prosić o wytłumaczenie dlaczego tak jest?

[arek1357]

Tam na końcu jest to wytłumaczone bo jest taki fajny wzór, który wymyślili mądrzejsi ode mnie:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Silnia