Ocena wątku:
  • 0 głosów - średnia: 0
  • 1
  • 2
  • 3
  • 4
  • 5
Kącik Zagadek
żeniec napisał(a):
Sofeicz napisał(a): 9 myszek?
A jaki byłby algorytm?

Cholera, ja poniżej 64 zejść nie mogłem. Algorytm trywialny, matryca 31 x 33 (wychodzi 1023, więc parę miejsc będzie pustych). Robimy mieszankę z każdego rzędu i każdej kolumny. Przy podawanych założeniach dwie myszy zdechną i na ich skrzyżowaniu odnajdziemy poszukiwaną butelkę.

Można to oczywiście dać w trzy wymiary, wtedy matryca jest 10x10x10, każda dawka jest ze stu butelek i mamy łącznie 30 myszy. Trzy zdechną, reszta się uchleje. Może ktoś potrafi zrobić matrycę z większą ilością wymiarów, ja dziękuję za uwagę. Moja odpowiedź jest 30.
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
bert04 napisał(a): Cholera, ja poniżej 64 zejść nie mogłem. Algorytm trywialny, matryca 31 x 33 (wychodzi 1023, więc parę miejsc będzie pustych). Robimy mieszankę z każdego rzędu i każdej kolumny. Przy podawanych założeniach dwie myszy zdechną i na ich skrzyżowaniu odnajdziemy poszukiwaną butelkę.

Można to oczywiście dać w trzy wymiary, wtedy matryca jest 10x10x10, każda dawka jest ze stu butelek i mamy łącznie 30 myszy. Trzy zdechną, reszta się uchleje. Może ktoś potrafi zrobić matrycę z większą ilością wymiarów, ja dziękuję za uwagę. Moja odpowiedź jest 30.
Całkiem niezły pomysł. Jeśli dobrze zrozumiałem metodę, to można ją przeciągnąć jeszcze trochę by zejść do 20. Nieźle, ale da się lepiej Uśmiech
Odpowiedz
Ok. Nowe podejście. Idziemy w czwarty wymiar. 5x6x6x6. Czyli pięć "kostek" o rozmiarze 6^3. Miejsce na 1080 butelek, więc znowu parę pustych. I 5+6+6+6 myszy, czyli 23. Pierwsze 5 myszy spija próby z każdej "kości", czyli z 216 butelek każda. Przy pozostałych 3 x 6 bierzemy jak w przykładzie trójwymiarowym każdą płaszczyznę (6x6...) ale ze wszystkich "kości" (...×5=180). Cztery myszy zdechną.

Od praktyki do teorii. Przeanalizowałem pierwiastki o podstawie większej niż 4. Zakładam, że układanie systemów, w których strona "kostki" jest równa 1 nie ma sensu, więc rozmiar każdego wymiaru musi być minimum 2. Teraz już łatwo. Poszukiwana jest 10 wymiarowa przestrzeń 2^10=1024. Mamy 2x10=20 myszy. Nie wiem dokładnie, jak je spijać, ale teoretycznie się da. Poniżej tej liczby IMHO zejść nie można.

20.


Edit: nie widziałem komentarza żeńca, ale doszedłem do 20-tki bez tego. Dalej nie potrafię a i tak nie mam zagadki, więc niech ktoś inny pociągnie.
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
No dobra. Mam. 10. Numerujemy każdą butelkę w systemie dwójkowym, od 0000000001 do 1111101000. Bierzemy 10 myszy na każdą pozycję w tych liczbach. Każda z myszy spija wino tylko wtedy, jeżeli wino w jej pozycji ma "1". Poszukiwany numer butelki odnajdziemy notując dla każdej martwej myszy "1" w jej pozycji. Jeżeli więc zdechły myszy druga, trzecia, siódma i dziesiąta, to szukamy butelki 0110001001, czyli 393.

Przy okazji zobaczyłem, że i dla poprzednich rozwiązań jedna mysz na wymiar była zbyteczna, więc dla matrycy 2 wymiarowej starcza 62 myszy, dla 3 - 27, dla 4 -19. Tu już w poprzednim wnioskowaniu mogłem dojść do liczby 10. Ale dopiero myślenie na temat "jak je spoić" doprowadziło mnie do rozwiązania.

Teraz czekam, jak kolega uzasadni 9
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
Dzielimy po chłopsku 1000 butelek na pół, robimy mieszaninę z każdej 500 i dajemy 2 myszkom.
Umiera ta, która wypiła zatrutą 500.
I tak dalej.
Po 9 krokach mamy odpowiedż (i 9 martwych myszek) Uśmiech
A nas Łódź urzekła szara - łódzki kurz i dym.
Odpowiedz
Sofeicz napisał(a): Dzielimy po chłopsku 1000 butelek na pół, robimy mieszaninę z każdej 500 i dajemy 2 myszkom.
Umiera ta, która wypiła zatrutą 500.
I tak dalej.
Po 9 krokach mamy odpowiedż (i 9 martwych myszek) Uśmiech

Zapomniałeś, że przyjęcie jest za godzinę. I okres czasu od wypicia do śmierci jest też godzina. Nie ma czasu na ponowne wykorzystywanie myszy, wynik musi być znany od razu. Inaczej można by wykorzystać jedną mysz, jak proponował ktoś wcześniej (trwałoby do 41,6 dni, ale przynajmniej chronimy zwierzątka).

Ale metodę miałeś w sumie taką samą, system binarny. Przynajmniej co do zasady, liczba dwójkowa to efekt dzielenia liczby dziesiętnej przez 2, z resztą.
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
bert04 napisał(a): Zapomniałeś, że przyjęcie jest za godzinę

Faktycznie. Dumam dalej.
A nas Łódź urzekła szara - łódzki kurz i dym.
Odpowiedz
bert04 napisał(a): No dobra. Mam. 10. Numerujemy każdą butelkę w systemie dwójkowym, od 0000000001 do 1111101000. Bierzemy 10 myszy na każdą pozycję w tych liczbach. Każda z myszy spija wino tylko wtedy, jeżeli wino w jej pozycji ma "1". Poszukiwany numer butelki odnajdziemy notując dla każdej martwej myszy "1" w jej pozycji. Jeżeli więc zdechły myszy druga, trzecia, siódma i dziesiąta, to szukamy butelki 0110001001, czyli 393.
Działa, zadajesz Uśmiech

bert04 napisał(a): Przy okazji zobaczyłem, że i dla poprzednich rozwiązań jedna mysz na wymiar była zbyteczna, więc dla matrycy 2 wymiarowej starcza 62 myszy, dla 3 - 27, dla 4 -19. Tu już w poprzednim wnioskowaniu mogłem dojść do liczby 10. Ale dopiero myślenie na temat "jak je spoić" doprowadziło mnie do rozwiązania.
Tak, jedną mysz na wymiar można odpuścić, bo koduje butelki, z których nie pije reszta myszek. Gdy jest jedna zatruta butelka to nie jest to konieczne.

bert04 napisał(a): Teraz czekam, jak kolega uzasadni 9
Spoiler!
Odpowiedz
Było nas kiedyś czterech przyjaciół. Mieliśmy cztery sługi. Cztery kolory żeśmy mieli. Każdy swoimi drogami chadzał, każdy inaczej, ale taki już los. A potem się wszystko pozmieniało. Przybyło nas, ubyło barw. I każdy inaczej się ubiera, inaczej się nazywa, nawet z zaimkami nie wiadomo do końca. I każdy się prowadzi inaczej, niż onegdaj. Tylko ja taki sam jak przed X wiekami, zasadniczo nic nie zmieniłem. Ale właśnie o mnie mówią, że jestem jakiś inny, że ciężko moje kroki przewidzieć, nawet mnie przezywają za to. Mnie? Serio? Kim więc jestem?

żeniec napisał(a):
Spoiler!

Spoiler!
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
Zara, zara, skoro

Cytat:... Możemy to zrobić za pomocą testowych myszek.
... Jaką minimalną liczbę myszek trzeba poświęcić,
to dammy miał rację.

A nawet lepiej, przy dozie szczęścia może się obyć bez ofiar.
Bierzemy 999 myszek (ich liczba nie została ograniczona) i każdej dajemy spróbować z jednej butelki.
Padnie jedna lub żadna (gdyby zatruta była akurat ta 1000 butelka).

Chyba że znowy czegoś nie doczytałem Smutny
A nas Łódź urzekła szara - łódzki kurz i dym.
Odpowiedz
Sofeicz napisał(a): Zara, zara, skoro

Cytat:... Możemy to zrobić za pomocą testowych myszek.
... Jaką minimalną liczbę myszek trzeba poświęcić,
to dammy miał rację.

A nawet lepiej, przy dozie szczęścia może się obyć bez ofiar.
Bierzemy 999 myszek (ich liczba nie została ograniczona) i każdej dajemy spróbować z jednej butelki.
Padnie jedna lub żadna (gdyby zatruta była akurat ta 1000 butelka).

Chyba że znowy czegoś nie doczytałem Smutny

Faktycznie, jeżeli interpretować "poświęcić" nie jako "wykorzystać" ale "uśmiercić", to najlepszy efekt ma matryca jednowymiarowa. Minus jeden.

Ale zadanie miało też pytanie dodatkowe, co zrobić, jeżeli liczba zatrutych butelek nie jest określona. Tego jeszcze nikt nie podjął.

EDIT:

żeniec napisał(a): Mamy do podania gościom na przyjęciu 1000 butelek wina. Jedno z nich jest jednak zatrute, a że nie chcemy nikogo otruć, próbujemy namierzyć trefną butelkę.

Jeżeli brać zadanie ultra-dosłownie, to jest ono niewykonalne. Po wyrzuceniu jednej butelki mamy ich 999, więc cel podania 1000 butelek wina jest nieosiągalny.

Oczywiście można zadanie przekształcić w "1000 minus te zatrute". To jest oczywiste dla jednej butelki, ale przestaje być dla liczby nieokreślonej. Wariant jednowymiarowy (999 myszek) prowadzi do dokładnego namierzenia, ale też do maksymalnej liczby ofiar. W wariantach wielowymiarowych możemy ustalić, że wylewamy całą "płaszczyznę" sprawdzania, jeżeli jedna mysz zdechnie. Przy odrobinie szczęścia pozostanie nam parę butelek, które nie były w jakimś podzbiorze zatrucia. Przy odrobinie pecha wylewamy wszystko i kupujemy 1000 butelek na allegro. Ale tu bez podania jakichś górnych pułapów zatrucia vs. wyrzucania trudno o optymalizację.

EDIT 2:

bert04 napisał(a): Jeżeli więc zdechły myszy druga, trzecia, siódma i dziesiąta, to szukamy butelki 0110001001, czyli 393.

W wariancie "matrycowym" wyrzucamy butelki z każdą kombinacją tych myszy. Ponieważ zdechły 4 myszy, wyrzucamy 4^2-1=15 butelek. Konkretnie:

1
8
9
128
129
136
137
256
257
264
265
384
385
392
393

To chyba tyle. Ponieważ butelek jest mniej niż 1024, nie będzie przypadku 1111111111, więc parę butelek nam zostanie.

EDIT 3:

Maksymalna liczba zatrutych myszy: 10. Jeżeli zostanie przynajmniej jedno zero, to wyrzucamy 511 butelek (przykładowo dla 0111111111), zostaje nam 489. Jeżeli mamy pecha, wyrzucamy cały skład.
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
Sofeicz napisał(a): Zara, zara, skoro

Cytat:... Możemy to zrobić za pomocą testowych myszek.
... Jaką minimalną liczbę myszek trzeba poświęcić,
to dammy miał rację.

A nawet lepiej, przy dozie szczęścia może się obyć bez ofiar.
Bierzemy 999 myszek (ich liczba nie została ograniczona) i każdej dajemy spróbować z jednej butelki.
Padnie jedna lub żadna (gdyby zatruta była akurat ta 1000 butelka).

Chyba że znowy czegoś nie doczytałem Smutny
Warunek globalny to nie zabicie nikogo z gości. Mógłbym to powtarzać w każdym zdaniu, ale jest to nieestetyczne. Pytanie więc domyślnie brzmi "Jaką minimalną liczbę myszek trzeba poświęcić (wykorzystać, licząc się z tym, że być może wszystkie umrą), aby z pewnością namierzyć butelkę z zatrutym winem"

bert04 napisał(a): Jeżeli brać zadanie ultra-dosłownie, to jest ono niewykonalne. Po wyrzuceniu jednej butelki mamy ich 999, więc cel podania 1000 butelek wina jest nieosiągalny.
Jeśli brać jedno zdanie ultra-dosłownie i nie czytać reszty zagadki, to tak Oczko

bert04 napisał(a): Oczywiście można zadanie przekształcić w "1000 minus te zatrute".
Wywracanie oczami

bert04 napisał(a): To jest oczywiste dla jednej butelki, ale przestaje być dla liczby nieokreślonej. Wariant jednowymiarowy (999 myszek) prowadzi do dokładnego namierzenia, ale też do maksymalnej liczby ofiar. W wariantach wielowymiarowych możemy ustalić, że wylewamy całą "płaszczyznę" sprawdzania, jeżeli jedna mysz zdechnie. Przy odrobinie szczęścia pozostanie nam parę butelek, które nie były w jakimś podzbiorze zatrucia. Przy odrobinie pecha wylewamy wszystko i kupujemy 1000 butelek na allegro. Ale tu bez podania jakichś górnych pułapów zatrucia vs. wyrzucania trudno o optymalizację.
Ano, zagadka dla dowolnej ustalonej liczby butelek robi się dużo trudniejsza. Jeśli natomiast zawczasu nie znamy liczby zatrutych butelek i mamy mieć pewność, że znaleźliśmy wszystkie, to chyba znowu robi się już prosto.

Co do namierzania w pierwszym wariancie, to nie ma problemu, jeżeli tylko jakoś ponumeruje się butelki, choćby właśnie w systemie dwójkowym, a bity przyporządkowuje się myszom. Bardziej "konstrukcyjnie" wyobrażałem to sobie tak, że mam odcinek ponumerowanych butelek, dzielimy go na dwa równe odcinki (no, z dokładnością do jednej butelki) i butelki z jednego odcina dajemy do posmakowania pierwszej myszce. W kolejnym kroku bierzemy te dwa odcinki i w każdym z nich robimy to samo, tzn. dzielimy na, powiedzmy, lewą i prawą połowę, i lewe połowy dajemy kolejnej myszce. Kontynuujemy aż odcinki są 1-elementowe lub puste.
Odpowiedz
żeniec napisał(a): Co do namierzania w pierwszym wariancie, to nie ma problemu, jeżeli tylko jakoś ponumeruje się butelki, choćby właśnie w systemie dwójkowym, a bity przyporządkowuje się myszom. Bardziej "konstrukcyjnie" wyobrażałem to sobie tak, że mam odcinek ponumerowanych butelek, dzielimy go na dwa równe odcinki (no, z dokładnością do jednej butelki) i butelki z jednego odcina dajemy do posmakowania pierwszej myszce. W kolejnym kroku bierzemy te dwa odcinki i w każdym z nich robimy to samo, tzn. dzielimy na, powiedzmy, lewą i prawą połowę, i lewe połowy dajemy kolejnej myszce. Kontynuujemy aż odcinki nie są 1-elementowe lub puste.

Sorki, ale to było rozwiązanie Sofeicza. Nie funkcjonowało dla jednej butelki, nie będzie też dla więcej niż jedna. Obawiam się, że bez określenia konkretnej liczby zatrutych butelek musimy sprawdzać każdą (999 myszy). Być może statystyka pomogłaby przy rozwiązaniu tego dylematu, ale tylko przy pozbyciu się / rozluźnieniu limitu czasu możemy wymyślić jakieś alternatywne scenariusze.

EDIT: Moje rozwiązanie "binarne" funkcjonuje, jeżeli określimy, że butelek zatrutych jest maksymalnie 9, wtedy w najgorszym przypadku wylewamy 511 (patrz wyżej). Dla 10+ zatrutych butelek jest możliwość, że wszystkie myszy padną. Na ile prawdopodobna, nawet nie chce mi się liczyć. I nawet nie potrafiłbym, statystyka to nie moja działka.


Podbijam:

bert04 napisał(a): Było nas kiedyś czterech przyjaciół. Mieliśmy cztery sługi. Cztery kolory żeśmy mieli. Każdy swoimi drogami chadzał, każdy inaczej, ale taki już los. A potem się wszystko pozmieniało. Przybyło nas, ubyło barw. I każdy inaczej się ubiera, inaczej się nazywa, nawet z zaimkami nie wiadomo do końca. I każdy się prowadzi inaczej, niż onegdaj. Tylko ja taki sam jak przed X wiekami, zasadniczo nic nie zmieniłem. Ale właśnie o mnie mówią, że jestem jakiś inny, że ciężko moje kroki przewidzieć, nawet mnie przezywają za to. Mnie? Serio? Kim więc jestem?
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
żeniec napisał(a): Co do namierzania w pierwszym wariancie, to nie ma problemu, jeżeli tylko jakoś ponumeruje się butelki, choćby właśnie w systemie dwójkowym, a bity przyporządkowuje się myszom. Bardziej "konstrukcyjnie" wyobrażałem to sobie tak, że mam odcinek ponumerowanych butelek, dzielimy go na dwa równe odcinki (no, z dokładnością do jednej butelki) i butelki z jednego odcina dajemy do posmakowania pierwszej myszce. W kolejnym kroku bierzemy te dwa odcinki i w każdym z nich robimy to samo, tzn. dzielimy na, powiedzmy, lewą i prawą połowę, i lewe połowy dajemy kolejnej myszce. Kontynuujemy aż odcinki są 1-elementowe lub puste.
Ale dałeś jedną godzinę na znalezienie trefnej butelki i jednocześnie tę samą jedną godzinę na swierdzenie zgonu myszki.
Ergo, takie założenie wyklucza sposoby iteracyjne.
Musi być jednorazowa degustacja i szlus.
A nas Łódź urzekła szara - łódzki kurz i dym.
Odpowiedz
Sofeicz napisał(a): Ale dałeś jedną godzinę na znalezienie trefnej butelki i jednocześnie tę samą jedną godzinę na swierdzenie zgonu myszki.
Ergo, takie założenie wyklucza sposoby iteracyjne.
Musi być jednorazowa degustacja i szlus.

Teoretycznie można spróbować to zrobić na raz. Zgodnie z zasadą sigma n->x a^n =a^n+1 - 1.

Czyli 1+2+4+8+16+32+64+128+256+512=1023.
Po poprawce mamy 1+2+4+8+16+32+64+128+256+488=1000.
Nadal musimy wykorzystać 10 myszy. I nadal możemy stracić wszystko, jeżeli zatrutych butelek jest więcej niż 9. Ale przy ograniczeniu do 9 zostaje minimum jedna. Maksimum 488, choć oczywiście można zaryzykować i odjąć te nadwyżkowe 23 od innej liczby.

(Edit: nazwijmy to metodą "Gaussową", chyba wiadomo, dlaczego)


bert04 napisał(a): EDIT: Moje rozwiązanie "binarne" funkcjonuje, jeżeli określimy, że butelek zatrutych jest maksymalnie 9, wtedy w najgorszym przypadku wylewamy 511 (patrz wyżej). Dla 10+ zatrutych butelek jest możliwość, że wszystkie myszy padną. Na ile prawdopodobna, nawet nie chce mi się liczyć. I nawet nie potrafiłbym, statystyka to nie moja działka.

To rozwiązanie zawiera pewien oczywisty błąd, przy 9 martwych myszach zostaje tylko jedna butelka. W podanym przykładzie (0111111111) jest to butelka o numerze 512 (1000000000), cała reszta jest wylewana. Podobnie dla innych rozwiązań, ilość ocalałych butelek będzie potęgą o podstawie 2 a bazie myszy przeżyłych minus jeden (2n-1). Przy czterech martwych myszach, jak w pierwszym przykładzie to byłoby 2^6-1=63.

EDIT 2: ... to dokładnie tyle, co minimalna liczba dla metody "Gaussowej". 1+2+4+8+16+32=63. Natomiast maksymalna liczba to 1000-15=985. Wydaje się więc, że metoda "Gaussowa" w najgorszym przypadku daje takie same wyniki, jak metoda binarna, a w najlepszym pozwala na zachowanie większości zbioru.
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
Sofeicz napisał(a): Ale dałeś jedną godzinę na znalezienie trefnej butelki i jednocześnie tę samą jedną godzinę na swierdzenie zgonu myszki.
Ergo, takie założenie wyklucza sposoby iteracyjne.
Musi być jednorazowa degustacja i szlus.
No i jest, niczego nie trzeba iterować, tylko ponumerować też myszy. Pierwsza myszka pije z butelek 1-500, druga 1-250 i 501-750, itd. Wnioskujemy która butelka była trefna na podstawie numerów myszek, które umarły, a nie kolejności umierania.

To też rozwiązuje bercie04 wątpliwości Twoje wątpliwości w wariancie z jedną butelką.

Co do zagadki - foton?
Odpowiedz
żeniec napisał(a): No i jest, niczego nie trzeba iterować, tylko ponumerować też myszy. Pierwsza myszka pije z butelek 1-500, druga 1-250 i 501-750, itd. Wnioskujemy która butelka była trefna na podstawie numerów myszek, które umarły, a nie kolejności umierania.

Zadnych "itd", tutaj konkretnie trzeba. Każda mysz wypija połowę butelek, ale każda według innego wzoru. Gdyby butelek było tylko cztery, pierwsza mysz piłaby 1+2, druga 1+3. Dla matrycy dwuwymiarowej to starczy, otrzymujemy więc:

1,2
3,4

Jeżeli więc przykładowo zdechną obie myszy, to dla zadania początkowego (jedna butelka zatruta) wyrzucamy nr. 1. A jeżeli nie zdechnie żadna, to butelkę 4.

Dla zadania rozszerzonego (liczba nieokreślona) i dwóch zdechniętych myszy wyrzucamy 1,2,3. Dodajmy też, że brak sprawdzenia butelki nr. 4 w powyższym przykładzie stanowi o słabości tej metody, musimy ją wyrzucać zawsze. Albo sprawdzić dodatkową myszą.

Podobnie jest w Twojej wersji od 1 do 1000. Dla zadania początkowego Twoja metoda nie różni się od metody binarnej, poza szczególną cechą, że ostatnia butelka nie będzie sprawdzana. Stosujemy warunek AND dla zbiorów. Jeżeli zdechnie 10 myszy, wyrzucamy butelkę nr. 1, jeżeli żadna, butelkę nr. 1000. Schody zaczynają się przy zadaniu rozszerzonym. Butelkę 1000 należy wyrzucić lub sprawdzić dodatkową (jedenastą) myszą. Lub w jakiś inny sposób zmienić metodę "połowienia połowienia" (przy standardowym nr 1000 jest zawsze butelką nietestowaną). Obowiązuje warunek OR dla zbiorów, tylko klasyfikowanie jest trudniejsze. Przy 9 zdechłych myszach prawdopodobnie zostanie tylko jedna butelka (999), w zależności od konkretnej metodyki podziału.

Cytat:To też rozwiązuje bercie04 wątpliwości Twoje wątpliwości w wariancie z jedną butelką.

Metoda funkcjonuje dla jednej butelki bez zarzutu jako wariant metody binarnej.


Cytat:Co do zagadki - foton?

Nie, i nawet nie wiem, na jakiej zasadzie miałby to być foton.
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
bert04 napisał(a): Zadnych "itd", tutaj konkretnie trzeba. Każda mysz wypija połowę butelek, ale każda według innego wzoru.
Konkretnie, to konstrukcja z odcinkami była. Niech [latex]I_\emptyset=[1,1000][/latex] i dla skończonego ciągu [latex]0-1[/latex] [latex]\sigma[/latex] robimy [latex]I_{\sigma^\frown 0}=[\min I_\sigma, \lfloor\frac{\min I_\sigma+\max I_\sigma}{2}\rfloor][/latex] oraz [latex]I_{\sigma^\frown 1}=[\lfloor\frac{\min I_\sigma+\max I_\sigma}{2}\rfloor +1, \max I_\sigma][/latex]. Następnie kładziemy [latex]A_1=I_0[/latex] i [latex]A_n=\bigcup\{I_{\sigma^\frown 0}: \sigma\in 2^{n-1}\}[/latex] dla [latex]n>0[/latex]. Zbiór [latex]A_i[/latex] to numery butelek, którymi częstujemy myszę [latex]i[/latex]. Generalnie nie ma co kontynuować tych konstrukcji dla [latex]n>10[/latex] Częstujemy równocześnie wszystkie myszy, czekamy godzinę i odczytujemy skończony ciąg [latex]\sigma[/latex] taki, że [latex]\sigma(i)=0 \Leftrightarrow i[/latex]-ta myszka nie żyje. Jeśli [latex]I_\sigma\neq\emptyset[/latex], to ma butelkę z trucizną. W przeciwnym razie bierzemy najdłuższe obcięcie [latex]\sigma'\subseteq \sigma[/latex], że [latex]I_{\sigma'}[/latex] jest niepuste i ten zbiór zawiera butelkę z trucizną.

bert04 napisał(a): Dla zadania rozszerzonego (liczba nieokreślona) i dwóch zdechniętych myszy wyrzucamy 1,2,3. Dodajmy też, że brak sprawdzenia butelki nr. 4 w powyższym przykładzie stanowi o słabości tej metody, musimy ją wyrzucać zawsze. Albo sprawdzić dodatkową myszą.

Podobnie jest w Twojej wersji od 1 do 1000. Dla zadania początkowego Twoja metoda nie różni się od metody binarnej, poza szczególną cechą, że ostatnia butelka nie będzie sprawdzana. Stosujemy warunek AND dla zbiorów. Jeżeli zdechnie 10 myszy, wyrzucamy butelkę nr. 1, jeżeli żadna, butelkę nr. 1000. Schody zaczynają się przy zadaniu rozszerzonym. Butelkę 1000 należy wyrzucić lub sprawdzić dodatkową (jedenastą) myszą. Lub w jakiś inny sposób zmienić metodę "połowienia połowienia" (przy standardowym nr 1000 jest zawsze butelką nietestowaną). Obowiązuje warunek OR dla zbiorów, tylko klasyfikowanie jest trudniejsze. Przy 9 zdechłych myszach prawdopodobnie zostanie tylko jedna butelka (999), w zależności od konkretnej metodyki podziału.
Moja metoda w zasadzie niczym się nie różni od binarnej, po prostu odcinkami wskazuję które butelki sprawdzam. Przy rozszerzonej mamy niejednoznaczność niezależnie od metody, bo śmierć lub przeżycie myszy na ostatnim bicie nic oznacza dla "sąsiedniej" butelki. Z tego powodu techniką połowienia, jeśli mamy 999 zatrutych butelek, to trzeba sprawdzić... wszystkie, oprócz jednej, kombinacje.

bert04 napisał(a): Nie, i nawet nie wiem, na jakiej zasadzie miałby to być foton.
Bardzo luźno parę rzeczy pasuje do bozonów cechowania. Zwłaszcza z tymi kolorami, sługami (oddziaływania?) itd.
Odpowiedz
@żeniec

Nadal nie łapię, jakie zalety miałaby mieć Twoja metoda, jeżeli to tylko inny wariant binarności. I nawet nie jestem pewien, czy też chcesz użyć 10 myszy, czy więcej.

Moim zdaniem dla zadania "liczba zatrutych butelek n jest nieokreślona" nie ma rozwiązania poniżej 999 myszy. Ale być może jest jakaś metoda na namierzanie butelek zatrutych, kiedy n jest określona i n>1? Trzeba by pogłówkować trochę. I może wyjdzie, jak liczba myszy m jest zależna od n. Ale to może później.

A ponieważ minął dzień od zadania zagadki, dam podpowiedź. Są trzy miejsca zagadki, które mają podwójne dno. To znaczy jest ich więcej, ale te trzy musiałem zakamuflować mocniej, gdyż inaczej zbyt szybko  mogą naprowadzić na właściwy trop:

bert04 napisał(a): Było nas kiedyś czterech przyjaciół. Mieliśmy cztery sługi. Cztery kolory żeśmy mieli. Każdy swoimi drogami chadzał, każdy inaczej, ale taki już los. A potem się wszystko pozmieniało. Przybyło nas, ubyło barw. I każdy inaczej się ubiera, inaczej się nazywa, nawet z zaimkami nie wiadomo do końca. I każdy się prowadzi inaczej, niż onegdaj. Tylko ja taki sam jak przed X wiekami, zasadniczo nic nie zmieniłem. Ale właśnie o mnie mówią, że jestem jakiś inny, że ciężko moje kroki przewidzieć, nawet mnie przezywają za to. Mnie? Serio? Kim więc jestem?
Wszystko ma swój czas
i jest wyznaczona godzina
na wszystkie sprawy pod niebem
Spoiler!
Koh 3:1-8 (edycje własne)
Odpowiedz
bert04 napisał(a): Nadal nie łapię, jakie zalety miałaby mieć Twoja metoda, jeżeli to tylko inny wariant binarności.
Przecież nie mówię, że ma jakąś przewagę nad binarną. Jest równoważna, po prostu mnie się łatwiej myśli o odcinkach i zstępujących przekrojach.

bert04 napisał(a): I nawet nie jestem pewien, czy też chcesz użyć 10 myszy, czy więcej.
Skąd niepewność? Mysz trzeba użyć tyle, ile jest zbiorów [latex]A_i[/latex], a tych jest sufit z [latex]\log_2 1000[/latex].
Odpowiedz


Skocz do:


Użytkownicy przeglądający ten wątek: 1 gości