zadanie AS: To następne zadanie,ale trudne.Parę lat temu już je podawałem,ale ponawiam z uwagi na bardzo ciekawe rozwiązanie.Prośba do tych którzy już znają z poprzedniej edycji,by na razie nie ujawniali rozwiązania i dali szanse tym nowym. Oto zadanie Pustynią wędrowała karawana złożona z 1000 wielbłądów. Każdy z nich dźwigał skrzynię zawierającą 1000 złotych monet. Każda moneta ważyła 10 j.w. (jedn.wagowych). W pobliżu oazy na karawanę napadła banda rabusiów (oby ich Allach pokarał),skradli 1 skrzynię wstawiając w to miejsce inną skrzynię zawierającą 1000 takich samych monet ale fałszywych. Bandę wkrótce złapano,skrzynię odzyskano.Przy pomocy łagodnych perswazji w postaci bicia w pięty,zeznali że każda moneta fałszywa była o 1 j.w. lżejsza,czyli ważyła 9 j.w, ale nie potrafili wskazać skrzyni którą w zamian wstawili. Posiadano jedną wagę,ale ważenie po kolei każdej skrzyni zajęłoby dużo czasu,a czas naglił. W oazie mieszkał kadi znany ze swojej mądrości i umiejętności matematycznych.Sprowadzono go i przedstawiono problem. Spytał się czy będzie mu wolno skrzynie otworzyć.Uzyskał na to zgodę. Po długim namyśle orzekł,że dokonując tylko jednego ważenia potrafi wskazać miejsce skrzyni z fałszywymi monetami. Jak on to zrobił? Uwaga: Wszystkie skrzynie i monety wzrokowo są nierozróżnialne.

Saizou : najprościej.... zapytać Kadiego

ZKS: Jeżeli mógł skrzynie otworzyć to wydaje mi się, że zasada ta polegała na wzięciu z pierwszej skrzyni tylko jednej monety, z drugie dwie, z trzeciej trzy i tak do tysięcznej skrzyni, z której wziął tysiąc monet. Teraz jeżeli w pierwszej skrzyni były fałszywki to waga powinna wskazać 5 004 999, jeżeli druga skrzynia zawierała podróbki to waga wskaże 5 004 998, a jeżeli tysięczna skrzynia to 5 004 000. Nie wiem, czy dobrze myślę.

J: ....wykonał tylko jedno ważenie....

AS: Tak,ale to nie było jedno ważenie,tylko w najgorszym przypadku 1000 ważeń,gdy tą fałszywą była ostatnia skrzynia.

ZKS: Jest jedno ważenie, ponieważ kładzie je od razu na wagę. Tak, więc ta skrzynia, która zawiera fałszywki dojdziemy poprzez odjęcie od 5 005 000 wyniku, który wskazuje waga. Przykładowo 5 005 000 − 5 004 777 = 223, zatem skrzynia zawierająca podróbki to skrzynia, z której wzięliśmy 223 monety.

J: może nie nadążam ... równie dobrze może ważyć po kolei każdą skrzynię do czasu, aż natrafi na lżejszą... ( bez wyciagania monet )

ZKS: Na wagę kładzie je wszystkie na raz. Podałem przepis jak to zrobił według mnie. Wziął jedną monetę z pierwszej skrzyni, z drugiej dwie, z trzeciej trzy i tak do tysięcznej skrzyni, z której wziął tysiąc monet i kładzie je wszystkie naraz na wagę.

ZKS: Tylko, wtedy nie będzie jednego ważenia w Twoim wypadku J.

J: OK ... numeruje skrzynie i po różnicy wagi wskazuje właściwy numer

ZKS: Jeżeli wszystkie były by prawdziwe monety to waga powinna nam wskazać 10 + 20 + 30 + ... + 10 000 = 5 005 000 10 wagi z pierwszej skrzyni 20 wagi z drugiej skrzyni 30 wagi z drugiej skrzyni 10 000 wagi z tysięcznej skrzyni, teraz jeżeli pierwsza zawiera podróbki to mamy 9 + 20 + 30 + ... + 10 000 = 5 004 999, jeżeli druga to mamy 10 + 18 + 30 + ... + 10 000 = 5 004 998 jeżeli trzecia to mamy 10 + 20 + 27 + ... + 10 000 = 5 004 997 jeżeli tysięczna to mamy 10 + 20 + 30 + ... + 9 000 = 5 004 000.

ZKS: Mogę się mylić z tym moim pomysłem, ale takie coś mi przyszło do głowy, jeżeli mógł je otworzyć i ważyć tylko jeden raz.

ZKS: AS jak możesz to potwierdź rozwiązanie, bo jeżeli złe to chyba się poddaję.

AS: Ale zawsze nie jest to jedno ważenie,tylko kilka prób aż trafię na tą właściwą.

ZKS: Hmm, ale powiedz mi jak nie jest to jedno ważenie, bo już sam się gubię.

ZKS: J pomóż, bo Ty chyba zrozumiałeś o co mi chodzi.

J: @ZKS ... nie robi ... Testuje na 5−ciu skrzyniach , w każdej 10 kul o wadze 1 kg, a w jednej 10 kul o wadze 9 kg przykład: 3 skrzynia wadliwa 9,9 + 9,8 + 8,7 + 9,6 + 9,5 = 47,5 kg 1 skrzynia wadliwa: 8,9 + 9,8 + 9,7 + 9,6 + 9,5 = 47,5 kg 5 skrzynia wadliwa: 9,9 + 9,8 + 9,7 + 9,6 + 8,5 = 47,5 kg .....

J: żle się wyraziłem ... w czterech skrzyniach 10 kul o wadze 1 kg każda, a w jednej (wadliwej) 10 kul o wadze 0.9 kg każda

AS: Pierwsze co trzeba zrobić to skrzynie ponumerować od 1 do 1000. Następnie z skrzyni oznaczonej numerem 1 pobrać 1 monetę, z skrzyni nr 2 dwie monety itd aż do ostatniej gdzie pobrano 1000 monet.Wszystko układać osobnymi stosami na szalce wagi, by później wyłapać monety fałszywe. Gdyby wszystkie monety w ilości 1000*1000 były prawdziwe, to ich waga wyniosłaby 1000*1000*10 j.w. Jeżeli skrzynia np. z numerem 56 zawierała monety fałszywe ubytek wagi wyniósłby 56 j.w.. a jeżeli 345 to 345 j.w. Oto całe rozwiązanie.

J: wycofuję post 11:28 .... napisałem bzdury

ZKS: Ważymy tylko jeden jedyny raz. Teraz taki jaki wynik otrzymamy to waga wskaże nam, która skrzynia zawiera podróbki. Jeżeli wszystkie skrzynia zawierały by prawdziwe monety to waga wskaże wynik 5 005 000, ponieważ z pierwszej braliśmy jedną, z drugiej dwie i tak dalej 10 + 2 * 10 + 3 * 10 + ... + 1000 * 10 = 5 005 000, ale jeżeli, któraś ze skrzyń zawiera podróbki i da nam wynik to należy od 5 005 000 odjąć wynik jaki wskaże nam waga, wtedy wiemy, która skrzynia ma podróbki 5 005 000 − x = y 10 + 2 * 10 + 3 * 10 + ... y * 9 + ... 1000 * 10 = x, czyli skrzynia y zawiera podróbki, ponieważ z niej wzięliśmy y monet, które ważą o 1 mniej od prawdziwych monet. Teraz podam na konkretnym przykładzie waga wskazuje nam wynik 5 004 555, zatem 5 005 000 − 5 004 555 = 445, więc skrzynia 445 zawiera podróbki, ponieważ 10 + 2 * 10 + 3 * 10 + ... + 445 * 9 + 446 * 10 + ... + 1 000 * 10 = 5 004 555.

J: @AS ... przecież dokładnie takie rozwiazanie podał ZKS

ZKS: To przecież tak pisałem AS, oczywiście nie pisałem o numerowaniu skrzyń, ale to nawet logiczne, żeby później się nie pomylić, która skrzynia to która.

ZKS: O numerowaniu wspomniał J w moim rozwiązaniu.

AS: Mam tylko takie zastrzeżenie,że nie wiem która skrzynia zawierała fałszywe monety.A oto przecież chodziło.

ZKS: J wspomniał o ponumerowaniu skrzyń w moim rozwiązaniu i tyle.

Kacper: Ja uważam, że szybciej położę 1000 skrzyń po kolei na wadze niż będę liczył 557 monet