szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 lis 2016, o 14:56 
Użytkownik

Posty: 7
Lokalizacja: Tuitam
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!.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 24 lis 2016, o 15:39 
Użytkownik
Avatar użytkownika

Posty: 6120
2)
Dwójek jest więcej niż piątek więc na największą potęgę 10^n wpływa ilość piątek w iloczynie 1000!
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 : 10,10^2,10^3,....,10^{249}
Góra
Mężczyzna Offline
PostNapisane: 24 lis 2016, o 17:58 
Użytkownik

Posty: 7
Lokalizacja: Tuitam
kerajs napisał(a):
2)

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
Góra
Mężczyzna Offline
PostNapisane: 24 lis 2016, o 19:16 
Użytkownik
Avatar użytkownika

Posty: 3228
Lokalizacja: blisko
Co do pierwszego to zróbmy to tak:

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 \left\{ 1\right\}

Ten wierzchołek jest incydentny z 65 wierzchołkami grafu V i teraz z zasady szufladkowej wynika że z wierzchołkiem \left\{ 1\right\} jest połączonych minimum 17 wierzchołków o tym samym kolorze - c krawędzi. Niech te wierzchołki należą do zbioru \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 \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 \left\{ 17\right\} ale już przy trójkolorowym malowaniu.

Rozumowanie powtórzmy:

w grafie \left\{ 17\right\} wybieramy punkt 1' i mamy z nim incydentnych 16 innych wierzchołków, przy czym z zasady szufladkowej Dirichleta mamy że musi istnieć minimum 6 wierzchołków połączonych z wierzchołkiem 1' za pomocą koloru np d
jeśli teraz w zbiorze \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 1'', który jest incydentny z pięcioma innymi wierzchołkami, z zasady szufladkowej mamy, że wierzchołek 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 \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 .
Góra
Mężczyzna Offline
PostNapisane: 24 lis 2016, o 20:27 
Użytkownik

Posty: 7
Lokalizacja: Tuitam
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?
Góra
Mężczyzna Offline
PostNapisane: 25 lis 2016, o 00:55 
Użytkownik
Avatar użytkownika

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

https://pl.wikipedia.org/wiki/Silnia
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zasada szufladkowa - n+1 liczb niewiększych od 2n.  bananajoe  2
 Zasada szufladkowa - zadanie 17  Olka97  1
 Zasada szufladkowa i geometria  edzioedzio55  4
 Permutacje, kombinacje?  kzn1990  5
 kombinacje a wariacje?  johny_wav  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl