Znaleziono 1110 wyników

autor: Mruczek
3 mar 2018, o 19:13
Forum: Kombinatoryka i matematyka dyskretna
Temat: Teoria grafów
Odpowiedzi: 3
Odsłony: 334

Re: Teoria grafów

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...
autor: Mruczek
12 lut 2018, o 20:05
Forum: Kółko matematyczne
Temat: [MIX] Zadania z OMJ(G) (Zawody, Obozy)
Odpowiedzi: 14
Odsłony: 1578

Re: [MIX] Zadania z OMJ(G) (Zawody, Obozy)

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...
autor: Mruczek
10 lut 2018, o 20:45
Forum: Polska Olimpiada Matematyczna
Temat: LXIX OM
Odpowiedzi: 165
Odsłony: 37459

LXIX OM

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...
autor: Mruczek
24 sty 2018, o 18:56
Forum: Kombinatoryka i matematyka dyskretna
Temat: Zasada szufladkowa Dirichleta?
Odpowiedzi: 1
Odsłony: 192

Re: Zasada szufladkowa Dirichleta?

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ę.
autor: Mruczek
24 sty 2018, o 18:51
Forum: Kombinatoryka i matematyka dyskretna
Temat: Ścieżka hamiltona w grafie
Odpowiedzi: 1
Odsłony: 193

Re: Ścieżka hamiltona w grafie

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.
autor: Mruczek
21 sty 2018, o 22:25
Forum: Polska Olimpiada Matematyczna
Temat: Geometria i kombinatoryka pod OMJ i OM
Odpowiedzi: 5
Odsłony: 1271

Re: Geometria i kombinatoryka pod OMJ i OM

Wpisz sobie w Google: "combinatorics olympiad pdf" lub "combinatorics imo training" to na pewno coś znajdziesz np. to http://math.sun.ac.za/~swagner/Combinatorics.pdf 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 foru...
autor: Mruczek
19 sty 2018, o 21:11
Forum: Kombinatoryka i matematyka dyskretna
Temat: Szachwonica 8x*
Odpowiedzi: 1
Odsłony: 219

Re: Szachwonica 8x*

To zadanie z 41 OM - I - 4: http://archom.ptm.org.pl/?q=node/654 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, łączym...
autor: Mruczek
19 sty 2018, o 20:54
Forum: Kombinatoryka i matematyka dyskretna
Temat: Teoria grafów, ilość krawędzi
Odpowiedzi: 1
Odsłony: 186

Re: Teoria grafów, ilość krawędzi

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...
autor: Mruczek
13 sty 2018, o 21:43
Forum: Kółko matematyczne
Temat: [Równania][Ciągi] Pawłowski/Tomalczyk, Zestaw I, Zad 3
Odpowiedzi: 5
Odsłony: 902

Re: [Równania][Ciągi] Pawłowski/Tomalczyk, Zestaw I, Zad 3

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ń z tych pi...
autor: Mruczek
13 sty 2018, o 02:24
Forum: Kombinatoryka i matematyka dyskretna
Temat: Ciekawe zadania z kombinatoryki?
Odpowiedzi: 4
Odsłony: 332

Re: Ciekawe zadania z kombinatoryki?

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:
https://artofproblemsolving.com/communi ... 47p2617494
http://rmms.lbi.ro/rmm2012/index.php?id=solutions_math
autor: Mruczek
27 lis 2017, o 21:24
Forum: Kółko matematyczne
Temat: [MIX] Mix bez nazwy
Odpowiedzi: 23
Odsłony: 2691

Re: [MIX] Mix bez nazwy

23:    
autor: Mruczek
20 lis 2017, o 19:33
Forum: Kombinatoryka i matematyka dyskretna
Temat: Algorytm przeszukiwania w głab (DFS)
Odpowiedzi: 1
Odsłony: 228

Re: Algorytm przeszukiwania w głab (DFS)

Jest źle.
W pierwszym kroku wrzuciłeś na stos i, h, g, e, b, potem ściągnąłeś z niego b i zgubiłeś pozostałe elementy znajdujące się na stosie. W drugim wierszu stos powinien wyglądać tak: i, h, g, e, f, e, c.
autor: Mruczek
1 lis 2017, o 01:45
Forum: Polska Olimpiada Matematyczna
Temat: LXIX OM
Odpowiedzi: 165
Odsłony: 37459

LXIX OM

W mojej ocenie obie metody są równoprawne. Gdyby nie były, autorzy w rozwiązaniu wzorcowym nie wspominaliby o tym, że rozwiązywanie takich rekurencji było w jakimś dodatku do którejś z broszurek. Z OMem to tak jest, że jak raz w historii OMa coś było gdzieś na którejś olimpiadzie / Zwardoniach / dod...