12 skrzyń z monetami

[smiechowiec]

Król Namir zgromadził 12 skrzyń pełnych monet.
W każdej skrzyni było po 511 monet.
9 skrzyń zawierały monety z czystego złota ważące po 20g,
w 3 skrzyniach były monety jedynie pozłacane o wadze 19g.
Król ogłosił konkurs na znalezienie 3 skrzyń za pomocą jednego ważenia na wadze o dokładności 1g, ale sam myślał, że zadania zrobić się nie da.
Rozumował tak: by być pewnym, które skrzynie zawierają fałszywe monety należy wziąć
z pierwszej skrzyni 1 monetę z drugiej 2, z trzeciej 4, z czwartej 8 itd...
Jednak monet w skrzyniach było za mało, aby ta metoda mogła się powieść.
Aż zjawił się Elpirt Canobif, który rozwiązanie podał.
Jak to zrobił ?

[kornel-1]

Z 1 skrzyni 1 monetę
Z 2 skrzyni 2 monety
........
........
Z 7 skrzyni 25 monet
........
........
Z 12 skrzyni 410 monet.


Mogłem się gdzieś machnąć, bo liczyłem na kartce papieru.

[kornel-1]

Z 12 skrzyni 510 monet (literowka)

[smiechowiec]

Być może Twoje rozwiązanie jest poprawne, trudno mi to zweryfikować.
Znam inne, w którym nie pobieram 25 i 510 monet.
Przepis na liczbę pobieranych monet Tworzy pewien ciekawy ciąg :)

[kornel-1]

smiechowiec napisał:

> Być może Twoje rozwiązanie jest poprawne, trudno mi to zweryfikować.

Zatem uzupełnię ciąg. Kolejne pobrania:
1, 2, 3, 5, 8, 14, 25, 45, 82, 150, 278, 510

> Znam inne, w którym nie pobieram 25 i 510 monet.

Chętnie się z nimi zapoznam.

> Przepis na liczbę pobieranych monet Tworzy pewien ciekawy ciąg :)

Patrzyłem na oeis.org/. Nie ma go.

Kornel

[kornel-1]

Sprawdziłem rozwiązanie w Excelu. Moje próby pobrane ze skrzyń ważą od 21522 do 22454 gramów i żaden wynik ważenia (220 kombinacji) się nie powtarza.

k

[smiechowiec]

Jestem pod wrażeniem Twojego rozwiązania.
Sprawdziłem sumy i potwierdzam, że wszystko się zgadza.
Brawo Kornelu!

Podam rozwiązanie, które znam 0 1 2 4 7 13 24 44 81 149 274 504.
Stanowi ono pewien ciąg, który bez problemu odgadniesz.
Z tego co słyszałem to ciąg ten jest rozwiązaniem ogólnym tego typu problemu
tzn pozwala łatwo policzyć kolejne wartości dla dowolnej liczby skrzyń np. 20 czy 30.
Twoje rozwiązanie musi być bardziej optymalne i ciekawy jestem w jaki sposób dobierałeś kolejne liczby.

[smiechowiec]

Przyglądając się Twoim liczbom wydaje mi się, że pierwsze 10 z nich równa się wyraz z podanego przeze mnie ciągu +1

[kornel-1]

smiechowiec napisał:

> Jestem pod wrażeniem Twojego rozwiązania.
> Sprawdziłem sumy i potwierdzam, że wszystko się zgadza.
> Brawo Kornelu!

Dzięki.
Ja z kolei jestem zadowolony z tego, ze nie szukałem rozwiązania maszynowo lecz na kartce papieru (i to bez kalkulatora).

> Twoje rozwiązanie musi być bardziej optymalne i ciekawy jestem w jaki sposób do
> bierałeś kolejne liczby.

1. Na początku przypominałem sobie "klasyczne" rozwiązanie, gdy bierze się ze skrzyń kolejne potęgi 2. Tu treść Twojej zagadki stanowiła podpowiedź i jednocześnie wskazanie, gdzie jest problem (niewystarczająca liczba monet w ostatniej skrzyni). Notabene rozwiązanie z ciągiem 2^n dotyczy jednej fałszywej skrzyni. Przyjąłem hipotezę, że wartość 510 monet nie jest przypadkowa lecz dobrana "na styk". To na razie nie miało znaczenia.

2. Uświadomiłem sobie, że konkretna różnica mas między monetami 20-19=1 pozwala na łatwiejsze poszukiwanie rozwiązania. Zamiast liczb 19 i 20 używałem "w myśli" 0 i 1 (gramów). Przykładowo, wiedziałem, że jeśli wezmę po 1 monecie z każdej ze skrzyń, to całość będzie lżejsza o 3 gramy od wagi wyłącznie monet prawdziwych. Pozostało do wyjaśnienia - jak odróżnić, z których skrzyń są wyjęte fałszywe.

3. Wypisałem sobie tabelkę dla 4 skrzyń (potem dla 5... 6... może 7) i wszystkie możliwe kombinacje fałszywych skrzyń:
Numery skrzyń N - Fałszywe skrzynie 0/1 - Liczby monet pobranych X - Sumaryczna waga S
----N----*----X----*-S
1 2 3 4 * 1 2 3 4
-------------------------
1 1 1 0 * 1 2 3 0 * 6
1 1 0 1 * 1 2 0 4 * 8
1 0 1 1 * 1 0 3 4 * 8
0 1 1 1 * 0 2 3 4 * 9

Jak widać powtarzają się dwie ósemki - kombinacja 2 i 3 jest nie do odróżnienia!

Zmieniałem liczbę pobranych monet:

----N----*----X----*-S
1 2 3 4 * 1 2 3 5
-------------------------
1 1 1 0 * 1 2 3 0 * 6
1 1 0 1 * 1 2 0 5 * 8
1 0 1 1 * 1 0 3 5 * 9
0 1 1 1 * 0 2 3 5 * 10

Tu już jest ok.

-----N-----*-----X-----*-S
1 2 3 4 5 * 1 2 3 5 6
-------------------------
1 1 1 0 0 * 1 2 3 0 0 * 6
1 1 0 1 0 * 1 2 0 5 0 * 8
1 1 0 0 1 * 1 2 0 0 6 * 9
1 0 1 1 0 * 1 0 3 5 0 * 9 stop!
1 0 1 0 1 *
1 0 0 1 1 *
0 1 1 1 0 *
0 1 1 0 1 *
0 1 0 1 1 *
0 0 1 1 1 *

W tym miejscu sobie uświadomiłem, że nie warto sprawdzać sum poniżej 9 (bo mogą się powtórzyć). Najbliższą "właściwą" sumą jest 11, co oznacza, że kolejną liczbą w ciągu musi być "bezpiecznie" 8 (11-1-1-1=8; 10 było sumą max. przy 4 skrzyniach)

Potem już poszło łatwo, np. max suma dla N=9 wynosi 24+45+82=151 więc dla N=10 liczba pobranych monet X wynosi 150 (nieco trudno jest odtworzyć tok myślenia, sorry).

4. Sprawdziłem w encyklopedii ciągów początkowe wyrazy 1 2 3 5 8 14 25. Znalazłem różne ciągi, ale żaden z nich nie miał kolejnych tych samych wyrazów.

> Podam rozwiązanie, które znam 0 1 2 4 7 13 24 44 81 149 274 504.


Później, już po zamieszczeniu odpowiedzi, wygenerowałem arkusz Excela i zauważyłem, że jest wiele rozwiązań, np można zmienić 510 na 509. Tak więc moje rozwiązanie nie jest optymalne w sensie minimalizacji liczby pobranych monet.

> Stanowi ono pewien ciąg, który bez problemu odgadniesz.
> Z tego co słyszałem to ciąg ten jest rozwiązaniem ogólnym tego typu problemu
> tzn pozwala łatwo policzyć kolejne wartości dla dowolnej liczby skrzyń np. 20 c
> zy 30.

To jakieś uogólnienie ciągu Fibonacciego (?)

Kornel

[smiechowiec]

Dzięki, za wyjaśnienia.
Rozwiązanie analityczne zawsze wydaje mi się bardziej wartościowe niż brute force,
między innymi dlatego, że pozwala zmierzyć się z problemami o większej złożoności,
dla których sprawdzenie wszystkich możliwości zajęłoby zbyt wiele czasu.
Chwała Ci za to.

Gdy wpiszesz liczby rozwiązania na stronie, którą podałeś dostaniesz podpowiedź Tribonacci numbers.

Nie sprawdziłem tego, ale na podstawie pierwszych 10 liczb przypuszczam, że dwie ostatnie liczby, w podanym przez Ciebie rozwiązaniu, można by podmienić na 275 i 505.
Pzdr

[kornel-1]

smiechowiec napisał:

> Nie sprawdziłem tego, ale na podstawie pierwszych 10 liczb przypuszczam, że dwi
> e ostatnie liczby, w podanym przez Ciebie rozwiązaniu, można by podmienić na 27
> 5 i 505.

Tak, można (ja wpisuję teraz ciąg do Excela i szybko się sprawdza rozwiązania).
Podoba mi się rozwiązanie z zerem na początku.

k.