Porwanie Smerfetki

[Gość: Prestidigitator]

Może juz było:)

Gargamel porwał i uwieził Smerfektę, Smerfy wyruszyły jej na pomoc, ale
sprytny Gargamel wpadł na pomysł, że rzuci na smerfów czar i ch również
uwięzi. Czar czyni ich nieruchomymi,nie mogą nic mówic, mrugac oczami itp.
Jednoczesnie Gargamel nakłada na głowę każdego smerfa niebieską lub żółtą
czapeczkę, smerfy siedzą przy okragłym stole i każdy widzi kolor innych ale
nie swojej. Czar pryśnie jeśli w tym samym momencie wszystkie smerfy mające
ten sam kolor czapki (i tylko one) będą chciały wstac. Smerfy nie wiedzą ile
jest czapeczek danego koloru, Gargamel wchodzi co pięc minut do celi by
sprawdzic czy smerfy nie uciekły.
Pomoz smerfom zeby czar prysł.

[Gość: lukkasz]

jakby tak kazdy wybral sobie losowo jakas liczbe niewymierna (ograniczona z
gory) i potem w przedzialach czasu o dlugosci rownej tej liczbie sekund na
zmiane staral sie wstac i sie nie staral, to by w koncu z prawdopodobienstwem
rownym jeden numer sie udal (i to dowolnie szybko, jesli by zamienic sekundy na
jakas mniejsza jednostke i odpowiednio ograniczyc liczbe niewymierna).
ale nie wiem, czy mozna zalozyc, ze one sa do tego zdolne.
a jesli chodzi o mozliwosc innego rozwiazania - rozumiem, ze nie ma zadnej
mozliwosci komunikacji i nie jest mozliwe ustalenie wspolnego rozwiazania, tak?
wiec mozna liczyc tylko na szczescie, ze inni wpadna na podobny pomysl?
Pozdr,
lukkasz

[Gość: Prestidigitator]

Gość portalu: lukkasz napisał(a):

> jakby tak kazdy wybral sobie losowo jakas liczbe niewymierna (ograniczona z
> gory) i potem w przedzialach czasu o dlugosci rownej tej liczbie sekund na
> zmiane staral sie wstac i sie nie staral, to by w koncu z prawdopodobienstwem
> rownym jeden numer sie udal (i to dowolnie szybko, jesli by zamienic sekundy
na
>
> jakas mniejsza jednostke i odpowiednio ograniczyc liczbe niewymierna).
> ale nie wiem, czy mozna zalozyc, ze one sa do tego zdolne.
> a jesli chodzi o mozliwosc innego rozwiazania - rozumiem, ze nie ma zadnej
> mozliwosci komunikacji i nie jest mozliwe ustalenie wspolnego rozwiazania,
tak?
>
> wiec mozna liczyc tylko na szczescie, ze inni wpadna na podobny pomysl?
> Pozdr,
> lukkasz

Nie chodziło mi o takie rozwiazanie. Można założyc,że smerfy będą myslały o
wstaniu co dowolnie mała częśc sekundy, więc kiedyś i tak wstanąci odpowiedni ,
Podpowiem, że zadanie da się nawet rozwiązac (w skonczonym okresie czasu) jeśli
smerfów jest nieskończenie wiele, ale liczebnośc czapek jednego koloru jest
ograniczona.
Tak,nie ma możliwości komunikacji pomiędzy smerfami, ale jest możliwe takie
ustalenie działania, że wszyscy odpowiedni wstaną za jednym razem

Powodzenia
Prestidigitator

[Gość: lukkasz]

mozna by tak:
jak ktos widzi parzysta ilosc niebieskich czapek, to wstaje, jak nieparzysta,
to siedzi.
udaje sie od razu, ale oczywiscie nie ma jak tej strategii wspolnie ustalic,
wiec kicha.
bede jeszcze myslal,
lukkasz

[Gość: pafcio]

jeżeli widzę n czapeczek żółtych i m czapeczek niebieskich (n+1<m) i po n
okresach podobnie do mnie myślące smerfy w czapeczkach żółtych nie wstają to
wstaję razem z nimi w n+1 okresie.... gorzej jak n=m i wszyscy naraz wstaną,
bo nie wiem czy to nie jest sprzeczne z treścią zadania...

[Gość: Prestidigitator]

Gość portalu: pafcio napisał(a):

> jeżeli widzę n czapeczek żółtych i m czapeczek niebieskich (n+1<m) i po n
> okresach podobnie do mnie myślące smerfy w czapeczkach żółtych nie wstają to
> wstaję razem z nimi w n+1 okresie.... gorzej jak n=m i wszyscy naraz wstaną,
> bo nie wiem czy to nie jest sprzeczne z treścią zadania...

Jezeli n=m to każdy smerf widzi jedną czapeczkę mniej w tym kolorze który ma
na sobie, wiec jeżeli widzi że ci co mieli mniej czapeczek nie wstali to się
zorientuje że liczba jest równa, wystarczy więc umówić się by w takiej
sytuacji w następnym okresie np. pierwsi wstali ci co widzą niebieskie czapki.
I czar pryska...

[Gość: lukkasz]

no tak, tylko wlasnie "trzeba sie umowic". Rozumiem, ze jest to niemozliwe.
ale z odpowiedzi Prestigitatora wnoszę, że to o tą odpowiedź chodziło?
pozdr

Drobna korekta, sorry - Re: Porwanie Smerfetki

[cardemon]

Gość portalu: Prestidigitator napisał(a):

> Może juz było:)

Witaj Prestidigitatorze,

Tej akurat zagadki, jak pamięcią sięgam, jeszcze na forum nie było. Były
natomiast różne jej wersje i modyfikacje. Nawet ja sam kiedyś jedną w tym stylu
napisałem i zamieściłem tu na forum. I powiem więcej: popełniłem to samo
przeoczenie, jakie i Tobie się przydarzyło. :)
Nie chcę nikomu psuć zabawy, wręcz przeciwnie, chcę ułatwic dojście do
prawidłowego rozwiązania, więc pozwól, że dodam jedno zdanie, które pozwoli
rozwiązać tę zagadkę obecnym tu forumowiczom.

Oto więc jej treść z drobną korektą:

>
> Gargamel porwał i uwieził Smerfektę, Smerfy wyruszyły jej na pomoc, ale
> sprytny Gargamel wpadł na pomysł, że rzuci na smerfów czar i ch również
> uwięzi. Czar czyni ich nieruchomymi,nie mogą nic mówic, mrugac oczami itp.
> Jednoczesnie Gargamel nakłada na głowę każdego smerfa niebieską lub żółtą
> czapeczkę

mówiąc dobitnie:
-A wy wstrętne, niedobre Smerfy. Zamiast tych waszych obrzydliwych czerwonych
czapeczek każdy dostanie teraz zółtą lub niebieską. I możecie mi wierzyć, że
przynajmniej jeden z was będzie miał zółtą i przynajmniej jeden z was będzie
miał teraz niebieską czapeczkę na głowie.

> Smerfy siedzą przy okragłym stole i każdy widzi kolor innych ale
> nie swojej. Czar pryśnie jeśli w tym samym momencie wszystkie smerfy mające
> ten sam kolor czapki (i tylko one) będą chciały wstac. Smerfy nie wiedzą ile
> jest czapeczek danego koloru, Gargamel wchodzi co pięc minut do celi by
> sprawdzic czy smerfy nie uciekły.
> Pomoz smerfom zeby czar prysł.

Teraz Smerfy same powinny dać sobie radę. :)
A swoją drogą jest to bardzo ciekawy aspekt tej zagadki wart przedyskutowania.

Pozdrowienia,
CdM

Drobna korekta, sorry - Re: Porwanie Smerfetki

[Gość: Prestidigitator]

Drogi Cardemonie

W algorytmie który ma byc rozwiązaniem tzn.
Jeżeli liczba jest skończona wystarczy, żeby w kolejnych turach "wstawali" ci
co widzą kolejno 0,1,2,...,n-1 czapeczek np. niebieskich.-jest możliwośc
rozwiązania nawet przy takich samych czapkach. Ponieważ ci co maja czapki
jednego koloru ( i tylko ci) widzą o 1 czapkę mniej tego koloru więc pewne jest
że wstaną w tym samym momencie.
W sytuacji gdy każdy widzi np. 0 czapek koloru niebieskiego to wstaje, jezeli
tych czapek jest 0 to wstana wszyscy, jeżeli jedna to wstanie właśnie ona.

Pozdrowienia za swiata magii
Prestidigitator

[andy._]

Korekta Cardemona na przypadek "wszystkie jednakowe" oczywiście bardzo trafna.
Ja mam inne zastrzeżenie dotyczące synchronizacji działania smerfów.
Rozwiązujący dostrzegli konieczność wprowadzenia cykli i założyli milcząco, że
okresem cyklu jest 5 minut albo jakiś umowny, jednakowy dla wszystkich "czas
namysłu", co wcale nie jest oczywiste z punktu widzenia każdego smerfa bez
wcześniejszej informacji oraz odpowiedniedo uzgodnienia.

Gość portalu: Prestidigitator napisał(a):
> ... Czar pryśnie jeśli w tym samym momencie wszystkie smerfy mające
> ten sam kolor czapki (i tylko one) będą chciały wstac.

Jak okreslić TEN moment?
Wydaje mi się, że powinno to być precyzyjniej określone w treści zagadki

Pozdr. A.

[Gość: Piotr M.]

Wydaje mi się, że nalezy dokładniej czytać.
Nikt w treści nie mówi o tym, że mają wstać lecz cytuję:
kiedy będą chcieli wstać. A to znaczy , ze kazdy z nich wykonuje
ileśtam operacji myslowych i w pewnym momencie juz wie ze chce
lub jszcze nie wstac.
Liczy sie to ich "chceniewstanięcia" (hihihi)
sa umysłowo na podobnym poziomie wiec po pewnym czasie wszyscy bez wzgledu na
to ile i jakich jest czapek, bedzie wiedzial, zacznie chciec i juz.
A jesli chodzi o rozumowanie smerfow to indukcja, cos na wzor
zadania o niewiernych zonach matematykow, ktore za swa niewiernosc mialy byc
rozstrzelane.
Pozdrawiam. Piotr M.

[Gość: swiercz]

A czy Smerfetka też jest uwikłana w ten czar, czy może patrzy z boku i może
mówić?