Łamigłówki

[[Ekspert] Hakken]

Tak, to jest poprawne rozwiązanie, pozwala uratować na 100% wszystkie osoby oprócz ostatniej, która ma tylko 50% szans na przeżycie. Brawo .

@down

47 był szybszy .

[Lemiru]

Ja mam rozwiązanie w którym wszyscy oprócz ostatniego mają 100% szans na przeżycie, a ostatni ma 50%

więźniowie umawiają się, że ten ostatni(czyli pierwszy zapytany powie czerwony, jeśli widzi nieparzystą liczbę czerwonych czapek,lub zielony, gdy widzi parzystą liczbę czerwonych czapek.

następny więzień zwracając uwagę na to co mówią poprzednicy może wydedukować jaką ma czapkę

Przykład:

Drugi więzień od końca usłyszał ?czerwony? i widzi parzysta liczbę czerwonycz czapek. Wie, że jego czapka jest czerwona, ponieważ liczba czerwonych czapek, które widzi przed sobą jest parzysta, mówi ?czerwony?

Trzeci więzień od końca usłyszał ?czerwony? i ?czerwony? i widzi parzystą liczbę czapek, więc wie, że jego kapelusz jest zielony, więc mówi ?zielony?. I tak dalej aż do pierwszego więźnia.

Ogólna zasada polega na tym, aby wsłuchać się w to co mówili więźniowie wcześniej i jeżeli liczba czerwonych czapek(parzysta lub nieparzysta) ulegnie zmianie w stosunku do tego co się widzi to znaczy, że ma się czapkę czerwoną, jeśli nie to ma się zieloną.

Ja się namęczyłem pół godziny żeby to napisać, a tu się okazuje, że ktoś mnie wyprzedził ?! jestem bardzo wkurzony

[Lemiru]

Skoro temat stoi od kilku dni to ja zadam zagadkę:

Na rozwidleniu dróg stoi dwóch braci, jeden zawsze mówi prawdę, a drugi zawsze kłamie. Jedna droga jest bezpieczna, a druga nie.

Pytanie: Jakie pytanie trzeba zadać, żeby dowiedzieć się, która droga jest bezpieczna? odpowiedź uzasadnić (bo nie uznam)

[Sermaciej]

Spytać się, co odpowiedziałby drugi brat, i pójść drugą drogą.

[Lemiru]

@UP:

Nie uznaję ponieważ:

1. Odpowiedź nie jest do końca poprawna (lecz jesteś bardzo blisko).

2. Nie uzasadniłeś.

[[Ekspert] Hakken]

Kolejna fajna zagadka/zadanie mi się przypomniało. Mozna znaleźć odpowiedź intuicyjnie albo udowodnić matematycznie.

Mamy budynek wysoki na N pięter i dwa jajka. Jajka ciekawe, bo identyczne. w budowli istnieje takie piętro graniczne, że jak zrzucimy jajko poniżej tego pietra to nic mu się nie stanie, a jak powyżej to się zniszczy. Jeśli jajko się nie zniszczy, to można go użyć ponownie, jest ono w pełni sprawne.

Jak znaleźć piętro graniczne jak najmniejszą liczbą rzutów?

[Fori]

Do zagadki Hakkena

Wejść na piętro N/2, albo (N-1)/2 jak N jest nieparzyste, i zrzucić jedno jajko. Jak się rozbije lecimy po kolei dolną połówkę. Jak się nie rozbije wchodzimy o połowę pozostałych pięter wyżej i próbujemy znowu. W najgorszym wypadku mamy N/2 rzutów,a w najlepszym log2(N).

[[Ekspert] Hakken]

Trafne użycie wyszukiwania binarnego, też była to moja pierwsza myśl, ale N/2 to słaby wynik i można go znacznie ulepszyć.

Dodam jeszcze, że chcemy optymalizować czas oczekiwany.

[Fori]

W takim razie inny pomysł.

Zwyczajnie spuszczając jajko raczej nie da się osiągnąć wyniku lepszego niż N/2, więc trza ciepnąć dwa na raz. Jedno w dół, a drugie w górę na wysokość dwóch pięter. jak rozbije się górne (piętro+2) to zrzucamy pozostałe jajo żeby sprawdzić czy granica przebiega między piętrami 0 i +1, czy +1 i +2. Jak żadne się nie rozbije to idziemy trzy piętra w górę. W najgorszym przypadku mamy ok. N/3 rzutów.

EDIT: Stosując algorytm jak wyżej:

Jeżeli weźmiemy ilość pięter na jaką podrzucamy jajko jako k, to maksymalna ilość rzutów będzie równa k-1+N/k. Taka funkcja ma minimum w k=sqrt(N)

[[Ekspert] Hakken]

Wciąż nie jest to optymalne.

Radzę do tego podejść bardziej ściśle, matematycznie. Chociaż co kto lubi, można kombinować i tak .

EDIT: Stosując algorytm jak wyżej:

Jeżeli weźmiemy ilość pięter na jaką podrzucamy jajko jako k, to maksymalna ilość rzutów będzie równa k-1+N/k. Taka funkcja ma minimum w k=sqrt(N)

Tak, to jest poprawna odpowiedź!

Chcesz przedstawić pełne rozumowanie/dowód matematyczne?

[Fori]

Za dowód podziękuję, nigdy nie byłem za dobry w dowodzeniu.

[[Ekspert] Hakken]

No to ja też nie pokażę, jak ktoś zechce pokazać to proszę bardzo. A jak ktoś chciałby zobaczyć to może napisać mi PW.

[Mysquff]

Pewnie coś źle zrozumiałem, ale co zrobicie, jak oba by się rozbiły?

@down - OK, sorry, troszkę źle zrozumiałem to co napisaliście wcześniej...

[[Ekspert] Hakken]

Nie ma takiej możliwości.

Rzucamy pierwsze jajko na wysokości sqrt(n) - jeśli się rozbije, to tym jajkiej które nam zostało idziemy od doły - maksymalnie sqrt(n) sprawdzeń.

Jeśli na sqrt(n) się nie rozbiło, to wchodzimy na 2sqrt(n). Jeśli się rozbije, to tym co zostało badamy od sqrt(n)+1 do 2*sqrt(n)- znowu max sqrt (n) sprawdzeń. I tak dalej i tak dalej

[Lemiru]

Jako, że temat stoi to ja zadam zagadkę.

Na stole leżą trzy patyczki. Nie dodając ani jednego patyczka zrób z trzech cztery. Patyczków nie wolno łamać.

układ patyczków: I I I

[Devius]

I V ?

[Lemiru]

Coś czułem, że będzie łatwo, ale żeby aż tak?

Devius zadajesz.

[Devius]

Nie mam pomysłu, oddaję.

[detox]

Na ożywienie tematu.

"Nuta w literze

Gości w kraterze."

Co to jest ?

[MarcinCthulhu]

Lawa. Też mi łamigłówka

[detox]

Chciałem tylko troszkę temat rozruszać zadajesz

[MarcinCthulhu]

No to może zarzucę klasykiem ;]

Co to jest: zarośnięte, spocone i lata miedzy majtkami...?

[Gawain]

Bosman

[MarcinCthulhu]

Tak jest, zadajesz

[Jubazav]

Na rozruch tematu.

Podczas samochodowej podróży, w której uczestniczyli ojciec z synem nastąpił wypadek. Ojciec zmarł na miejscu, syna w ciężkim stanie przewieziono do szpitala, w którym musiał być natychmiast operowany. Na salę operacyjną wchodzi chirurg i woła:

- O Boże, przecież to mój syn!

Pytanie: Kim był chirurg dla pacjenta?