zdrowy rozsądek i trochę matmy

Matematyczne łamigłowki i zagadki...
Ptolemeusz
Użytkownik
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

Post autor: Ptolemeusz »

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.
półpasiec
Gość Specjalny
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

Post autor: półpasiec »

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
Ostatnio zmieniony 27 lip 2004, o 20:31 przez półpasiec, łącznie zmieniany 1 raz.
Ptolemeusz
Użytkownik
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

Post autor: Ptolemeusz »

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.
półpasiec
Gość Specjalny
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

Post autor: półpasiec »

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.
Ptolemeusz
Użytkownik
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

Post autor: Ptolemeusz »

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
random321
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 26 lut 2019, o 00:17
Płeć: Mężczyzna
Lokalizacja: Polska

Re: zdrowy rozsądek i trochę matmy

Post autor: random321 »

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}\):

Kod: Zaznacz cały

a  c
 \/
 /\
b  d
\(\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}\):

Kod: Zaznacz cały

/-----\
a  c  e 
 \/ \/
 /\ /\
b  d  f
\-----/
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

Kod: Zaznacz cały

/-------\
    /----\
/-----\
a  c  e  g
 \/ \/ \/
 /\ /\ /\
b  d  f  h
\-----/
    \----/
\-------/
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 :o.

Chętnie się dowiem czy to co zrobiłem ma sens.
ODPOWIEDZ