Matematyka.pl

1. Przez liść będę rozumiał wierzchołek stopnia co najwyżej jeden. W przypadku, gdy drzewo składa się z tylko jednego wierzchołka przyjmujemy, że ten wierzchołek jest liściem. Dalej załóżmy, że drzewo składa się z min. 2 wierzchołków, z tego wynika, że każdy wierzchołek ma stopień przynajmniej 1 (ab...

Trzeba pokazać, że istnieje taki zbiór D , wskazać go, może być to dowolny zbiór. Popatrz na drzewo rozpinające tego spójnego grafu. Spróbuj podzielić zbiór wierzchołków tego drzewa na takie dwa zbiory o jakie chodzi w zadaniu. Ustal korzeń tego drzewa. Popatrz na zbiory wierzchołków w ustalonej odl...

Masz poprawne obserwacje. Weź cykl składający się z 5 wierzchołków. Nie zawiera on trójkątów (oczywiste). Nie zawiera też zbioru niezależnego składającego się z 3 wierzchołków. Można to pokazać rozpatrując wszystkie przypadki, albo w ten sposób: Przypuśćmy, nie wprost, że zawiera taki zbiór niezależ...

Nie masz racji. Podałem kontrprzykład, więc twierdzenie jest fałszywe.

Powyższe twierdzenie jest fałszywe. Weźmy np. graf gwiazdę, czyli drzewo, które ma jeden wierzchołek w korzeniu i jest połączone z 10 wierzchołkami. Maksymalny zbiór niezależny to zbiór liści tego drzewa, ma wielkość 10 . Jest on też zbiorem dominującym, ale nie minimalnym, bo minimalny zbiór dominu...

Załóżmy, że nie musi istnieć taka trójka osób, to znaczy każda reszta występuje co najwyżej 2 razy. Wszystkich reszt z dzielenia przez 101 jest 101 , a wszystkich osób 202 , więc wtedy każda reszta występuje dokładnie 2 razy. Pokażemy, że istnieje graf, w którym każda reszta jest przypisana dokładn...

To ja przedstawię algorytmiczne rozwiązanie zad. 2 (bo to zadanie to chyba była taka kombinatoryczna teoria liczb, nie?) Mamy n = 8k + 4 = 2^2(2k + 1) czyli n ma w rozkładzie na czynniki pierwsze liczbę 2 w potędze 2 , a pozostałe czynniki są nieparzyste. Z każdym nieparzystym dzielnikiem d liczby n...

Oblicz ile jest podzbiorów \(\displaystyle{ 4}\)-elementowych zbioru \(\displaystyle{ 9}\) -elementowego (koraliki).
Oszacuj jaka może być maksymalna suma elementów takiego \(\displaystyle{ 4}\)-elementowego podzbioru (szufladki).
Wywnioskuj z ZSD, że pewne dwa podzbiory muszą mieć tą samą sumę.

Dla \(\displaystyle{ n = 2}\) mamy minimalny stopień \(\displaystyle{ \delta(G) \ge \frac{2}{2} - 1 = 0}\). Bierzemy dwa wierzchołki izolowane, ten graf nie ma ścieżki Hamiltona.

Wpisz sobie w Google: "combinatorics olympiad pdf" lub "combinatorics imo training" to na pewno coś znajdziesz np. to Poza tym ze 160 zadań jest w archiwum OM, pewnie z kilkanaście tysięcy na AoPSie, są też w Delcie, Zwardoniach i na kółku na tym forum. Zobacz też tutaj: https://...

To zadanie z 41 OM - I - 4: Ponadto to zadanie było też na II etapie II Olimpiady Informatycznej - zadanie Szachownica (tam usuwano trzy pola). W skrócie rozwiązanie z OI polega na przerobieniu szachownicy na graf w standardowy sposób (pola to wierzchołki, łączymy krawędziami pola sąsiadujące jednym...

Pokażę algorytm konstruujący ten graf: Startujemy z grafu o 23 wierzchołkach bez krawędzi. Powtarzamy następujący krok 19 razy: Bierzemy dowolne 5 wierzchołków. Między nimi nie ma krawędzi, to znaczy że musi być przynajmniej jedna krawędź między tymi wierzchołkami, przyjmujemy, że w G te dwa wierzch...

To zadanie już kiedyś było: https://www.matematyka.pl/417880.htm?hilit=%20stirlinga

Można to zrobić inaczej bez zgadywania tych wzorków. To zadanie jest w książce KMDO p. Pawłowskiego, w rozdziale "Wzory Viete'a". Tak więc trzeba zrobić jakiś wielomian, którego pierwiastkami będą liczby x, y, z - dlatego ten wielomian musi mieć stopień 3 . Potem trzeba ułożyć układ równań...

Sporo jest tego na kółku na tym forum, w archiwum OM, a w szczególności na AoPSie.

Tutaj masz fajne zadanko z grafów - zad. 1 z RMMS 2012: