[Kombinatoryka][MIX] Interesująca kombinatoryka

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[Kombinatoryka][MIX] Interesująca kombinatoryka

Post autor: Swistak »

Zebrałem trochę moim zdaniem bardzo fajnych kombi i zrobiłem z nich mixa. Starałem się je z grubsza ułożyć wg rosnącego stopnia trudności.
Btw zad. 5 już kiedyś wrzucałem, ale ładnie się tu wpasowuje

1. Dany jest graf bez wierzchołków izolowanych (czyli takich, z których nie wychodzi ani jedna krawędź). Udowodnij, że da się jego wierzchołki pomalować na czerwono i niebiesko, tak aby każdy czerwony wierzchołek sąsiadował z co najmniej jednym niebieskim, a każdy niebieski z co najmniej jednym czerwonym.
2. Dana jest grupa ludzi, w której każda osoba nie lubi co najwyżej trzech innych, przy czym jeżeli A nie lubi B, to B nie lubi A. Udowodnij, że da się tę grupę podzielić na takie 2, że żaden człowiek nie będzie nie lubić co najmniej 2 ludzi ze swojej grupy.
3. Dana jest tablica o n wierszach i kolumnach. W 2n polach umieszczono pionki. Udowodnij, że da się wybrać niepusty podzbiór pionków, taki że w każdym wierszu i kolumnie będzie wybrana parzysta liczba pionków.
4. Graf nazwijmy epickim jeżeli istnieje podział jego wierzchołków na grupy A i B takie, że A jest kliką, a B jest zbiorem niezależnym (kilka to taki graf, w którym każdy wierzchołek jest połączony z każdym, a zbiór niezależny to taki zbiór, w którym żadne 2 wierzchołki nie są połączone). Udowodnij, że znajomość stopni wierzchołków determinuje to, czy graf jest epicki, czy nie, czyli, że jeżeli ktoś ustali nam z góry stopnie i każe nam dorzucić krawędzie, tak aby z każdego wierzchołka wychodziła odpowiednia liczba krawędzi, to utworzony przez nas graf albo zawsze będzie epicki albo nigdy.
5. Na płaszczyźnie zaznaczono skończoną liczbę pewnych punktów kratowych (czyli takich, których obie współrzędne są całkowite). Udowodnij, że da się je pomalować na czerwono i niebiesko, tak aby dla każdej pionowej lub poziomej linii, aby moduł różnicy między liczbą czerwonych i niebieskich punktów wynosił co najwyżej 1.
6. Dany jest graf spójny o k krawędziach. Udowodnij, że da się jego krawędzie ponumerować liczbami ze zbioru {1, 2, …, k} (każda ma być użyta dokładnie raz), w taki sposób, aby dla każdego wierzchołka, którego stopień jest większy od 1, największy wspólny dzielnik liczb przyporządkowanych krawędziom z niego wychodzącym był równy 1.
7. Dana jest tablica o n wierszach i kolumnach, w której każdemu wierszowi i kolumnie przyporządkowano pewną liczbę całkowitą ze zbioru \(\displaystyle{ \{ 0, 1, …, n \}}\) przy czym suma liczba przyporządkowanych wierszom i kolumnom jest sobie równa. Udowodnij, że jeżeli nie istnieje taki zbiór \(\displaystyle{ k}\) kolumn i \(\displaystyle{ l}\) wierszy, że zachodzi \(\displaystyle{ S_{k}>S_{l}+(n-l)k}\), gdzie \(\displaystyle{ S_k}\) jest sumą liczbą przyporządkowanych tym kolumnom, a \(\displaystyle{ S_l}\) sumą liczb w wierszach, to wtedy istnieje takie pokolorowanie niektórych pól tablicy, że każda liczba w kolumnie i wierszu będzie mówić ile w tym rzędzie jest czarnych pól. A warunek prostszym językiem znaczy tyle, że nie znajdziemy takiego kawałka szachownicy, że patrząc na sumę liczb w odpowiednich kolumnach wynika, że powinno być w nim jakoś dużo czarnych pól, a patrząc na sumę liczb w odpowiednich wierszach wynika, że w tym kawałku powinno być jakoś mało czarnych pól.
8. Dany jest graf skierowany, w którym każdy wierzchołek ma stopień wyjściowy i wejściowy równy co najwyżej 2. Udowodnij, że liczba pokryć cyklowych tego grafu (czyli zbiorów krawędzi, które tworzą rozłączne wierzchołkowo cykle i każdy wierzchołek należy do dokładnie jednego cyklu) jest potęgą dwójki.
9. a) Dany jest graf G. Udowodnij, że da się go podzielić na takie 2 części, że każdy wierzchołek będzie miał w swoim podgrafie parzysty stopień.
b) Hard wersjon: Udowodnij, że liczba takich możliwych podziałów jest potęgą dwójki (można założyć prawdziwość podpunktu a) ).
Przy czym nie gwarantuję, że do b) istnieje kombinatoryczne rozwiązanie .
10. Krytycznymi wierzchołkami spójnego grafu nazwijmy te wierzchołki, po których usunięciu ich oraz krawędzi z nich wychodzących graf się rozspójnia. Dany jest spójny graf G, w którym nie ma żadnych krytycznych wierzchołków. Udowodnij, że da się pokolorować wierzchołki tego grafu na 3 kolory w taki sposób, że jeżeli wyrzucimy krawędzie łączące wierzchołki tego samego koloru, to G pozostanie spójny i ciągle nie będzie miał krytycznych wierzchołków.
11. Alicja i Bob grają w grę, w której mają dane 3 kupki, w których jest kolejno \(\displaystyle{ a, b, c}\) kamieni, przy czym \(\displaystyle{ a, b, c}\) są całkowitymi dodatnimi parami różnymi liczbami. Ruch polega na wskazaniu kupki i zabraniu z niej dodatniej liczby kamieni, ale przy zachowaniu własności, że żadne 2 kupki nie mają tej samej dodatniej liczby kamieni. Grę wygrywa ten, kto zabierze ostatni kamień. Alicja zaczyna. Udowodnij, że Bob ma strategię wygrywającą wtedy i tylko wtedy, gdy \(\displaystyle{ (a+1) \oplus (b+1) \oplus (c+1)=0}\), gdzie \(\displaystyle{ \oplus}\) jest operatorem działania XOR.
Ostatnio zmieniony 12 gru 2011, o 19:27 przez Swistak, łącznie zmieniany 1 raz.
KPR
Użytkownik
Użytkownik
Posty: 254
Rejestracja: 11 lip 2009, o 20:00
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 31 razy

[MIX] Interesująca kombinatoryka

Post autor: KPR »

A jak w zadaniu piątym obu kolorów jest nieskończenie wiele, to jaka jest różnica?-- 12 gru 2011, o 19:01 --1:
Ukryta treść:    
Awatar użytkownika
BSP
Użytkownik
Użytkownik
Posty: 69
Rejestracja: 2 gru 2008, o 11:45
Płeć: Mężczyzna
Lokalizacja: W pewnym otoczeniu nieskończoności (Wrocław)
Podziękował: 11 razy
Pomógł: 6 razy

[MIX] Interesująca kombinatoryka

Post autor: BSP »

Odp na Zadanie 3

3. Dana jest tablica o n wierszach i kolumnach. W 2n polach umieszczono pionki. Udowodnij, że da się wybrać niepusty podzbiór pionków, taki że w każdym wierszu i kolumnie będzie wybrana parzysta liczba pionków.
Ukryta treść:    
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[MIX] Interesująca kombinatoryka

Post autor: Swistak »

Istotnie kolega BSP nie zrozumiał treści zadania 3. Niepusty podzbiór pionków ma ZOSTAĆ na szachownicy, a nie być zdjęty .
A rozwiązanie zad. 1 oczywiście poprawne.
Awatar użytkownika
BSP
Użytkownik
Użytkownik
Posty: 69
Rejestracja: 2 gru 2008, o 11:45
Płeć: Mężczyzna
Lokalizacja: W pewnym otoczeniu nieskończoności (Wrocław)
Podziękował: 11 razy
Pomógł: 6 razy

[MIX] Interesująca kombinatoryka

Post autor: BSP »

Przepraszam, myślałem że wybrać, w sensie zabrać
Aczkolwiek to co napisałem wyżej można w praktycznie taki sam sposób użyć w drugą stronę, czyli że
Ukryta treść:    
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[MIX] Interesująca kombinatoryka

Post autor: Swistak »

Zastanów się raz jeszcze
Panda
Użytkownik
Użytkownik
Posty: 342
Rejestracja: 31 maja 2008, o 19:44
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 26 razy
Pomógł: 28 razy

[MIX] Interesująca kombinatoryka

Post autor: Panda »

2.
Ukryta treść:    
-- 15 grudnia 2011, 21:46 --

3.
Ukryta treść:    
-- 15 grudnia 2011, 21:55 --4...
Ukryta treść:    
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[MIX] Interesująca kombinatoryka

Post autor: Swistak »

Czwarte Pandy to tak niesamowity blef, że aż boli . Wierzchołki z kliki mogą się bez problemu łączyć z tymi ze zbioru niezależnego.
Panda
Użytkownik
Użytkownik
Posty: 342
Rejestracja: 31 maja 2008, o 19:44
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 26 razy
Pomógł: 28 razy

[Kombinatoryka][MIX] Interesująca kombinatoryka

Post autor: Panda »

Stare Dziwne, że nikt nie zareagował.

Poprawne:
4:    
Lepiej:
3:    
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

[Kombinatoryka][MIX] Interesująca kombinatoryka

Post autor: Mruczek »

3 to prostsze 51-3-5 OM.

6 to IMO 1991, nr 4.

9a to Mszana 2011, drużynowe zad. 4.
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[Kombinatoryka][MIX] Interesująca kombinatoryka

Post autor: Swistak »

Wiem . Żadne z tych zadań nie jest moim oryginalnym, chciałem po prostu pozbierać ciekawe kombinatoryczne zadania z różnych źródeł .
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

[Kombinatoryka][MIX] Interesująca kombinatoryka

Post autor: Mruczek »

Tak, tak, a mógłbyś podać źródła pozostałych nierozwiązanych jeszcze zadań o ile je pamiętasz i źródła te są w internecie? (minęło już 4.5 roku od utworzenia wątku xD)
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[Kombinatoryka][MIX] Interesująca kombinatoryka

Post autor: Swistak »

1. Gildie XVII OI I etap
2. Powszechny folklor m.in. złote rybki Kurlandczyka
3. Finał OMa w stylu LI, można zakodzić tutaj:
4. Konspiracja XVIII OI I etap
5. Któreśtam IMO (rzędu okolice 1986?) zad.6, można zakodzić tutaj:
6. Któreśtam inne IMO (trochę późniejsze, ale nie pamiętam dokładnie, można zakodzić tutaj: http://ki.staszic.waw.pl/task.php?name=aragorn
7. ONTAK 2011, wariacja na podstawie zadania: http://main.edu.pl/en/archive/ontak/2011/zag -
8. PA 2002 http://main.edu.pl/en/user.phtml?op=sho ... con=PA2002
9. XII OI http://main.edu.pl/pl/archive/oi/12/dwa . Mając cześć a), część b) można robić opierając się na algebraicznej intepretacji, o której można przeczytać tutaj: http://www.deltami.edu.pl/temat/informa ... przyjecia/ (Szreder znał takie rozwiązanie, bo je wymyśliłem w trakcie jego kółka xD)
10. + 11. ja je znam z WICa 2011 (którego nie ma w necie), ale oryginalnie pochodzą z jakichś ruskich contestów.
Rozw 11. można przeczytać o tutaj: http://www.deltami.edu.pl/temat/matemat ... h_stosach/

Jak widać, forma w której przedstawiłem każde z zadań jest czysto matematyczna, ale każde z nich albo oryginalnie pochodzi z algorytmicznego contestu albo ma swój algorytmiczny odpowiednik wzorowany na matematycznym oryginale . Nie jest to przypadek. Była to częsć mojego chytrego planu, aby przekonać Anię Siennicką do tego, że zadania informatyczne też są fajne xD. Dałem jej zadania stąd, stwierdziła, że fajne, a potem bum, uświadomiłem ją, że tak naprawdę to zadania algorytmiczne (aczkolwiek wielkich skutków w przyszłości to nie miało ). Ale mam nadzieję, że zapostowaniem fajnego mixu użytkownikom forum też się przysłużyłem xD.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

[Kombinatoryka][MIX] Interesująca kombinatoryka

Post autor: Mruczek »

Dzięki!!
ODPOWIEDZ