Matematyka.pl

Pewien okrutny król mial w swojej piwnicy 1000 beczek wina. Pewna królowa z
sąsiedniego państwa postanowiła zgładzić tego złego krola i wyslala swego
sługe, by zatruł wino w jego winnej piwnicy. Niestety straznicy krola zlapali
intruza, gdy ten zdolal skazic trucizna zaledwie jedna beczke wina. Nie
wiadomo, do ktorej beczki nalal trucizny poslaniec krolewny i nie ma szans by
sie o tym dowiedziec, jako ze ten popelnil wnet samobojstwo. Wiadomo jedynie,
ze trucizna jest o niezwyklej mocy i nawet w rozcienczeniu 1:100000 (milion
razy) dziala smiertelnie. Wiadomo rowniez, ze ta trucizna jest tak perfidna,
ze objawia sie dopiero po 31 dniach, tzn. dopiero 31 dnia pada sie od niej
trupem. Krol, jak tylko sie o tym dowiedzial wpadl we wscieklosc, bo za piec
tygodni szykowala sie na dworze Wielka Uczta, na ktora przygotowano wlasnie
te 1000 beczek wina. Zawezwal wiec do siebie swego nadwornego medrca i rzekl
tymi slowy:

- W wiezieniu jest 10 skazancow, mozesz wziac ich i zrob wszystko, bym na
czas Wielkiej Uczty wiedzial, gdzie jest trucizna.
Na to medrzec jako, ze byl rownie madry jak i szlachetny odrzekl:
- Panie a czy ci skazancy, ktorzy przezyja te probe, zostana przez Ciebie
uniewinnieni?
- Niech i tak bedzie. Ci, ktorzy sie nie otruja, moga isc wolno.

Po tych slowach medrzec wymyslil taki sposob na odnalezienie zatrutej beczki,
by zdazyc na czas Wielkiej Uczty, a zarazem by przezylo przynajmniej.....
No wlasnie, ilu skazancow moze na pewno uratowac?

To ja to zrobiłem w taki sposób (jak źle to mnie popraw , albo po prostu powiedz )

Przyjmijmy, że Ty jesteś tym mędrcem (łatwiej mi będzie myśleć )

Pierwszego dnia dajesz każdemu spróbować ze 100 beczek (każdemu ze 100 innych)
Drugiego dnia odstawiasz po jednej beczce od każdego na bok (podpisując je) i jak każdemu zostaje po 99 beczek, to rozdajesz je po równo dla reszty (czyli beczki 1 rozdzielasz po 9 dla każdego ) i tak wszyskie
Trzeciego dnia odstawiasz od każdego ludzika po 9 beczek (po jednej, którą dostali od pozostałych) i pozostałe 90 dzielisz w następujący sposób (biorąc na przykład więźnia nr.1. Ma on po 10 beczek od każdego innego więźnia, które można rozdzielić 8 więźniom. Czyli dajemy każdemu po jednej (18 zostawiając na następny dzień) )
Czwartego dnia dajesz pozostałe 18 więźniom (np. Beczki które były od drugiego (dwie) dajesz 3 i 4 i tak dalej) i patrzysz jak umierają

31 dnia na pewno umrze jeden więzień.
32 dnia jak nie umrze żaden więzień, to jż wiadomo gdzie była trucizna (w beczce odstawionej na początku), jeśli umrze następny, to czekamy dalej
33 dnia jeśli nikt nie umrze, to znaczy, że trucizna była w beczułce odstawionej za drugim razem (tam, gdize odstawialiśmy po 9 wystarczy znaleźć tą, która była dostarczona, przez wcześniejszego trupa ), jeśli ktoś umrze to patrzymy od kogo dostawał beczki i robimy ścieżkę do pierwszego zgonu i mamy beczkę
34 dnia jeśli nikt nie umrze, to znaczy, że spostrzeżenia z 33 dnia były prawdziwe, jeśli natomiast ktoś umrze, to sprawdzamy tak samo ścieżkę, jak dnia 33 w przypadku zgonu.

Mamy beczkę i 1-3 więźniów martwych (czyli 70-90% skuteczności, matura zdana )

powiedz, że dobrze (jak tylko zrozumiesz co tam wypociłem, bo drugi raz sam tego nie zrozumiem )

pozdrawiam artak_serkses

artak_serkses pisze: Pierwszego dnia dajesz każdemu spróbować ze 100 beczek (każdemu ze 100 innych)
Drugiego dnia odstawiasz po jednej beczce od każdego na bok (podpisując je) i jak każdemu zostaje po 99 beczek, to rozdajesz je po równo dla reszty (czyli beczki 1 rozdzielasz po 9 dla każdego ) i tak wszyskie....

...31 dnia na pewno umrze jeden więzień.
32 dnia jak nie umrze żaden więzień, to jż wiadomo gdzie była trucizna (w beczce odstawionej na początku), jeśli umrze następny, to czekamy dalej ...

masz rację to twoje wyjaśnienie jest trochę zagmatwane i ma błędy(ma już je na początku więć dalej pewnie też może być coś nie tak ale już dalej nie sprawdzałem jak znalazłem na początku)...cytowałem tylko ten twój początek bo to się tego tyczy a więc:
gdy w drugim dniu po odstawieniu jednej beczki każdy da każdemu po 9 beczek to ogólna liczba dla każdego sie nie zmieni czyli 99 ALE dając 9 osobom po 9 beczek to jest 81 czyli każdemu zostanie po 18 beczek które próbował w pierwszym dniu...z tego wynika że jak w drugim dniu nikt nie umrze to ta zatruta beczka może być zarówno w tej odstawionej beczce jak i w tych 18 które próbował ten sam gość...
bardziej przejrzysta taktyka mile widziana

Znalazłem sposób na uratowanie przynajmniej siedmiu więźniów:

Każdą beczkę oznaczamy trzema symbolami ze zbioru: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A} (np. 62A, 409 itp.), tak, że żaden symbol z wyjątkiem 0 nie może się pojawić wielokrotnie na jednej beczce.
Zauważmy, że mamy 11*10*9 = 990 kombinacji, plus układy z kilkoma zerami, co da ostatecznie 1021 różnych układów. Możemy zatem przyporządkować każdej beczce inny układ.
Każdy symbol oznacza innego więźnia (przy czym A oznacza dziesiątego więźnia, a 0 odstawienie beczki i nie dawanie jej nikomu). W pierwszych trzech dniach postępujemy z każdą beczką według jej kodu. (tzn. np. beczkę 62A pierwszego dnia dajemy więzniowi szóstemu, drugiego dnia więźniowi drugiemu, trzeciego dnia więźniowi dziesiątemu.) W ten sposób więźniowie umarli w 31, 32 i 33 dzień jednoznacznie wyznaczą zatrutą beczkę i zginie ich co najwyżej 3.

Uważam, że nie da się z pewnością uratować 8 więźniów.

Arbooz pisze:Znalazłem sposób na uratowanie przynajmniej siedmiu więźniów:

Każdą beczkę oznaczamy trzema symbolami ze zbioru: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A} (np. 62A, 409 itp.), tak, że żaden symbol z wyjątkiem 0 nie może się pojawić wielokrotnie na jednej beczce.
Zauważmy, że mamy 11*10*9 = 990 kombinacji, plus układy z kilkoma zerami, co da ostatecznie 1021 różnych układów. Możemy zatem przyporządkować każdej beczce inny układ.
Każdy symbol oznacza innego więźnia (przy czym A oznacza dziesiątego więźnia, a 0 odstawienie beczki i nie dawanie jej nikomu). W pierwszych trzech dniach postępujemy z każdą beczką według jej kodu. (tzn. np. beczkę 62A pierwszego dnia dajemy więzniowi szóstemu, drugiego dnia więźniowi drugiemu, trzeciego dnia więźniowi dziesiątemu.) W ten sposób więźniowie umarli w 31, 32 i 33 dzień jednoznacznie wyznaczą zatrutą beczkę i zginie ich co najwyżej 3.

Uważam, że nie da się z pewnością uratować 8 więźniów.

hmmm...coś nie mogę się z tym zgodzić ponieważ:
ok bierzemy zbiór 10-elementowy(opuszczam narazie 0) z którego którego wybieramy 3 elementy które tworzą nam oznaczenie beczki a więc wariacje bez powtórzeń:
10!/(10-3)!=720 kombinacji(a nie 990)
następnie wszystkie możliwe kombinacje z jednym 0 a więc wszystkie kombinacje 2 elementów plus dodanie 0 na początku póżniej w środku i w końcu na końcu tych kombinacji:
10!/(10-2)!=90 * 3 =270 kombinacji...
to nam daje w sumie 990 kombinacji a mamy 1000 beczek...

dagoth a gdzie wciąłeś wariacje z 0 występującym dwa lub trzy razy? Według mnie rozwiązanie Arbooza jest dobre i mógłbyś się już nie czepiać. To że ktoś czasem wymyśli lepsze rozwiązanie od nas nie oznacza że trzeba go zaraz negować

dagoth pisze:

artak_serkses pisze: Pierwszego dnia dajesz każdemu spróbować ze 100 beczek (każdemu ze 100 innych)
Drugiego dnia odstawiasz po jednej beczce od każdego na bok (podpisując je) i jak każdemu zostaje po 99 beczek, to rozdajesz je po równo dla reszty (czyli beczki 1 rozdzielasz po 9 dla każdego ) i tak wszyskie....

...31 dnia na pewno umrze jeden więzień.
32 dnia jak nie umrze żaden więzień, to jż wiadomo gdzie była trucizna (w beczce odstawionej na początku), jeśli umrze następny, to czekamy dalej ...

masz rację to twoje wyjaśnienie jest trochę zagmatwane i ma błędy(ma już je na początku więć dalej pewnie też może być coś nie tak ale już dalej nie sprawdzałem jak znalazłem na początku)...cytowałem tylko ten twój początek bo to się tego tyczy a więc:
gdy w drugim dniu po odstawieniu jednej beczki każdy da każdemu po 9 beczek to ogólna liczba dla każdego sie nie zmieni czyli 99 ALE dając 9 osobom po 9 beczek to jest 81 czyli każdemu zostanie po 18 beczek które próbował w pierwszym dniu...z tego wynika że jak w drugim dniu nikt nie umrze to ta zatruta beczka może być zarówno w tej odstawionej beczce jak i w tych 18 które próbował ten sam gość...
bardziej przejrzysta taktyka mile widziana

Tfu literówka miało być, że dajesz po 11 (tak, żeby było po te 99 dla każdego)

Bardziej przejrzyście mówisz ?? Ciężko będzie :D Ale spróbuję:

Masz 10 więźniów (ABCDEFGHIJ) i 1000 beczek :)
Rozdzielasz beczki tak: 100A, 100B, 100C, ... Jak każdy spróbuje ze swoich 100 beczek, to odstawiasz po jednej (tak, że każdy ma 99)
Drugi dzień: 99A rozdzielasz na 9 osób (czyli po 11 ), tak że każdy ma 99 beczek, z czego A ma: 11B, 11C, 11D, 11E, 11F, 11G, 11H, 11I, 11J.
Próbują i następnie odstawiasz po 9 od każdego, tak, że ten nasz więzień A ma: 10B, 10 C, 10D, 10E, 10F, 10G, 10H, 10I, 10J
trzeciego dnia rozdzielasz beczki w ten sposób, że po dwie zostawiasz na czwarty dzień, a po 8 dajesz: 8B->dla->CDEFGHIJ, 8C->dla->BDEFGHIJ itd.
czwartego dnia rozdzielasz te, które odłożyłeś dzień wcześniej (2*9*10) w sposób taki, jak dzień wcześniej (czyli 2B->CD 2C->DE itd. ). Chodzi o to, zeby podczas tasowania tymi beczkami jeden gostek nie miał dwa razy tej samej beczki.

A kille sprawdzasz tak jak post wcześniej (mam nadzieję, że teraz nie ma żadnych głupich literówek/cyfrówek i że jest zrozumiale namazane )

DEXiu pisze:dagoth a gdzie wciąłeś wariacje z 0 występującym dwa lub trzy razy?

No właśnie. Zauważ dlaczego przy przy cyfrach musimy zastosować kombinacje bez powtórzeń: Chodzi tu tylko o to, żeby nie wyszło na to, że jakiś więzień musiałby umrzeć dwa razy (np. przy 141 pierwszy więzień musi umrzeć trzydziestego pierwszego i trzydziestego trzeciego dnia)
A układy z wieloma zerami jak najbardziej grają i to właśnie one dopełniają nam do 1000.

BTW: idea mojego rozwiąznia jest bardzo podobna do idei artaka_serksesa

wiem wiem...czepiam się a nie zauważyłem że tam jest że dopełniasz kombinacjami z dwoma zerami ....gratz dla was...
btw:ja też nie mogłem uratować więcej niż siedmiu więźniów...