Takie zadanie:
Na dworze króla Artura spotkało się 2n rycerzy, a każdy z nich miał wśród obecnych co najwyżej n-1 wrogów. Udowodnij, że Merlin, nadworny czarnoksiężnik króla Artura, może tak rozmieścić rycerzy przy Okrągłym Stole, że żaden z nich nie będzie siedział obok swojego wroga.
Jest to zadanie 292 ze zbioru Musztari’ego
Znam dwa rozwiązania jedno ze zbioru , a drugie moje.
Ciekaw jestem jeszcze innych.
zdrowy rozsądek i trochę matmy
-
- Użytkownik
- Posty: 365
- Rejestracja: 11 lip 2004, o 18:51
- Płeć: Mężczyzna
- Lokalizacja: Jarosław/Kraków
- Pomógł: 2 razy
-
- Gość Specjalny
- Posty: 534
- Rejestracja: 8 lip 2004, o 17:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 17 razy
zdrowy rozsądek i trochę matmy
Posadzmy tych rycerzy przy stole. Zalozmy, ze a1 siedzi zle, wtedy wstaje i szuka takich dwoch rycerzy, ktorzy nie sa jego wrogami i siedza kolo siebie. Taka sytuacja musi istniec. Zalozmy przeciwnie, ze moze istniec taka sytuacja, ze zadnych dwoch sposrod conajmniej n przyjaciol a1 nie siedzi kolo siebie. Sprobujmy taki stol skonstruowac. Posadzmy najpierw tych przyjaciol i przy 2n-1 osobowym stole siedzi conajmniej n osob. Zeby ich rozdzielic to pomiedzy b1 a b2, b2 a b3 ,b3 a b4, .... b(n-1) a bn, bn a b1 musimy posadzic jednego wroga, tych par (bi , b(i+1)) jest n i w kazdej ma sie znalezc wrog, ale wrogow jest tylko n-1 wiec nie mozna. Tak wiec a1 wstaje i szuka tych przyjaciol ktorzy siedza kolo siebie, niech to beda ak i a(k+1), ak wstaje i siada na miejscu a(k-1), a(k-1) na miejscu a(k-2) ... a3 na miejscu a2 i a2 na miejscu a1. Jesli w nowopowstalej parze sasiadow a2 i a2n znajduja sie wrogowie to powtarzamy ta czynnosc dla a2, jesli taka sama sytuacja sie powtorzy dla a3 to robimy tak znowu i powtarzamy ja dopoki kolo a2n nie usiadzie jej przyjaciel. Jezeli jednak bedziemy wciaz odsylac ich w to samo miejsce, to po pewnym czasie a1 wroci do swojej pozycji pierwotnej i zrobi nam sie sytuacja w ktorej juz nic nam to odsylanie nie da. Niech grupa tych ludzi ktorych osylanie nic nie dalo (a1 -> a2->...->ak) nazywa sie A, ponadto wiemy ze w A ai jest przyjacielem ai-1 i ai+1 oraz ak - a1. Przesadzamy wiec a2n w inne miejsce, tak jak na poczatku a1, ale jesli i tym razem sytuacja nam sie powtorzy, grupe tych ludzi ktorych odsylanie nic nie dalo i nalezy do nich a2n nazwijmy B(niech w tej grupie bezie l ludzi a2n->a2n-1->...->a2n-l+1), to z racji tego, ze mozemy na miejsce pierwotne a1 posadzic dowolna osobe z A i na miejsce pierwotne a2n posadzic dowolna osobe z B. Mozemy zrobic kl par siedzacych obok siebie, zalozmy jednak, ze to nic nie dalo, oznacza to, ze kazdy z A jest wrogiem kazdego z B, wniosek z tego, ze k,l mniejsze rowne n-1. Udowodnimy teraz cos takiego: Niech C oznacza tych rycerzy, ktorzy nie naleza ani do A ani do B. Dla kazdego rycerza nalezacego do grupy zawierajacej nie wiecej osob istnieje w C takich dwoch rycerzy, ze sa oni jego przyjaciolmi i siedza obok siebie.
Zalozmy, ze k nie wieksze l, w C znajduje sie conajmniej n-k+1 przyjaciol kazdego z A, zalozmy, ze nie moze zaistniec taka sytuacja, wtedy kazdy z tych przyjaciol musi zostac rozdzielony wrogiem, czyli miedzy n-k+1 przyjaciol trzeba wsadzic n-k wrogow, rzeczywista ilosc wrogow w C wynosi n-1-l, wiec musi zajsc n-1-l >= n-k k>=l+1 a to jest sprzecznosc, bo l+1>k. Bierzemy wiec osobe siedzaca na miejscu pierwotnym a1 i sadzamy miedzy dwoch jego kompanow, nastepnie a2, miedzy jego kompanow az do ak, jesli zajdzie taka sytuacja, ze pewni dwaj rycerze siedzacy obok w C beda przyjaciolmi dwoch rycerzu z A to sadzmy obydwu miedzy nich bo przeciez mozemy. Posadzilismy wiec wszystkich z A miedzy rycerzy w C i wymieszalismy ich. Teraz na miejscu pierwotnym a1 siedzi ak+1, i postepujemy z nim tak samo jak na poczatku z a1, bo znamy juz sposoby na racenie sobie z blednymi kolami. Postepowanie to musi sie skonczyc, bo za kazdym razem kiedy powtarzac bedziemy cykl zwiekszy nam sie indeks rycerza ktory bedzie siadal kolo rycerzy z B. Do nie B(czyli do grupy osob, wsrod ktorych bedziemy powtarzac cykl) nalezy wiecej rycerzy niz do B zatem w pewnym momencie zabraknie wsrod tych nowych ludzi wrogow rycerzy z B. Nalezy jeszcze wziac poprawke na to, ze jesli w pewnym momencie nowe bledne kolo bedzie wieksze od B to rozumowanie powtarzamy dla B i pozniej dla kazdego kola ktore bedzie mialo mniej osob. Koniec
Zalozmy, ze k nie wieksze l, w C znajduje sie conajmniej n-k+1 przyjaciol kazdego z A, zalozmy, ze nie moze zaistniec taka sytuacja, wtedy kazdy z tych przyjaciol musi zostac rozdzielony wrogiem, czyli miedzy n-k+1 przyjaciol trzeba wsadzic n-k wrogow, rzeczywista ilosc wrogow w C wynosi n-1-l, wiec musi zajsc n-1-l >= n-k k>=l+1 a to jest sprzecznosc, bo l+1>k. Bierzemy wiec osobe siedzaca na miejscu pierwotnym a1 i sadzamy miedzy dwoch jego kompanow, nastepnie a2, miedzy jego kompanow az do ak, jesli zajdzie taka sytuacja, ze pewni dwaj rycerze siedzacy obok w C beda przyjaciolmi dwoch rycerzu z A to sadzmy obydwu miedzy nich bo przeciez mozemy. Posadzilismy wiec wszystkich z A miedzy rycerzy w C i wymieszalismy ich. Teraz na miejscu pierwotnym a1 siedzi ak+1, i postepujemy z nim tak samo jak na poczatku z a1, bo znamy juz sposoby na racenie sobie z blednymi kolami. Postepowanie to musi sie skonczyc, bo za kazdym razem kiedy powtarzac bedziemy cykl zwiekszy nam sie indeks rycerza ktory bedzie siadal kolo rycerzy z B. Do nie B(czyli do grupy osob, wsrod ktorych bedziemy powtarzac cykl) nalezy wiecej rycerzy niz do B zatem w pewnym momencie zabraknie wsrod tych nowych ludzi wrogow rycerzy z B. Nalezy jeszcze wziac poprawke na to, ze jesli w pewnym momencie nowe bledne kolo bedzie wieksze od B to rozumowanie powtarzamy dla B i pozniej dla kazdego kola ktore bedzie mialo mniej osob. Koniec
Ostatnio zmieniony 27 lip 2004, o 20:31 przez półpasiec, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 365
- Rejestracja: 11 lip 2004, o 18:51
- Płeć: Mężczyzna
- Lokalizacja: Jarosław/Kraków
- Pomógł: 2 razy
zdrowy rozsądek i trochę matmy
Co do twojego posta to pozostaje mi tylko powiedzieć: no,no,no (choć tak bardzo wnikliwie tego nie czytałem) i stwierdzić że to było dłuuugie, jak dla mnie za.
Wydaje mi się że najistotniejsze było zauważenie że można sobie tak ustawić dowolnie i potem dopiero przestawiać. Takie, jak dla mnie ciekawe podejście, jeszcze się z wieloma takimi zadaniami nie spotkałem.
Wydaje mi się że najistotniejsze było zauważenie że można sobie tak ustawić dowolnie i potem dopiero przestawiać. Takie, jak dla mnie ciekawe podejście, jeszcze się z wieloma takimi zadaniami nie spotkałem.
-
- Gość Specjalny
- Posty: 534
- Rejestracja: 8 lip 2004, o 17:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 17 razy
zdrowy rozsądek i trochę matmy
to jest dlugie, bo krocej nie da sie tego opisac, tak zeby mniej wiecej bylo wiadomo o co chodzi, chociaz pomysl na jego rozwiazanie jest krotki i krokow tez nie jest za wiele (wg mnie). W sumie cale rozwiazanie polega na tym, ze udowadniamy mozliwosc rozsadzenia kazdej zlej pary.
-
- Użytkownik
- Posty: 365
- Rejestracja: 11 lip 2004, o 18:51
- Płeć: Mężczyzna
- Lokalizacja: Jarosław/Kraków
- Pomógł: 2 razy
zdrowy rozsądek i trochę matmy
nie opis jest chyba dobry tylko rozwiązanie zadługie, jest kilkulinijkowe
Dam Ci podpowiedź przejdź na terminologie teorio grafową i udowodnij że odpowiedni graf jest hamiltonowski
Dam Ci podpowiedź przejdź na terminologie teorio grafową i udowodnij że odpowiedni graf jest hamiltonowski
Re: zdrowy rozsądek i trochę matmy
Postanowiłem spróbować to zadanie bez żadnej wiedzy dot. topologii itp. Mogę uzasadnic w formie obrazkowej, że zawsze można stworzyć relację między rycerzami taką aby można było rozsadzić rycerzy tak jak wymaga to zadanie, dla dowolnego \(\displaystyle{ n}\). Pytanie czy każdą, dowolną relację spełniającą warunek zadania można sprowadzić, przetransferować do mojej. Jeżeli umiałbym to uzasadnić to miałbym nieformalny, opisowy "dowód". Być może można to łatwo obalić kontrprzykładem i wtedy dupa z moich rozważań.
Do rzeczy. Pominę \(\displaystyle{ n=1}\), bo jest trywialne. Łatwo byłoby to rozrysować, ale żywotność obrazków w internecie jest o wiele krótsza niż tekstu, dlatego przedstawie to graficznie w formie tekstu. Będę rozważał zawsze \(\displaystyle{ n-1}\) wrogów, bo to "worst case".
\(\displaystyle{ n=2}\):
\(\displaystyle{ a,b,c,d}\) to rycerze rozstawieni przy stole, a linie, w tym wypadku przekątne, informują nas kto jest wrogiem kogo. W tym wypadku \(\displaystyle{ a,d}\) są wrogami oraz \(\displaystyle{ b,d}\) no i oczywiście wrogowie nie siedzą koło siebie. Każda linia dotykająca rycerza oznacza ile ma wrógów. W tym wypadku każdy ma tylko jednego wroga, \(\displaystyle{ n-1}\). W ponższym przykładzie każdy będzie miał dwóch wrogów itd.
\(\displaystyle{ n=3}\):
Algorytm przejścia z \(\displaystyle{ n}\) do \(\displaystyle{ n+1}\) wygląda więc tak: dodajemy dwóch rycerzy, w tym wypadku \(\displaystyle{ e,f}\). Twórzymy przekątne w nowym "kwadracie" \(\displaystyle{ e,d}\) oraz \(\displaystyle{ c,f}\). Następnie łączymy nowo dodanego rycerza z górnej krawędzi ze wszystkimi rycerzami z górnej krawędzi z wyjątkiem rycerza siedzącego obok nowo dodanego. Czyli łączymy \(\displaystyle{ e}\) z \(\displaystyle{ a}\), ale nie z \(\displaystyle{ c}\). Analogicznie z dolną krawędzią.
\(\displaystyle{ n=4}\):
Stosując powyższy algorytm otrzymujemy
I tak dalej.
Pozostaje pytanie czy mając dowolną konstelację spełniającą zadanie, zawsze będę mógł przypisać rycerzy do mojego rysunku? Jeżeli udałoby mi się to uzasadnić to koniec. Obawiam się, że może to być o wiele bardziej skomplikowane... albo można znaleźć jakiś kontrprzykład, ale bym musiał chyba chwilę posiedzieć jeszcze nad tym .
Chętnie się dowiem czy to co zrobiłem ma sens.
Do rzeczy. Pominę \(\displaystyle{ n=1}\), bo jest trywialne. Łatwo byłoby to rozrysować, ale żywotność obrazków w internecie jest o wiele krótsza niż tekstu, dlatego przedstawie to graficznie w formie tekstu. Będę rozważał zawsze \(\displaystyle{ n-1}\) wrogów, bo to "worst case".
\(\displaystyle{ n=2}\):
Kod: Zaznacz cały
a c
\/
/\
b d
\(\displaystyle{ n=3}\):
Kod: Zaznacz cały
/-----\
a c e
\/ \/
/\ /\
b d f
\-----/
\(\displaystyle{ n=4}\):
Stosując powyższy algorytm otrzymujemy
Kod: Zaznacz cały
/-------\
/----\
/-----\
a c e g
\/ \/ \/
/\ /\ /\
b d f h
\-----/
\----/
\-------/
Pozostaje pytanie czy mając dowolną konstelację spełniającą zadanie, zawsze będę mógł przypisać rycerzy do mojego rysunku? Jeżeli udałoby mi się to uzasadnić to koniec. Obawiam się, że może to być o wiele bardziej skomplikowane... albo można znaleźć jakiś kontrprzykład, ale bym musiał chyba chwilę posiedzieć jeszcze nad tym .
Chętnie się dowiem czy to co zrobiłem ma sens.