[Kombinatoryka] Ciekawa kombinatoryka

[limes123]

Kilka ciekawszych zadań z kombi, z którymi mam problem:
1. Dwudziestu pięciu hobbitów podzieliło działkę 5x5 na działki 1x1. Zaden hobbit nie chce miec wroga za sasiada (ani nawet zeby jego dzialka stykala sie wierzcholkami z sasiadem). Wiadomo ze zaden nie poklocil sie z wiecej niz trzema innymi hobbitami. Udowodnic, ze mozna ich tak rozstawic, zeby kazdy byl otoczony tylko przyjaciolmi. (wsk. -> udowodnic, ze jedli sasiaduja ze soba jacys wrogowie to mozna zminiejszyc liczbe takich sasiadow)
2. M jest zbiorem 21 pkt na okregu. Udowodnic, ze sposrod katow srodkowych o koncach w punktach zbioru M mozna wybrac nie mniej niz 100 takich, ze katy srodkowe na nich oparte nie przekraczaja 120 stopni (wsk. -> z Dirichleta udowodnic, ze istnieje pkt, ktory z 13 innymi tworzy katy nie wieksze niz 120)
3. Sto liczb, wsrod ktorych sa zrowno dodatnie jak i ujemne, wypisano w jednym wierszu. Pokreslamy najpierw liczby dodatnie, pozniej liczby ktorych suma z nastepna jest dodatnia, oraz liczby, ktorych suma z nastepnymi dwiema jest dodatnia. Czy suma liczb podkreslonych moze byc ujemna lub rowna 0? (wsk. -> dla kazdej liczby podkreslonej rozwazyc najmniejszy zbior 0,1 lub 2 elementonwy taki, ze suma podkreslonej liczby i liczb tego zbioru jest dodatnia, pozniej odrzucamy kolejne takie zbiory).
Z góry dzięki za pomoc

[adamadam]

3. Sto liczb, wsrod ktorych sa zrowno dodatnie jak i ujemne, wypisano w jednym wierszu. Pokreslamy najpierw liczby dodatnie, pozniej liczby ktorych suma z nastepna jest dodatnia, oraz liczby, ktorych suma z nastepnymi dwiema jest dodatnia. Czy suma liczb podkreslonych moze byc ujemna lub rowna 0? (wsk. -> dla kazdej liczby podkreslonej rozwazyc najmniejszy zbior 0,1 lub 2 elementonwy taki, ze suma podkreslonej liczby i liczb tego zbioru jest dodatnia, pozniej odrzucamy kolejne takie zbiory).
Z góry dzięki za pomoc

Przy pierwszej "rudzie" podkreślania podkreśliliśmy wszystkie dodatnie. Suma podkreślonych liczb jest wtedy dodatnia. W drugiej rundzie podkreślamy za każdym razem liczbę ujemną. Liczba po jej prawej stronie jest dodatnia i większa od niej. Zatem po każdym takim ruchu liczbie ujemnej przyporządkowujemy tą liczbę obok niej. Suma wszystkich podkreślonych zmniejszy się o tą ujemną liczbę, ale nie zmieni znaku. W trzeciej rundzie podkreślania mamy dwa przypadki:
a) podkreślamy liczbę ujemną taką, że po jej prawej stronie są dwie dodatnie (już podkreślone), do których nie jest przyporządkowana żadna ujemna. Po takim podkreśleniu oczywiście suma nie zmieni znaku.
b) podkreślana jest ujemna, ta obok jest ujemna, a kolejna dodatnia. Skoro ich suma jest dodatnia, to ta środkowa jest już podkreślona. Dodatnia jest przyporządkowana tej ujemnej, ale cała suma i tak po dodaniu tej aktualnie podkreślanej nie zmieni znaku.
Zatem ostatecznie suma jest zawsze większa od 0.

[limes123]

Dzięki a masz może jakiś pomysł na 2? Całkiem nie wiem jak to ruszyć...

[adamadam]

2. M jest zbiorem 21 pkt na okregu. Udowodnic, ze sposrod katow srodkowych o koncach w punktach zbioru M mozna wybrac nie mniej niz 100 takich, ze katy srodkowe na nich oparte nie przekraczaja 120 stopni (wsk. -> z Dirichleta udowodnic, ze istnieje pkt, ktory z 13 innymi tworzy katy nie wieksze niz 120)

Załóżmy, że teza nie zachodzi. Wtedy jest co najwyżej 99 takich kątów. Niech G będzie grafem o wierzchołkach w tych punktach, takim, że istnieje krawędź pomiędzy dwoma punktami wtedy i tylko wtedy kiedy kąt środkowy między nimi jest większy niż 120 stopni. Łatwo liczymy, że graf ma co najmniej 111 krawędzi. Zauważmy, że w grafie nie ma trójelementowej kliki (oczywiste). Z twierdzenia Turana dostajemy, że jest w nim co najwyżej 110 krawędzi. Sprzeczność.
Treść twierdzenia np. .
A jak zrobić to korzystając z tej wskazówki to też nie mam pojęcia :>

[limes123]

Za grafy się jeszcze nie brałem ale i tak dzięki. A potrafisz udowodnić samą wskazówkę?

[adamadam]

A potrafisz udowodnić samą wskazówkę?

Nie.

(wsk. -> z Dirichleta udowodnic, ze istnieje pkt, ktory z 13 innymi tworzy katy nie wieksze niz 120)

Weź sobie punkt A na okręgu. Weź jeszcze 10 punktów tak, żeby tworzyły one z nim bardzo mały kąt. Po drugiej stronie średnicy przechodzącej przez A weź pozostałe 10 punktów. Wtedy ta wskazówka nie zachodzi (przy założeniu, że dobrze rozumiem jej treść ).
A rozumiem ją tak, że jedno ramię każdego z tych kątów przechodzi przez punkt A. Jeśli nie o to chodzi, to przeformułuj tą wskazówkę.

[snm]

nr 1

Rozstawiamy hobbitów w dowolny sposób. Jeśli jakiś hobbit jest obok swojego wroga, chcemy tak poprzekładać hobbity, by przestał on obok niego być i żeby nie pojawiły się nowe pary wrogów znajdujących się obok siebie.
Załóżmy, że hobbit A ma w swoim otoczeniu wroga, powiedzmy B. Ogólnie hobbit A mieszka w sąsiedztwie hobbitów B, C, D, E. Chcemy zamienić miejscami hobbita A z jakimś innym hobbitem, by liczba wrogów się zmniejszyła. Zauważmy, że:
1. Łącznie hobbitów, z którymi możemy zamienić A, jest 24
2. Nie chcemy go zamieniać z hobbitami B, C, D, E - zostaje 20
3. B poza A może mieć jeszcze max 2 wrogów - zostaje 18
4. Każdy z hobbitów C, D, E może mieć max 3 wrogów - zostaje 18-3*3=9
5. Nie chcemy przenieść A w okolice jego wroga. A ma poza B max 2 wrogów, a każdy z nich jest w sąsiedztwie max 4 pól - zostaje 9-2*4=1

Zatem zawsze jest co najmniej 1 hobbit, zamieniając którego z A zmniejszymy łączną liczbę będących obok siebie wrogów. Można zatem zmniejszyć tę liczbę do 0, co kończy dowód.

[mm-aops]

snm, Twoje rozwiazanie opiera sie na tym ze dzialku "sasiaduja" ze soba wtedy i tylko wtedy gdy maja wspolna krawedz, podczas gdy w tresci zadania jest mowa o tym ze nie moga sie nawet stykac wierzcholkami, ale wydaje mi sie ze po prostu tresc zadania jest bledna, z tego co pamietam taka sama (bledna) jest w Musztarim i podana jest identyczna wskazowka (nie pamietam czy jest cale rozwiazanie)
gdyby brac ze nie moga sie stykac wierzcholkami to nie wiem czy w ogole teza jest prawdziwa, ale prawie na pewno nie da sie tego zrobic tym sposobem; podsumowujac - tresc jest bledna, rozwiazanie dobre

[snm]

Fak, źle przeczytałem - hm, mnie też się zdaje, że w takim razie teza będzie fałszywa - a raczej na pewno zamieszczona w treści zadania wskazówka jest bezużyteczna. Cóż, zbyt zasugerowałem się wskazówką.

[wujomaro]

Nie zgadzam się z tym. Ja znalazłem rozwiązanie... Działkę o polu 25 ponumerujmy poziomymi rzędami:
1, 2, 3, 4,5
6, 7, 8, 9,10
11,12,13,14,15
16,17,18,19,20
21,22,23,24,25
jeżeli 3,8,11,12,13,14,15,18,23 będą meli za wrogów 1,5 i 25 jest to możliwe.
1,2,6,7 ma za wrogów 5,21 i 25
4,5,9,10 ma za wrogów 1,21 i 25
16,17,21,22 ma za wrogów 1,5 i 25
19,20,24,25 ma za wrogów 1,5 i 21
Wszystko się zgadza... Taka operacja jest możliwa...-- 28 lis 2009, o 12:46 --W zadaniu nie jest napisane, że dana liczba hobbitów nie może mieć takich samych wrogów.

[Swistak]

Podałeś przykład, że dla danego dobrania wrogów jest możliwe takie rozmieszczenie działek, jednak nie udowodniłeś, że dla dowolnego dobrania wrogów jest to możliwe, a o to chodzi w zadaniu.

[wujomaro]

Mamy 25 hobbitów. Załóżmy, że 9 h. ma 3 tych samych wrogów. odejmujemy 9. zostaje 16.12 z 16 ma 3 tych samych wrogów. zostaje nam 6 h. którym nie przypisaliśmy wrogów. za wrogów dajemy im h. z którymi nie sąsiadują. Nie wiem czy moje rozumowanie jest dobre. Jednak sądzę, że jest to możliwe.

[Swistak]

Ale mówię, że ty po prostu rozpatrujesz szczególne przypadki! To tak jakbyś miał udowodnić twierdzenie, dla wszystkich liczb naturalnych, a udowodniłbyś je tylko dla jedynki!

[wujomaro]

A może ty masz jakiś pomysł?

[lukaszm89]

A hobbici nie pójdą z tw. o kolorowaniu mapy?