Dodaj do ulubionych

Wybrakowane naboje - zadanie konkursowe nr 3

06.10.03, 13:55
Przedstawiam trzecią łamigłówkę w naszej zabawie o 200 PLN z cyklu "Konkurs
Łamigłówkarski, Wrzesień 2003" (po szczegóły zajrzyj do odpowiedniego wątku
na tym forum):

W pewnym policyjnym magazynie z amunicją doszło do fatalnej pomyłki. Otóż w
magazynie tym znajdowały się pudełka z nabojami do służbowych pistoletów
pakowane po osiem sztuk w jednym pudełku. Nieszczęśliwie się tak zdarzyło, że
do całego składu wmieszało się jedno pudełko z wybrakowanymi nabojami-
niewybuchami. Magazynier dostał polecenie znalezienia i odrzucenia tego
pudełka. Wszystkie pudełka wyglądały identycznie i wszystkie dobre naboje
miały dokładnie tę samą masę, natomiast niesprawne naboje, choć wszystkie też
ważyły dokładnie tyle samo, były lżejsze od tych dobrych, jako że nie
posiadały spłonki. Nieznana natomiast była waga dobrego i złego naboju. Do
dyspozycji magazyniera podstawiono wagę z sąsiedniego posterunku, w którym
też zmagano się z podobnym problemem, dlatego zastrzeżono, że wagę udostępnia
się tylko na trzy ważenia.
Waga jest dwuszalkowa i bardzo pojemna, tzn. na każdej z jej szalek można
umieścić dowolną ilość nabojów. Waga ta może też bez problemu wychwycić
różnicę w wadze między dobrym a złym nabojem i dokładnie określić jakiej
wielkości jest ta różnica. Magazynier ma więc możliwość wykonania trzech
ważeń, po czym musi zdecydować, które ośmiopociskowe pudełko zawiera
niesprawne naboje. Może w tym celu pudełka otwierać, wybierać z każdego
dowolną ilość nabojów, znaczyć je flamastrem, kłaść na wagę itd. Ma tu
całkowitą dowolność, ale nie może korzystać z niczego więcej oprócz tej wagi.

Pytanie brzmi: Jaka jest największa ilość pudełek, jakie magazynier może
sprawdzić i bezbłędnie wyłowić zeń trefne pudełko nabojów w dostępnych mu
trzech ważeniach?


Ponieważ jest to kolejne zadanie konkursowe podaję obowiązujące reguły:

1. Zwycięzcą zagadki zostanie osoba, która poda poprawny sposób na wyłowienie
złych nabojów spośród największej liczby pudełek. Punktacja za te zadanie
będzie wyglądała następująco: największa ilość pudełek i pierwsze miejsce – 5
pkt., drugie – 3 pkt., trzecie 2 pkt., czwarte 1 pkt.
2. Zagadka będzie zakończona i punkty konkursowe przyznane w momencie, gdy
padnie optymalna odpowiedź. Jeśli optymalna odpowiedź nie padnie, to jury
zastrzega sobie prawo do zamknięcia zagadki w stosownym czasie.
3. Wszyscy łamigłówkowicze z premiowanej pierwszej czwórki będą na końcu
poproszeni o podanie swoich pełnych rozwiązań. Pełne rozwiązanie można też
podać od razu. Natomiast jeśli masz już teraz jakiś pomysł, dajmy na to na N
pudełek, to na pewno warto go od razu przedstawić i podać swoją liczbę,
by "zaklepać" swoje rozwiązanie i zapewnić sobie punkty konkursowe.
4. Jury jak zwykle zastrzega sobie prawo do własnej interpretacji i
wprowadzenia zmiany do każdego jednego punktu niniejszego regulaminu (choć
nie lubi tego robić i na 99% tego nie zrobi :) ).


Życzę wszystkim łamigłówkowiczom owocnych zmagań z tą trudną zagadką. :)

CdM
Obserwuj wątek
    • stomek Prośba o uszczegółowienie 06.10.03, 15:35
      Mam wątpliwość czy chodzi o:
      1) metodę wyszukania trefnego pudełka spośród n pudełek, przy założeniu, że jest
      dokładnie jedno trefne
      2) metodę sprawdzenia n pudełek, przy czym co najwyżej jedno jest trefne

      Wydaje mi się, że chodzi o 1, ale mam wątpliwość wynikającą z tego, że przecież
      w magazynie jest dużo pudełek, a magazynier nie sprawdzi wszystkich (chyba, że
      ma mniej pudełek niż jest odpowiedź dla przypadku 1.

      Tomek

      • cardemon Re: Prośba o uszczegółowienie 06.10.03, 18:01
        stomek napisał:

        > Mam wątpliwość czy chodzi o:
        > 1) metodę wyszukania trefnego pudełka spośród n pudełek, przy założeniu, że
        > jest dokładnie jedno trefne
        > 2) metodę sprawdzenia n pudełek, przy czym co najwyżej jedno jest trefne
        >
        > Wydaje mi się, że chodzi o 1, ale mam wątpliwość wynikającą z tego, że
        przecież
        > w magazynie jest dużo pudełek, a magazynier nie sprawdzi wszystkich (chyba, że
        > ma mniej pudełek niż jest odpowiedź dla przypadku 1.
        >
        > Tomek
        >

        Zdecydowanie chodzi o przypadek numer 1. A problem innymi słowami brzmi: Ile w
        magazynie może być maksymalnie pudełek z nabojami, by magazynier w trzech
        ważeniach mógł wyłapać te jedno z ośmioma wybrakowanymi pociskami?

        pzdr. CdM
      • cardemon Re: Wybrakowane naboje - zadanie konkursowe nr 3 06.10.03, 22:38
        lotrzynapl napisał:

        > Pytanie do autora i nie tylko. Czy zalozenie, ze uzyskujac na wadze szalkowej
        > rownowage jestem w stanie wyliczyc mase pojedynczego naboju, jest poprawne ?
        >

        Nie bardzo wiem, jak chcesz to zrobić. Ważenie odbywa się w ten sposób, że
        najpierw umieszcza się na obu szalach to, co ma być zważone, a potem przekręca
        się wajchę blokującą, a nstępnie odczytuje na skali liczbową różnicę w
        wychyleniu ramion.

        pzdr. CdM
        • lotrzynapl Re: Wybrakowane naboje - zadanie konkursowe nr 3 06.10.03, 23:13
          Czyli rozumiem, ze sie nie da.Potrzebne mi to bylo do mojego rozwiazania z 147
          pudelkami, ktore automatycznie staje sie niepoprawne bo przy 2 rownowagach po
          2 pierwszych wazeniach w 3 wazeniu (pozostalych 49 pudelek) (nie licze 3
          rownowagi) mozemy jedynie wyznaczyc roznice w wadze naboi ale nie wiemy ile
          ona wynosi dla pojedynczego naboju wiec nie wiemy, ktore pudelko jest trefne :-
          )

          pozdr.
          ALP
    • stomek 3687 - pełna odpowiedź z dowodem 06.10.03, 21:15
      Na początek dowód, że 3687 jest najlepszym możliwym do uzyskania wynikiem przy założeniu, że w każdym ważeniu na obu szalkach jest tyle samo naboi. Wydaje
      mi się, że nie ma sensu ważyć różnej liczby nabojów, ale już tego nie udowadniam.

      Załóżmy, że x to różnica wagi między nabojem trefnym, a dobrym. Jest tylko jedno trefne pudełko więc, w każdym ważeniu możemy dostać wynik n*x gdzie n to
      liczba całkowita z przedziału od -8 do 8. Policzmy ile różnych kombinacji można uzyskać w trzech ważenia.

      Jeżeli nie będzie zera to otrzymamy 3 bity informacji o znakach oraz 8*8*8=512 różnych wyników. Niestety niektóre z nich są nierozróżnialne z powodu
      nieznajomości x (np. x,2x,3x i 2x,4x,6x). Z 512 układów można uzyskać 439 różnych wartości stosunków D2/D1 i D3/D1. Czyli bez zer mamy 8*439 rozróżnialnych
      wyników.

      Jeżeli będzie dokładnie jedno zero to musiało wystąpić w pierwszym ważeniu. Po wyniku niezerowym nie będziemy już przecież porównywać dobrych nabojów z
      dobrymi bo to nic nie wnosi. W dwóch pozostałych ważeniach mamy 2 bity informacji o znakach oraz 8*8=64 wyniki, z których 43 są rozróżnialne. Czyli z dokładnie
      jednym zerem mamy 4*43 rozróżnialnych wyników.

      Jeżeli będą dokładnie dwa zera to musiały wystąpić w pierwszym i drugim ważeniu. W ostatnim ważeniu mamy 1 bit informacji o znaku oraz 8 nierozróżnialnych
      wyników. Czyli z dokładnie dwoma zerami mamy 2 rozróżnialne wyniki.

      Jeżeli były 3 zera to mamy tylko jeden rozróżnialny wynik.

      W sumie mamy 8*439 + 4*43 + 2 + 1 = 3687 rozróżnialnych wyników więc przy większej liczbie pudełek nie zawsze uda się jednoznacznie wskazać trefne.

      A teraz przepis na wykonanie takich ważeń.

      W każdym ważeniu:
      * na obu szalkach stoi tyle samo pudełek
      * w każdym pudełku jest od 1 do 8 naboi pochodzących z tego pudełka
      * na każdej szalce jest w sumie tyle samo naboi

      Wybieramy 439 "trójek" liczb z przedziału 1..8 dających rozróżnialne stosunki. Bierzemy 439 razy po 8 pudełek. Każdej ósemce przyporządkujmy inną "trójkę", która
      wyznaczy liczbę nabojów w pudełku podczas kolejnych ważeń.

      W pierwszym ważeniu z każdej ósemki po cztery pudełka idą na przeciwne szalki. Odrzucamy pudełka z cięższej szalki.
      W drugim ważeniu z każdej pozostałej czwórki po dwa pudełka idą na przeciwne szalki. Odrzucamy pudełka z cięższej szalki.
      W trzecim ważeniu z każdej pozostałej dwójki po jednym pudełku idzie na przeciwne szalki. Odrzucamy pudełka cięższej szalki.

      Pozostało 439 pudełek, a wśród nich trefne. Wyniki ważeń jednoznacznie wskazują na odpowiednią "trójkę" i jest tylko jedno pudełko, które w kolejnych ważeniach
      miało takie liczby naboi.

      Jeżeli podczas pierwszego ważenia waga wskazała 0 to pozostały jeszcze dwa ważenia na wyszukanie trefnego pudełka z pozostałej puli. Algorytm jest
      analogiczny, przy czym dwa ważenia:
      * dają 64 możliwe kombinacje, a wśród nich 43 różne
      * pozwalają dwukrotnie odrzucić połowę pudełek
      Czyli w dwóch ważeniach możemy "obsłużyć" dodatkowe 4*43 pudełka.

      Analogicznie w jednym ważeniu: jedna kombinacja i odrzucenie połowy pudełek pozwala "obsłużyć" jeszcze dodatkowe 2 pudełka.

      Analogicznie bez ważeń: jedna kombinacja bez możliwości odrzucania pozwala "obsłużyć" jeszcze jedno dodatkowe pudełko!

      W sumie 8*439 + 4*43 + 2*1 + 1 = 3687.

      • stomek Niestety - errata (3867) 07.10.03, 10:18
        Wynik, który wydawał mi się ostateczny można jeszcze poprawić
        z 3687 na 3867 (ciekawa gra cyferek).
        Jest to dowód na to, że nigdy nie należy mówić, że coś jest
        ostateczne.

        Tomek
          • stomek Dowód, że 4035 to max 07.10.03, 12:41
            Teza: 4035 jest najlepszym możliwym do uzyskania wynikiem przy założeniu,
            że w każdym ważeniu na obu szalkach jest tyle samo naboi. Wydaje mi się,
            że nie ma sensu ważyć różnej liczby nabojów, ale już tego nie udowadniam.

            Załóżmy, że x to różnica wagi między nabojem trefnym, a dobrym.
            Jest tylko jedno trefne pudełko więc, w każdym bierze udział co najwyżej
            8 trefnych naboi (a dokładnie od 0 do 8). W każdym ważeniu możemy dostać
            wynik postaci n*x gdzie n to liczba całkowita z przedziału od -8 do 8.
            Inaczej mówiąc możemy dostać:
            a) zero, lub
            b) jeden bit znaku oraz D = n*x gdzie 1 <= n <= 8
            Policzmy ile różnych kombinacji można uzyskać w trzech ważeniach.

            Oznaczmy przez D1, D2, D3 wskazania wagi w kolejnych ważeniach
            (niezerowe, bez znaku). Jeżeli nie będzie zera to otrzymamy
            3 bity informacji o znakach (czyli 2^3=8) oraz 8*8*8=512 różnych
            wyników. Niestety niektóre z nich są nierozróżnialne z powodu
            nieznajomości x (np. x,2x,3x i 2x,4x,6x). Możemy się opierać
            tylko na proporcjach wyników. Z 512 układów można uzyskać
            439 różnych wartości stosunków D2/D1 i D3/D1.
            Czyli bez zer mamy 8*439 rozróżnialnych wyników.

            Jeżeli będzie dokładnie jedno zero to wystąpiło w jednym
            z 3 ważeń. W dwóch pozostałych ważeniach mamy 2 bity informacji
            o znakach (czyli 2^2=4) oraz 8*8=64 wyniki, z których 43 są
            rozróżnialne. Czyli z dokładnie jednym zerem mamy 3*4*43
            rozróżnialnych wyników.

            Jeżeli będą dokładnie dwa zera to niezerowe było jedno z 3 ważeń.
            W niezerowym ważeniu mamy 1 bit informacji o znaku (2^1 = 2)
            oraz 8 nierozróżnialnych wyników. Czyli z dokładnie dwoma
            zerami mamy 3*2*1 rozróżnialne wyniki.

            Jeżeli były 3 zera to mamy tylko jeden rozróżnialny wynik.

            W sumie mamy 8*439 + 3*4*43 + 3*2*1 + 1 = 4035 rozróżnialnych
            wyników więc przy większej liczbie pudełek nie zawsze uda się
            jednoznacznie wskazać trefne.

            Tomek

            P.S.
            Nie męczcie się dalej, chyba że wykombinujecie rozwiązanie, w którym
            ważymy różne liczby naboi na każdej szalce.
          • uller Re: Ostatecznie 4035 07.10.03, 14:39
            Ciężko rozwiązać to zadanie bez komputera. O ile jeszcze w przypadku dwóch
            ważeń liczba 43 była do wyznaczenia na piechotę w rozsądnym czasie to niestety
            dla trzech ważeń wyznaczenie 439 niejednoznacznych przypadków wymaga napisania
            krótkiego programu.
            • lotrzynapl Watpliwosci zwiazane z tak duza liczba pudelek. 07.10.03, 15:14
              Moje 'spostrzezenie" jest bardzo proste. W pierwszym wazeniu na wadze szalkowej
              na jednej z szal musi znalzezc sie jedno cale pudelko zawierajace 8 zlych kul i
              o ile dobrze mysle moga sie w takim wazeniu znalezc tylko pelne pudelka a
              dlaczego ? Otoz jezeli w pierszym wazeniu (wazac niepelne pudelka) wyznaczymy
              jakas roznice wag to nie wiemy dla ilu kul w konkretnym podelku ta roznica byla
              wyznaczona. Inaczej nie wiemy czy wyznaczona roznica odpowiada 1 zlej kuli, 2
              zlym kulom, 3 zlym kulom itd. W takim przypadku nie widze za bardzo mozliwosci
              dalszych dzialan nawet na podstawie stosunkow roznic wag w poszczeglonyh
              wazeniach poniewaz pierwsze wazenie nie odpowiada nam na pyanie jaka jest
              roznica wag dla jednej kuli. Jezeli jestem w bledzie to prosze o poprawienie
              mnie. W zwiazku z powyzszym za poprawne uwazam wazenie w pierwszym wazeniu
              jedynie pelnych pudelek i im wiecej uda nam sie ich upchnac tym lepsze bedzie
              rozwiazanie ja zatrzymalem sie na 615 ale moze uda sie to poprawic - zobaczymy.

              pozdr.
              ALP
              • Gość: pafcio Re: Watpliwosci zwiazane z tak duza liczba pudele IP: *.acn.waw.pl 07.10.03, 16:06
                dla pokazania jak to się robi na niecołatwieszym przykładzie - max 4 naboje...
                w pierwszym ważeniu na obie szalki wrzucam tę zwierciadlanie:
                - po jednym naboju z 8 pudełek (nazwijmy je 11 12 13 14 15 16 17 18)
                - po dwa naboje z 4 pudełek (21 22 23 24)
                - po 3 naboje z 6 pudełek (31 32 31 34 35 36)
                - po 4 naboje z 4 pudełek (41 42 43 44) - razem 22 pudełka czyli 11*2 co nie
                jest przypadkiem, a skąd się wziął ten podział za chwilkę
                załóżmy że jedna z szalek jest lżejsza

                w 2 ważeniu po połowei dzielę na obie szalki równo w ten sposób, że
                z pudełka 11 1 nabój 12 2 naboje 13 3 naboje 14 4 naboje
                21 jeden nabój 22 3 naboje
                31 1, 32 2, 33 4
                i wreszcie 31 1 nabój, 43 3 naboje
                ta szalka okazuje się lżejsza
                na podstawie różnicy wskazań dochodze do wniosku że:
                jeżeli wynik w obu ważeniach ten sam to musiało byc pudełko 11
                jeżeli 2 pudełko 12, 3 13, 4 14, 1/2 21, 3/2 22, 1/3 31, 2/3 32, 4/3 33, 1/4 41
                i wreszcie 3/4 42.

                takich rozkładów z nabojami jest sporo różnych ale mają tę samą cechę -
                wykorzystują to że w 2 ważeniach stosunki pomiarów muszą być jednoznacznie
                wskazujące na rozwiązanie stąd jest ich tylko 11, a nie 16

                pzdr
            • stomek Można ręcznie 07.10.03, 17:49
              uller napisał:

              > Ciężko rozwiązać to zadanie bez komputera. O ile jeszcze w przypadku dwóch
              > ważeń liczba 43 była do wyznaczenia na piechotę w rozsądnym czasie to niestety
              > dla trzech ważeń wyznaczenie 439 niejednoznacznych przypadków wymaga napisania
              > krótkiego programu.

              Niekoniecznie od razu programu. Ja posłużyłem się Excel-em. Skoro pisząc na
              forum posługujesz się komputerem (chyba?) to pewnie masz pod ręką jakiś arkusz
              kalkulacyjny.
              W ostateczności można na piechotę wypisywać niejednoznaczne układy - będzie to
              dużo mniej pracy niż wyliczanie wszystkich par stosunków, sortowanie i
              sprawdzenie ile jest różnych par.

              Jako bazowe bieżemy tylko ciągi niemalejące (inne dostajemy przez permutacje).
              Pomijamy te, które wyszły wcześniej jako wielokrotności bazowych (np. pomijamy 2
              2 2 bo był 1 1 1).

              1 1 1 - 2 2 2, ..., 8 8 8 (7 odpada)
              1 1 2 - 2 2 4, 3 3 6, 4 4 8 (3 odpadają * 3 permutacje, razem 16)
              1 1 3 - 2 2 6 (1 * 3, 19)
              1 1 4 - 2 2 8 (1 * 3, 22)
              1 2 2 - 2 4 4, 3 6 6, 4 8 8 (3 * 3, 31)
              1 2 3 - 2 4 6 (1 * 6, 37)
              1 2 4 - 2 4 8 (1 * 6, 43)
              1 3 3 - 2 6 6 (1 * 3, 46)
              1 3 4 - 2 6 8 (1 * 6, 52)
              1 4 4 - 2 8 8 (1 * 3, 55)
              2 2 3 - 4 4 6 (1 * 3, 58)
              2 3 3 - 4 6 6 (1 * 3, 61)
              2 3 4 - 4 6 8 (1 * 6, 67)
              3 3 4 - 6 6 8 (1 * 3, 70)
              3 4 4 - 6 8 8 (1 * 3, 73)

              I już mamy wszystkie odpadające, a 512-73=439! Nawet bez pomocy kalkulatora!
              Uller - zrobiłem to specjalnie dla Ciebie.
              Tomek
    • tororo Prosba o szczegół - jak działa ta waga??? 06.10.03, 21:59
      Mam pytanie
      Otóz wagę opisuja dwa zdania:

      1). Waga jest dwuszalkowa i bardzo pojemna, tzn. na każdej z jej szalek można
      umieścić dowolną ilość nabojów.

      2). Waga ta może też bez problemu wychwycić różnicę w wadze między dobrym a
      złym nabojem i dokładnie określić jakiej wielkości jest ta różnica.

      Wcale z tego nie wynika, że waga może okreslić ilościowo (liczbową) róznicę
      wagi miedzy dowolna liczbą naboi.

      Wynika że tylko tyle możemy zmierzyc róznice miedzy jednym cieższym a jednym
      lżejszcym nabojem, oraz że możemy okresli czy cieżar połozony na jednej szali
      jest lżejszy/cieższy od cięzaru na drugiej szali.

      Łatwo sobie wyobrazic bowiem taka wagę szalkową, która wskazuje ilosciowo
      (liczbowo różnice) między dwoma szalami tylko do pewnego zakresu, a potem tylko
      jakościowo tzn pokazuje ciężar na której szali jest lzejszy a na której cieższy.

      No i żeby Cardemon wiedział o co pytam -
      Czy waga w zadaniu wskazuje liczbowo róznice miedzy dowolną liczbą naboi czy
      tylko taką różnicę która jest równa róznicy między jednym dobrym nabojem a
      jednym złym.

      A jakie sa konsekwencje odpowiedzi dla metody rozwiazania.
      Otóz jesli waga wskazuje różnice ilościową tylko między jednym dobrym a jednym
      złym to wartość tej róznicy nie tworzy informacji do wykorystania w ważeniach.
      Jesli zaś wskazuje róznie ilosciowa (np w gramach) miedzy dowolną liczba naboi -
      to pozwala to na formułowanie wielu róznych algorytmów rozwiązania.

      Pozdr

      Tororo
      • cardemon Re: Prosba o szczegół - jak działa ta waga??? 06.10.03, 22:33
        Oj, dobrze, że zajrzałem na forum, bo widzę, że pojawiają się wątpliwości. Już
        spieszę z wyjaśnieniem. Waga jest super precyzyjna i pozwala na dokładne (w tym
        i liczbowe) określenie różnicy pomiędzy ładunkami na obu szalach i to
        niezależnie od tego, jaki ciężar w sumie na tych szalach leży.

        pzdr. CdM
    • tororo 547 pudełek z dokładną procedurą ważenia 06.10.03, 22:28
      Zakładam, ze waga jest w stanie zmierzyć różnicę ciężaru dowolnej wielkości.

      1-sze WAŻENIE po 256 pudełek na każdej z szali (razem 512) – 35 pudełek czeka z
      boku.

      PRZYPADEK I – brak równowagi
      Wnioski:
      a) – 35 pudełek nie wazonych jest OK
      b) Mam wyznaczoną róznice cięzaru miedzy dobyrm nabojem a złym. Wynosi Równa
      jest ona 1/8 róznicy ciężaru między szalami. Oznaczmy ją R.
      c) Odrzucam podełka z cięzszej szali.

      2-gie WAŻENIE - ważenaboje z 256 paczek

      na kazdej z szali z 16 paczek po 1 naboju z kazdej , z 16 następnych paczek po
      dwa naboje z każdej ... az do z 16 kolejnych paczek po 8 naboi z kazdej.
      Razem na jednej szali naboje z 16*8- 128 paczek i tyle samo na drugiej szali.
      Róznica wskazań między szalami wyniesie od R do 8*R
      Wnioski:
      1) Jeśli róznica była R to fałszywy nabój jest na szali po lżejszej stronie
      wsród naboi z paczek z których wzięlismy po jednym naboju jeśli 2 to jest z
      jednej z paczek z których wzielismy po dwa naboje i tak aż do ośmiu
      2) zostaje nam do wybrania jedna paczka z szesnastu.

      3-cie WAZENIE
      na każdej ze stron szali kładziemy 1 nabój z pierwszej paczki 2 z drugiej 3 z
      trzeciej az do osmiu. Razem naboje z 16 paczek. Jesli róznica między szalami
      wyniesie R to trefny nabój jest z pierwszej paczki z lżejszej szali jeśli 2 R
      to z drugiej itd. aż do 8. Trefna paczka zidentyfikowana


      PRZYPADEK II – 1-sze WAŻENIE – równowaga
      Wniosek – fałszywy nabój jest wsród 35 pozostałych paczek ale zostały nam tylko
      dwa ważenia

      II WAZENIE - Na kazdej z szali kładziemy po 16 paczek, 3 ostatnie na boku

      a) brak równowagi
      16 paczek cieższych i te 3 na boku jest OK.
      Dla 16 lżejszych – powtarzamy III WAZENIE Z I PRZYPADKU i w ten sam sposób
      mamy zidentyfikowaną trefną paczkę

      b) równowaga – te 32 paczki są ok. Trefna jest wśród ostatnich trzech.

      Kładziemy na szali dwie z tych trzech – równowaga – trefna jest jedyna
      niewazona. Brak równowagi – trefna jest lżejsza.

      razem 512+32+3 = 547 pudełek.


      Pozdr

      Tororo







      .pl
        • tororo Re: 549 pudełek z dokładną procedurą ważenia 07.10.03, 00:10

          Jestem za dolożeniem tych dwóch pudełek - ale patrze patrze - kawa oczy mi
          zalewa - i nie widze nic. Napisz prosze jak.
          Nie gniewaj sie ALP - ale jestem przeciw uznaniu tych dwóch pudełek dla mnie -
          bo nie ja je wymysliłem. Powstaje natomiast pytanie (zapewne nie ostatnie) do
          Cardemona. Jak regulaminowo beda traktowane ulepszenia zgłoszonych juz
          procedur? Konkretnie w tym przypadku: czy jesli ALP ulepsza procedure o ktorej
          powiada ze sam jej nie wymyslił (i jeszcze mi punktacje miło chce podwyzszyc -
          dzieki ci ALP za to) - to mu sie to liczy w konkursie czy nie? - ja osobiscie
          nie ma nic przeciwko temu bo w sumie jest to dla mnie pasjonująca zabawa - ale
          nie tylko ja i ALP tu się bawimy pięknie a dobrze wiem jakie emocje potrafia
          takie konkursy wzbudzac i może warto sie zastanowic nad problemem.
          A może buduję sztuczny problem?? - sam nie jestem pewien do końca.

          Pozdr

          Tororo
          • lotrzynapl Re: 549 pudełek z dokładną procedurą ważenia 07.10.03, 00:17
            Przy pierwszym wazeniu rozkladamy pudelka i naboje tak jak opisales i
            dodatkowo na kazdej szalce kladziemy 3 cale pudelka naboi. Przy rownowadze nic
            sie nie dzieje natomiast jezeli nie ma rownowagi to roznica w wadze nadal moze
            wynosic max 8R przy czym to 8r albo bedzie w jednym z "calych: pudelek albo w
            jednym z 16 pudelek "rozlozonych". Ponownie wazymy z Twoim ustawieniem a 3
            dolozone wczesniej pudelka odkladamy. Jezeli mamy rownowage to te 8R bylo, w
            ktoryms "calym" pudelku i 3 wazenie je wyloni (po jednym na szalke i mamy
            wynik) a jezeli nie ma rownowagi to 3 wazenie jest takie jak Ty podales i
            znowu odnajdujemy zle pudelko bo te 6 dolozonych okazaly sie neutralnymi. Mam
            nadzieje, ze zbytnio nie zagmatwalem :-)

            pozdr.
            ALP
            • lotrzynapl Re: 549 pudełek z dokładną procedurą ważenia 07.10.03, 00:26
              Jednak troche pokrecilem:) W pierwszym wazeniu wazymy po 259 pudelek a przed 2
              3 odkladamy na bok i reszte wazymy w sposob jaki podales. Jezeli w 2 wazeniu
              jest rownowaga to trefne jest wsrod pozostalych 3 jezeli nie ma rownowagi to
              dalej postepujemy (postepujesz ?;-) tak jak opisywales.

              pozdr.
              ALP
              • tororo Już 579 pudełek z dokładną procedurą ważenia 07.10.03, 01:15
                lotrzynapl napisał:

                W pierwszym wazeniu wazymy po 259 pudelek a przed 2
                > 3 odkladamy na bok i reszte wazymy w sposob jaki podales. Jezeli w 2 wazeniu
                > jest rownowaga to trefne jest wsrod pozostalych 3 jezeli nie ma rownowagi to
                > dalej postepujemy (postepujesz ?;-) tak jak opisywales.

                Znakomity pomysł ALPA w ramach tej procedury :))
                Ale mozna wazyć w pierwszym ważeniu po 282!!!
                Otóz jesli jest równowaga to i tak przechodzimy do badania odstawionych na bo
                35 pudełek.
                Jesli równowagi nie ma, to znamy róznice wagi między dobry i złym nabojem
                I do drugiego wazenia bierzemy 256 pudełek z lzejszej szali( 16 zostawiamy na
                boku) - rozkładamy je wg schematu przedstawionego w sposobie na 547 pudełek.
                Jesli nie ma równowagi - dalej postepujemy jak przy "547" pudekach.
                Jesli równowaga w tym drugim ważeniu jest, to wiemy że złe pudełko znajfduje
                się wśród tych 16, które były na lżejszej szali w pierwszym ważeniu a przed
                drugim ważeniem zostały odłożone na bok.
                I terazs zukamy trefnej paczki własnie wsród tych 16-tu. Postepujemy jak w
                trzecim ważeniu w pierwszym przypadku - tzn na szale wagi kładziemy 1 nabój z
                pierwszego pudełka drugi z drugiego itd - rozkładamy tak naboje z jednych 8
                pudełek na jednej szali a z 8 pozostałych na drugiej. Różnica waga między
                szalami podzielona przez róznice między jednym dobrym nabojem a jednym złym
                wskaze nam które naboje (z którego pudełka) na lzejszej szali sa trefne.

                Dzieki ci ALP

                Pozdr Tororo
              • lotrzynapl Re: 583 pudełka z dokładną procedurą ważenia 07.10.03, 01:23
                W pierwszym wazeniu wazymy po 256+17=273 pudelka. Pred 2 wazeniem 17 odkladamy
                a pozostale wazymy tak jak opisal tororo. Jezeli w 2 wazeniu bedzie rownowaga
                to z 17 odlozonych ukladamy kolejno 1 naboj z pierwszego 2 z drugiego itd. az
                do 8 naboi z 8 pudelka na jednej szalce i to samo na 2 szalce a jedno pudelko
                odkladamy cale na bok. Jezeli w 3 wazeniu nie bedzie rownowagi to roznica od
                1R do 8R wskaze nam trefne pudelko a jezeli bedzie rownowaga to trefnym
                okazuje sie to jedno odlozone. Gdy natomiast w 2 wazeniu nie bedzie rownowagi
                to dalej postepujemy tak jak opisal Tororo a wszystkie 17 odlozone pudelka sa
                dobre.Natomiast jezeli w 1 wazeniu byla rownowaga to w 2 wazymy 37 a nie 35
                pudelek. A wyglada to tak - po rownowadze w piwerwszym wazeniu w drugim wazymy
                po 17 pudelek jezeli jest rownowaga to trefne pudelko jest w pozostalych 3
                pudelkach i wiadomo jak je odnalezc natomiast jezeli nie ma rownowagi to jedno
                z 17 pudelek lzejszych odkladamy a pozostale wazymy metoda 1 naboj z
                pierwszego pudelka itd. Jezeli w tym momencie po 3 wazeniu jest rownowaga to
                trefne bylo to 17 pudelko a jezeli nie to poraz kolejny roznica od 1R do 8R
                powie nam, ktore pudelko jest zle. Tradycyjnie mam nadzieje, ze nie jest to
                wsyztsko zbyt zagmatwane. Ide spac bo jak tak dalej pojedzie to dojde do 10
                000 ;-)pudelek i nie wstane do pracy :)

                pozdr.
                ALP
                • lotrzynapl Re: 615 pudełek z dokładną procedurą ważenia 07.10.03, 08:39
                  Jest rozwiazanie dla 615 :-)

                  W pierwszym wazeniu wazymy o 32 pudelka wiecej (czyli po 289 pudelek).Jezeli
                  jest rownowaga to dalej jest tak jak wczesniej. Jezeli nie ma rownowagi to
                  odkladamy 17 pudelek a z 16 dodatkowych wyciagamy naboje i uwaga: w kazdym z
                  tych 16 zostawiamy odpowiednio w dwoch po 1 w 2 po 2 itd az do w dwoch
                  pudelkach po 8 naboi. Drugie wazenie - jezli tu jest rownowaga to tak
                  postepujemy tak jak podaalem w rozwiazaniu dla 583 pudelek a jezeli nie ma
                  rownowagi to roznica w wadze moze nadal wynosic od 1R do max 8R przy czym
                  roznice te wniesc moga zarowno naboje wyjete z paczek (pierwsze rozwiazanie
                  Tororo) jak i pociski w pudelkach (te dodatkowych 16 pudelek). Dokonujemy
                  trzeciego wazenie w sposob jaki opisal tororo a dodatkowe 8 pudelek jakie nam
                  pozostaje (16/2) odkladamy na bok. Jezeli w 3 wazeniu byla rownowaga to roznice
                  od 1R do 8R moglo wniesc jednie jedno z odlozonych przed 3 wazeniem 8 pudelko
                  to rozpoznajemy oczywiscie po wilkosci roznicy. Natomiast jezeli w 3 wazeniu
                  nie bylo rownowagi to mamy do czynienia z przypadkiem jaki podawal Tororo w
                  pierwszym rozwizaniu i takze rozpoznajemy trefne pudelko po wielkosci roznicy.
                  OK - tradycyjnie mam nadzieje, ze opisalem rozwiazanie w miare zrozumiale :-)
                  Msle dalej nad tymi 3 tysiacami :-)

                  pozdr.
                  ALP
    • cardemon Uściślenia, komentarze - Re: Wybrakowane naboje... 07.10.03, 01:13
      Mam kilka uwag i komentarzy na gorąco. Przede wszystkim przypominam uściślenia
      do tej zagadki: waga jest super dokładna i precyzyjnie podaje różnicę w
      wychyleniu obu szalek. Z każdego ważenia można więc otrzymać liczbę równą
      różnicy mas na obu szalkach. Ponadto do momentu umieszczenia wszystkich
      ważonych naboi na obu szalkach oba ramiona wagi są zabezpieczone blokadą, więc
      nie w samej wadze, ani nie w jakichś sztuczkach przy ważeniu leży klucz do
      rozwiązania tej zagadki.
      Cieszę się z dużego odzewu na tę zagadkę, ale zastrzegam, że aż do momentu
      zamknięcia zagadki nie skomentuję ani jednego rozwiązania, ani nie podam żadnej
      podpowiedzi. Mogę tylko powiedzieć, że ponieważ uznaję tę zagadkę za super
      trudną, jest ona tak wysoko punktowana (w sumie jest 11 punktów do zdobycia!).

      CdM
          • cardemon Re: 3271 08.10.03, 00:16
            mesquaki napisała:

            > 3271 = 1 + 2 + 4*43 + 72*43
            > I już pójdę spać, a jutro mogę to wszystko odszczekać ;).

            Witaj Mes!!! Bardzo miło mi Cię znów tu widzieć! :) Gdzie byłaś, jak Cię nie
            było? :)
            Wszystko jest OK, ale podaj mi proszę, skąd wzięło się "72*43"?

            Serdecznie pozdrawiam, CdM
            • mesquaki Re: 3271 08.10.03, 05:50
              cardemon napisał:

              > Witaj Mes!!! Bardzo miło mi Cię znów tu widzieć! :)
              A zamiatam kołpakiem, mi również miło, jak zawsze.

              > Gdzie byłaś, jak Cię nie było? :)
              Barrrdzo Strrraszny Egzamin :O

              > Wszystko jest OK, ale podaj mi proszę, skąd wzięło się "72*43"?


              To jest taka leniwa wersja rozwiązania, w której nie trzeba (tzn. nie chciało
              się ;) szukać wszystkich jednoznacznych kombinacji trzech wskazań wagi.
              Obawiałam się, że to będzie bolesne, teraz widzę, że zupełnie nie :).

              Skąd się wzięło 43 to wiadomo.
              Każdy z 43 układów jest reprezentowany przez 76 różnych pudełek. Razem jest
              43*76+3 pudelek.

              4*43 +3 paczki odkładamy na bok, zajmiemy się nimi w razie równowagi po
              pierwszym ważeniu.

              Teraz pozostałe 72*43:

              1. W pierwszym ważeniu kładziemy na szalach po 36 paczek z każdych
              43 układów. Zajmujemy się lżejszymi.

              2. W drugim ważeniu z wybranych 36*43 kładziemy na szalach po 17*43 paczek.
              2*43 odkładamy na bok, zważymy je w razie równowagi.
              Jeśli jest nierówność, to ze stosunku wychyleń w pierwszym i drugim ważeniu
              można jednoznacznie określić, która z 17-stek zawiera lżejsze kule. Ponadto
              wiadomo, o ile lżejsza jest trefna kula.

              3. Na każdej szali ważymy po 8 pudełek ze zidentyfikowanej 17-tki, każde z
              różną ilością kul.
              W razie równowagi lżejsza jest w tej 17.

              Jeszcze tu widzę niewielkie zapasy, ale już nie będę drążyć.

              Poza tym prosiłabym uniżenie, o ile to nie nadmierne fanaberie, coby szacowne
              jury jednak mnie wypisało z konkursu. To był taki pozakonkursowy wybryk :)

              pozdrawiam serdecznie

              m
      • tororo KONIEC! - Re: Wybrakowane naboje 07.10.03, 14:38
        Szlachetne jury zamknęło rundę. Wiec podyskutujmy.

        Poniżej słowo program nie oznacza programu komputerowego a procedurę ważenia.

        Ja uważam, że prawidłowe rozwiązanie to dokładne rozpisanie ważenia nie
        pozostawiające wątpliwości.
        Posłużę się dwoma przypadkami.
        pierwszy to klasyczne zadanie znalezienia przy pomocy wagi szalkowej fałszywej
        monety spośród 12 w trzech ważenia kiedy jedna jest albo cięższa albo lżejsza
        a waga wskazuje tylko stany 1/0/-1.
        Prosty rachunek 3*3*3=27 pokazuje ile jest możliwych kombinacji wyników
        ważenia. Nie ma tu układów nierozróżnialnych.
        Aby móc jednoznacznie zidentyfikować fałszywą monetę tak musimy zaprogramować
        ważenie aby każdej z monet przypisać dwie jednoznacznie identyfikujące ją
        kombinacje - w przypadku gdy jest ona moneta lżejszą i w przypadku gdy jest
        cięższą.
        27/2= 13 r1
        Zatem biorąc pod uwagę te rozważania powinniśmy móc w 3 ważeniach
        jednoznacznie określić fałszywą monetę spośród nie tylko 12 ale i spośród 13
        monet...
        Układałem taki program dla tego przypadku – namozoliłem się sporo,ale ułozyłem
        i w zyciu nie będę tego robił dla większej liczby a już na pewno nie dla
        kilkuset czy kilkut ysiecy pudełek z rózną liczba nabojów (a tak trzeba w
        zadaniu). Potem znalazłem w literaturze – był taki sam. Nie słyszałem, aby ktoś
        ułożył taki program dla 13 monet w3 ważeniach.

        Zatem nie bardzo można być pewnym, że jeśli się ma określoną górna granicę to
        na pewno jesteśmy w stanie taka procedurę ważenia zaplanować.
        A jakie to pracochłonne – można spróbować na prostszych przypadkach – tzn
        pudełkach z dwoma lub z trzema kulami:
        - dla dwóch naboi w pudełku mamy potencjalnie 5*5*5 = 125 różnych wyników –
        ale trzeba najpierw odrzucic niejednoznaczne – np. 111 222 –1,-1-1;-2,-2,-2 i
        jeszcze sporo innych
        - dla 3 kul w pudełku już mamy 7*7*7=343 wyniki od których trzeba odjąć dużo
        naprawdę niejednoznacznych i dopiero wtedy zacząć układać program ważenia.

        Dlaczego tak się przyczepiłem do drobiazgowo rozpisanego programu ważenia
        (numery pudełek na szalach liczby naboi w pudełkach) a w swojej metodzie tego
        nie robię?

        Otóż metoda która pracowaliśmy ja i ALP – to taka jak ktoś napisał
        łopatologiczna a żartobliwie ujmując "logiczna metoda naocznych stanów
        fizycznych".

        W metodzie w której układamy program identyfikacji po stanach nie mamy owej
        naoczności czy też łopatologii - i musimy być pewni że mamy do czynienia z
        jednoznaczną identyfikacja pudełka ze złymi nabojami.

        Uff – to tyle. Za chwilkę drugi post i do roboty normalnej.

        Pozdr
        Tororo

    • tororo APEL DO ALPA 07.10.03, 14:46
      ALP - myslę w tej naszej metodzie mamy jeszcze troszke rezerw - w tych 35
      kulach odkładanych przy pierwszym wazeniu. ja niestety wyczerpałem swój czas az
      do wieczora - nie ulepszył bys jeszcze tych 615? - jesteś w tym naprawdę
      dobry:))

      Pozdr
      Tororo
      • lotrzynapl Re: APEL DO ALPA 07.10.03, 15:06
        Szczerze mowiac jak zobaczylem te rozwiazania po kilka tysiecy pudelek to juz
        nad tym "naszym" rozwiazaniem nie myslalem za wiele :-)A po pierwszej
        rownowadze juz jest 37 kul i chyba ciezko cos bedzie tam dolozyc :-) Ja rowniez
        mam swoje watpliwosci co do rozwiazan dajacyh kulka tysiecy pudelek ale o tym w
        innym poscie :-) Moze cos jednak jeszcze wycisne z tych 615 ?;-)

        pozdr.
        ALP
    • cardemon Wyniki nieoficjalne - Re: Wybrakowane naboje 07.10.03, 18:28
      Prawidłowa odpowiedź do tej zagadki została podana przez Stomka w
      poście "Ostatecznie 4035 stomek 07.10.2003 10:32" i zagadka zgodnie z punktem
      drugim regulaminu została w tym momencie zamknięta. Wszystkie wyniki, które
      wpłynęły po tym czasie nie będą mogły być wzięte pod uwagę (bardzo mi przykro
      Uller i Pafcio).

      Nieoficjalnie pierwsze cztery punktowane miejsca zajęli:

      1. Stomek - 4035 = 8*439 + 3*4*43 + 3*2*1 + 1
      2. Marchewa - 3867
      3. Mesquaki - 3271 = 1 + 2 + 4*43 + 72*43
      4. Krzysiek - 3015

      Bardzo proszę Marchewę i Krzyśka o podanie swoich końcowych równań, tak jak
      uczynili to Stomek i Mesquaki.
      Podkreślam, że są to wyniki nieoficjalne. Oficjalne wyniki z punktacją,
      obszerny komentarz oraz omówienie rozwiązania wraz z opisem techniki ważenia
      znajdą się w następnym poście.

      CdM
      • Gość: krzysiek równanie IP: *.acn.pl 07.10.03, 22:59
        moje rozwiązanie różni się od standardowego....
        aczkolwiek jest poprawne matematycznie, to poszło ostro w krzaki i jest zbyt
        wydumane,,, ale cóż, bardzo późno było......
        dlatego oprócz równania przedstawiam uzasadnienie


        równanie jest następujące:
        3015 = 4 * (42*8 + 22*17) + (43*4) + 2 + 1



        po dwóch pierwszych ważeniach wyznaczam wagę złego pudełka oraz grupę pudełek,
        w których jest zła paczka.
        wyznaczyłem taki zestaw dwóch ważeń, który na podstawie proporcji różnicy w
        wagach jednoznacznie określa wagę złego pudełka oraz ogranicza podejrzane
        pudełka do 1/64 lub 2/64 grupy pudełek po drugim ważeniu.

        i to był mój największy błąd, że w trzecim losowaniu chciałem na podstawie
        znajomości wagi złego naboju określić złe pudełko.

        do pierwszego ważenia wziąłem 2840 pudełek - tj. 42 po 32 pudełka i 22 po 68
        pudełek.
        po dwóch ważeniach mam 42 po 8 pudełek i 22 po 17 pudełek.
        ważenia są tak dobrane, że jednoznacznie wskazują albo na jedną kupkę 17
        pudełek, albo na dwie po 8 pudełek.
        a następnie w sposób 'brutalny' kładąc po 8 pudełek na każdej szalce, w każdym
        inna ilość naboi, i znając wagę wadliwego naboju wyznaczam własciwe pudełko.


        jeśli w pierwszym ważeniu była równowaga do drugiego ważenia biorę dodatkowe
        172 pudełka.
        wykorzystałem tu dokładnie ten sam algorytm doboru ważeń, choć już czułem że to
        nie to, ale było naprawdę późno.
        172 pudełka = 42 po 2 (a fizycznie 21*4 i 21*0) oraz 22 po 4

        no i jeśli drugie ważenie wykazało równowagę dochodzą jeszcze 2 pudełka i
        trzecie, jesli w trzecim ważeniu też jest równowaga.


        a teraz wspomniany wcześniej zestawik ważeń.
        1) podzieliłem 2840 pudełek w ten sposób:
        32 - 32 - 32 - 32 - 32 - 32 - 32 - 32
        32 - 32 - 32 - 68 - 68 - 68 - 68 - 32
        68 - 68 - 32 - 68 - 68 - 68 - 68 - 32
        32 - 32 - 32 - 32 - 68 - 32 - 68 - 32
        32 - 32 - 32 - 32 - 32 - 32 - 68 - 32
        32 - 32 - 68 - 32 - 68 - 32 - 68 - 32
        32 - 32 - 32 - 32 - 68 - 32 - 32 - 32
        68 - 68 - 68 - 32 - 68 - 32 - 68 - 32

        2) w pierwszym ważeniu użyłem z każdej kolumny z każdego pudełka tyle naboi:
        1 - 2 - 3 - 4 - 5 - 6 - 7 - 8

        3) w drugim ważeniu użyłem odpowiednio:
        5 - 5 - 1 - 1 - 1 - 1 - 1 - 1
        6 - 2 - 7 - 2 - 2 - 4 - 2 - 7
        3 - 3 - 5 - 3 - 3 - 8 - 3 - 3
        7 - 7 - 1 - 1 - 4 - 7 - 4 - 1
        5 - 5 - 5 - 5 - 1 - 5 - 5 - 5
        6 - 2 - 6 - 5 - 6 - 1 - 6 - 5
        7 - 7 - 7 - 7 - 7 - 7 - 1 - 7
        8 - 8 - 8 - 7 - 8 - 5 - 8 - 3

        liczby są tak dobrane, że uzyskuję:
        - 22 ilorazy, które się nie powtarzają, oraz
        - 21 ilorazów, które powtarzają się dwukrotnie,

        przy czym istotne jest to, że jeśli mamy dwa takie same ilorazy, to w obu
        przypadkach w pierwszym i drugim ważeniu zostały użyte te same ilości naboi.
        stąd wyciągam wniosek o wadze złego pudełka.

        =====
        tak więc wywodem moim udowodniłem chyba tezę postawioną na początku,
        a mianowicie, że zaliczyłem niezłe krzaczory.
        mimo wszystko mam nadzieję, że nie tu błędu, a i że przez jury uznane zostanie

        pozdrawiam,
        krzysiek
      • marchewa4 Wyniki nieoficjalne - Re: Wybrakowane naboje 08.10.03, 08:26
        Rownania niestety nie podam, bo rozwiazanie uzyskalem niejako numerycznie:
        wzialem wszystkie mozliwe trojelementowe kombinacje z powtorzeniami zbioru (-
        8, .., 8). Wklepalem je do Excela wiersz po wierszu (automatycznie, nie
        recznie ;-)). Zauwazylem, ze np stany (1,1,2) i (2,2,4) sa nierozroznialne.
        Teraz postanowilem potestowac, ktore sa rozroznialne. W tym celu musialem
        ustalic jakies cechy, ktore bede porownywal. Przyjalem poczatkowo, ze beda to
        ilorazy liczby 2. do 1. i 3. do 1 (przy czym wynikiem jest 0 jesli 1. liczba
        jest 0). Zauwazylem, ze to nie roznicuje mi tych wierszy tak jakbym chcial
        (uznaje za tozsame np. stany (-1, -1, -1) i (1,1,1)), wiec dodalem jeszcze znak
        pierwszego elementu. Policzylem (policzyl Excel) ile jest takich roznych trojek
        (te dwa ilorazy i znak). Wyszlo mi 3859. Wzialem dodatkowo pod uwage nie tylko
        znak pierwszego elementu, ale i pozostalych i wyszlo mi 3867.
        Sprawdzilem, czy da sie ulozyc kule na szalkach, tak aby te wazenia mialy sens.
        Po ponumerowaniu wszystkich stanow (x,y,z) od 1 do 3859, z kazdej paczki
        kladziemy przy pierwszym wazeniu x kul na prawa szale jesli x > 0 i (-x) kul na
        lewa szale jesli x < 0. Przy drugim i trzecim wazeniu odpowiednio y i z.
        Zauwazylem, ze oprocz stanu (0,0,0) kazdy stan (x,y,z) ma swoj odpowiednik w
        postaci stanu (-x, -y, -z). A to oznaczy, ze przy kazdym wazeniu liczba kul na
        obu szalach jest jednakowa. Zatem wazenia wg tego planu sa wykonalne.

        Pozdrowienia
        M.

        PS. Pozniej juz zauwazylem, ze przyjete przeze mnie cechy nie roznicuja stanow
        (0,1,2) i (0,1,3), bo w obu tych przypadkach pierwsze dwie cechy sa 0. Zamiast
        wiec dwoch ilorazow (2 do 1 i 3 do 1) wzailem nieco na wyrost wszystkie 6
        mozliwych ilorazow. Majac teraz dziewiec cech (6 ilorazow i 3 znaki) doszedlem
        po niewczasie do liczby 4035.
    • stomek 4035 - rozwiązanie 07.10.03, 18:45
      Zakładam, że czytelnik rozwiązania zna post
      forum.gazeta.pl/forum/72,2.html?f=514&w=8356242&a=8374487
      z dowodem na to, że 4035 jest maksymalnym możliwym do uzyskania wynikiem,
      przy założeniu, że ważymy zawsze taką samą liczbę nabojów na każdej szalce.

      Dzielimy 4035 na cztery grupy 8*439, 12*43, 3*2 i 1.

      Pierwszą grupę dzielimy na 8 zestawów po 439 pudełek. Każde pudełko
      z tej grupy będzie uczestniczyło w trzech ważeniach. Każdemu zestawowi
      przyporządkowujemy jedną z 439 rozróżnialnych kombinacji liczb nabojów
      do ważenia w poszczególnych trzech ważeniach. W każdym zestawie mamy 8
      pudełek i w kolejnych ważeniach:
      pudełko 1 jest kolejno: na lewej (l), lewej (l) i znowu lewej (l) szalce
      2: l, l, p
      3: l, p, l
      4: l, p, p
      5: p, l, l
      6: p, l, p
      7: p, p, l
      8: p, p, p

      Drugą grupę dzielimy na 12 zestawów po 43 pudełka. Każde pudełko z tej
      grupy będzie brało udział w dwóch ważeniach. Każdemu zestawowi
      przyporządkowujemy jedną z 43 rozróżnialnych kombinacji liczb nabojów
      do ważenia w poszczególnych dwóch ważeniach.
      Każdy zestaw dzielimy na 3 komplety po 4 pudełka. W pierwszym ważeniu
      będą brały udział komplety 1 i 2, w drugim 1 i 3, w trzecim 2 i 3.
      Pudełka z danego kompletu będą:
      pudełko 1 na lewej przy pierwszym ważeniu danego kompletu i lewej przy drugim
      2: l p
      3: p l
      4: p p

      Trzecia grupa to 6 pudełek. Każde będzie ważone dokładnie raz.
      W pierwszym ważeniu na lewej będzie 1 na prawej 2.
      W drugim na lewej 3 na prawej 4.
      W trzecim na lewej 5 na prawej 6.

      Czwarta grupa to jedno pudełko, które nie będzie ważone.

      Jeśli każde ważenie da zero to trefne jest pudełko z grupy 4.

      Jeśli będą dokładnie dwa zera to trefne jest pudełko z grupy 3, nietrudno
      ustalić które - to z niezerowego ważenia, z lżejszej strony.

      Jeśli będzie dokładnie jedno zero to trefne jest pudełko z grupy 2.
      Stosunek wyników wskazuje na jeden z 43 zestawów po 12 pudełek.
      Numer ważenia zerowego wskazuje nam na jeden z trzech kompletów po 4 pudełka
      (ten który nie brał udziału w tym ważeniu). Kierunki wychylenia wagi
      identyfikują jedno z 4 pudełek w komplecie.

      Jeżeli nie będzie zer to trefne jest pudełko z grupy 1. Stosunek wyników
      wskazuje na jeden z 439 zestawów po 8 pudełek, a kierunki wychylenia wagi
      identyfikują pudełko.

      Mam nadzieję, że Cardemon mi to zaliczy :-)

      Tomek
      • stomek Re: 4035 - rozwiązanie 07.10.03, 18:49
        stomek napisał:

        > Mam nadzieję, że Cardemon mi to zaliczy :-)

        Tyle czasu zajęło mi pisanie rozwiązania, że nie zauważyłem,
        że w międzyczasie Cardemon już mi zaliczył (co prawda nieoficjalnie)
        na podstawie dowodu.

        pozdrowienia dla wszystkich "magazynierów",
        Tomek
        • tororo Pytanie do Stomka 07.10.03, 21:04
          Tomek

          Jestem pod wrażenie zagadki Cardemonowej - jak zwykle znakomitej - jestem
          również pod wrazeniem twojego rozwiazania - czyli stworzenia algorymu ważenia.
          To jest o wiele bardziej eleganckie rozwiazanie - czuć duszę matematyka lub
          informatyka – czy zgadłem? - niż moje rozważania - jako że badany jest zbiór
          stanów i z tego badania wyciagane sa praktyczne wnioski. Mnie się to kiedys
          udało dla przypadku o wiele bardziej banalnego – po długich rozważaniach – co
          jeszcze pogłebia moje obecne wrażenia.

          Jesteś dla mnie teraz najbardziej kompetenty w tej zagadce i dlatego własnie do
          Ciebie kieruje moja watpliwość, której sobie nie potrafie wyjaśnić.

          Otóż piszesz
          „Każdemu zestawowi przyporządkowujemy jedną z 439 rozróżnialnych kombinacji
          liczb nabojów do ważenia w poszczególnych trzech ważeniach”

          Otóz jak pisalem już we wczesniejszym poscie znane sa sytuacje, ze mamy do
          dyspozycji wystarczajaca liczbe stanów a mimo to nie daje się ich tak
          rozplanowac aby przeprowadzic wazenie . Zebys nie musiał skakac po długiej
          liście postów wklejam moje rozwazania z drobnymi skrótami raz jeszcze.:

          „....to klasyczne zadanie znalezienia przy pomocy wagi szalkowej fałszywej
          monety spośród 12 w trzech ważenia kiedy jedna jest albo cięższa albo lżejsza a
          waga wskazuje tylko stany 1/0/-1.Prosty rachunek 3*3*3=27 pokazuje ile jest
          możliwych kombinacji wyników ważenia. Nie ma tu układów nierozróżnialnych.

          Aby móc jednoznacznie zidentyfikować fałszywą monetę tak musimy zaprogramować
          ważenie aby każdej z monet przypisać dwie jednoznacznie identyfikujące ją
          kombinacje - w przypadku gdy jest ona moneta lżejszą i w przypadku gdy jest
          cięższą.

          27/2= 13 r1.
          Zatem biorąc pod uwagę te rozważania powinniśmy móc w 3 ważeniach jednoznacznie
          określić fałszywą monetę spośród nie tylko 12 ale i spośród 13 monet..
          Układałem (recznie) taki program ważenia dla tego przypadku (dla 12 monet) –
          namozoliłem się sporo, ale ułozyłem.Potem znalazłem w literaturze – był taki
          sam. Nie słyszałem, aby ktoś ułożył taki program dla 13 monet w 3 ważeniach”

          Jedyne rozwiazanie problmu 13 monet w 3 wazeniach z jakim się wielokrotnie
          zetknąłem – to takie że możemy stwierdzic że 13 jest fałszywa ale nigdy nie
          powiemy czy jest lzejsza czy cięższa.(to w przypadku wyniku 0-0-0). Inaczej
          mówiac – nie da się mimo wystarczajacej liczby stanów zaplanowac ważeń.

          Moje pytanie jest takie – jeśli nie udało się rozplanowac ważeń dla przypadku
          27 kombinacji (na dodatek przy 1 kombinacji zapasowej) to czy możemy mieć
          pewnośc ze uda się to zrobić dla 439 kombinacji?
          Czyli jeśli jakaś metoda nie sprawdza się w jednym przydaku, to aby moc
          powiedziec ze metoda ta sprawdza się w innym podobnym przypadku musimy być
          tego pewni.

          Być może te dwa problemy na tyle się róznia że daje się pokazac iż przyczyna,
          która powoduje ze nie daje się w przypadku 13 monet zaplanowac ważen znika w
          przypadku naszej łamigłowki. Ja sam takiej róznicy nie widze.

          Pewnośc oczywiście w tym przypadku niekoniecznie musi oznaczac rozpisanie tego
          po wszystkich numerach pudełek i liczbach nabojów – jako ze można posłuzyc się
          jakims dowodem.
          JOczywiście innym sposobem rozwiązaia tego problemu jest skuteczne
          zaplanowanie trzech wazen dla 13 monet.

          Żeby było jasne – nie gonię za podwazaniem czegokolwiek – jedynie lubie mieć
          rzeczy wyjasniane do spodu tak jak to wspaniale zrobiłes z dowodem na 4035
          rozróznialnych w tym przypadku kombinacji.

          Pozdr
          Tororo
          • stomek O naturze zagadek z "testami" 08.10.03, 01:12
            Mnie również zaintrygowały zagadki tego typu, w których wykonując określone
            "testy" i uzyskując pewne informacje chcemy ustalić jednoznacznie odpowiedź
            spośród ustalonego z góry zbioru możliwych odpowiedzi.
            Czy jeśli szukamy jednej z N możliwych odpowiedzi, a przy określonych założeniach
            (np. ustalona liczba ważeń, liczba naboi w pudełkach itp.) możemy uzyskać M >= N
            rozróżnialnych wyników testów to czy zawsze da się zaplanować takie testy żeby
            rozwiązać zadanie?

            Czy ktoś zna odpowiedź na to pytanie?

            Wracając do Twoich pytań o 13 monet - dla 3 ważeń monet z jedną fałszywą
            (nie wiemy czy lżejsza czy cięższa) wcale nie mamy 27 rozróżnialnych układów.
            Np. (1, 1, 1) jest taki sam jak (-1, -1, -1) bo nie wiemy czy fałszywa jest
            lżejsza czy też nie. W każdym z tych dwóch przypadków wiemy, że
            fałszywa moneta brała udział w każdym ważeniu i była na tej samej szalce.
            Jeśli jest tylko jedna taka moneta to ona jest fałszywa (ale wcale nie
            korzystamy z kierunku wychylenia szalki, a za to dowiemy się czy
            jest lżejsza!). Jeśli są dwie monety spełniające takie kryteria to jeśli leżały
            na tej samej szalce to nie wiemy, która to z nich, a jeśli leżały na przeciwnych
            szalkach to też nie wiemy bo nie wiemy czy fałszywa jest lżejsza.

            Dla samych 0 mamy 1 układ.
            Dla dwóch 0 mamy 3 układy (niezerowe w jednym z trzech miejsc,
            ale kierunek nic nam nie mówi)
            Dla jednego 0 mamy 2*3 = 6 układów (zerowe w jednym z trzech miejsc,
            a niezerowe albo są takie same albo przeciwne).
            Przy braku zer mamy 1 + 3 = 4 układy (albo wszystkie równe, albo jedno
            z trzech różni się od dwóch pozostałych).
            W sumie mamy 14 rozróżnialnych wyników.

            Faktycznie nie znam rozwiązania dla 14 monet, ani nie znam dowodu,
            że nie da się tego zrobić. Widziałem rozwiązanie dla 13 monet.

            Jeżeli szukasz rozwiązania, w którym oprócz wskazania monety fałszywej
            chcesz też wiedzieć czy jest lżejsza to faktycznie żądasz jednej z 26 odpowiedzi
            (jedna z 13 monet plus jeden bit informacji o wadze). Skoro dla 3 ważeń mamy
            14 rozróżnialnych wyników to nie da się tego zrobić. Teoretycznie można zrobić
            14 monet, ale tylko ze wskazaniem fałszywej, a bez wskazania czy jest lżejsza.

            Po zastanowieniu potrafię to rozwiązać w trzech ważeniach dla 14 monet,
            ale potrzebuję do tego dodatkowej 15 monety, o której wiem, że jest prawdziwa.
            Myślę, że zapodam tą zagadkę w osobnym wątku.

            Tomek
    • cardemon Komentarz na gorąco - Re: Wybrakowane naboje 08.10.03, 00:11
      To jeszcze nie jest ten "następny post" przeze mnie zapowiadany. :)
      Omówienie rozwiązania i oficjalne wyniki pojawią się dopiero wtedy, gdy jury
      rozpatrzy rozwiązania Marchewy, Mesquaki i Krzyśka, zgodnie z tym, co mówi
      punkt trzeci regulaminu niniejszej zagadki. Jury nie wymaga przedstawienia
      pełnego rozwiązania i zadowoli się jedynie końcowym równaniem prowadzącym do
      zgłoszonej liczby (plus jakiś lapidarny komentarz). Oczywiście w przypadku
      wątpliwości jury może zwrócić się o dalsze wyjaśnienia. Rozwiązanie Stomka jest
      poza wszelkimi wątpliwościami i tu już na pewno wiadomo, że jest on zwycięzcą
      niniejszej zagadki.

      No dobrze, ale nie o tym teraz chciałem napisać. Zabieram głos, bo muszę kilka
      rzeczy na gorąco skomentować, póki emocje jeszcze nie opadły. Po pierwsze
      zagadka wydawała mi się super trudna, a tymczasem nie "przeżyła" nawet 24
      godzin. Przyznaję, że było to dla mnie duże zaskoczenie. Wielkie brawa! Po
      drugie walka i wyścig o pierwsze miejsce były niezwykle emocjonujące. Składam
      w związku z tym WSZYSTKIM łamigłówkowiczom, i to zarówno tym, którzy zajęli
      premiowane miejsca ja i tym, którzy wymyślili rozwiązania plasujące ich na
      dalszych pozycjach, ogromne słowa uznania. To dzięki Wam rozegrała się tutaj
      pasjonująca i pełna dramatyzmu walka.
      Mam też kilka ciepłych słów dla Tororo i to wcale nie dlatego, że mi ostatnio
      schlebił ;) (Pytanie do Stomka Autor: tororo Data: 07.10.2003 21:04). Twoja
      postawa i tandem z Alpem oraz Twoja uporczywa walka w każdej zagadce
      konkursowej są naprawdę imponujące! I już za to należy Ci się choćby jeden
      punkt w naszej rywalizacji, ale wiadomo, że jury musi być bezstronne, nieugięte
      i nie ulegające emocjom... :)

      Na końcu kilka przemyśleń. Wydaje mi się, że konkurs zyskuje coraz większe
      audytorium, co bardzo cieszy, bo taki był pierwotny nasz - Marchewy i mój –
      zamysł (skąd się wziął ten konkurs? – odpowiedź na wątku "Konkurs
      Łamigłówkarski..."). Czuję natomiast pewną gorycz w związku z tym, że kilka
      osób, a myślę tu z poczuciem winy o Ullerze i Pafcio, nie "załapało się" na
      niniejszą zagadkę z powodu niezbyt szczęśliwej pory jej ogłoszenia i
      zamieszczenia. Jest mi z tego powodu bardzo przykro i natychmiast wyciągam
      wnioski z tego błędu. Ogłoszenie następnej łamigłówki odbędzie się z
      odpowiednim wyprzedzeniem, tak żeby nikt nie mógł jej przegapić! Więcej wkrótce
      na ten temat w wątku "Konkurs Łamigłówkarski...", serdecznie zapraszam do
      dyskusji.

      Pozdrawiam wszystkich łamigłówkowiczów,

      Car de Mon
      • uller Komentarz na gorąco - Re: Wybrakowane naboje 08.10.03, 10:44
        Po pierwsze gratulacje za zamieszczenie bardzo ciekawej zagadki.
        Po drugie to nie ma co się przejmować, że ktoś czasem się nie załapie. Gdybyś
        zamieścił informację dwa dni wcześniej to i tak bym dowiedział się o niej
        wczoraj. Tak akurat się złożyło że nie odpalałem sieci przez weekend. Poza tym
        akurat w poniedziałek wkopywałem studzienkę odwodnieniową u siebie na działce i
        od świtu do nocy spędziłem dzień w błocie ze szpadelkiem. A wieczorem byłem tak
        zmęczony że nie miałem już sił na cokolwiek. Tak więc uważam że nic się nie
        stało, zwłaszcza że miałem sportową szansę rozwiązania tego zadania (całe 2h).
        W ubiegłym roku tuż przed finałem Mistrzostw Polski w Grach Matematycznych i
        Logicznych urodził mi się syn i pomimo tego że ten konkurs jest moją życiową
        pasją musiałem sobie odpuścić.
        Jeżeli chodzi o mnie to zapowiedz zadania wystarczy ogłosić 36h wcześniej.
        Wówczas gdy będzie taka możliwość na pewno zmogę się z kolejnym zadaniem.
        Pozdrawiam - Uller
Inne wątki na temat:

Popularne wątki

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka