14 monet

[stomek]

Zagadka dla miłośników wałkowania wciąż tego samego tematu :-)
Jest ona "produktem ubocznym" zagadki konkursowej o wybrakowanych
nabojach, a jej powstanie było inspirowane przez Tororo.
forum.gazeta.pl/forum/72,2.html?f=514&w=8356242&a=8384178
A oto treść:
Do mędrca przyszedł kupiec z prośbą o pomoc. Kupiec posiadał 14 monet,
z których dokładnie jedna była fałszywa. Różniła się wagą od prawdziwych
(które miały identyczną wagę), ale nie wiadomo czy była lżejsza czy cięższa.
Mędrzec dysponował starą wagą szalkową, która była w stanie wytrzymać
jeszcze tylko 3 ważenia :-)
Kupiec poprosił mędrca o odnalezienie fałszywej monety.
Mędrzec zadumał się na dłuższą chwilę. Nagle kupiec wyciągnął z kieszeni
jeszcze jedną monetę i rzekł do mędrca "Mam tu jeszcze jedną monetę,
o której wiem, że jest prawdziwa!".
1. Czy teraz mędrzec będzie w stanie pomóc kupcowi?
2. Czy dodatkowa moneta jest mędrcowi potrzebna?

Z góry zastrzegam, że sam nie znam odpowiedzi na pytanie 2!

powodzenia,
Tomek

14 monet - dodatkowe wyjaśnienia

[stomek]

> 1. Czy teraz mędrzec będzie w stanie pomóc kupcowi?
> 2. Czy dodatkowa moneta jest mędrcowi potrzebna?

Żeby nie było wątpliwości:
* w pytaniu 1 chodzi o to czy mając dodatkową monetę medrzec sobie poradzi
* w pytaniu 2 chodzi o to czy poradzi sobie bez tej monety

Na pytanie 1 znam odpowiedź, na 2 nie znam.
Jeżeli ktoś uważa, że odpowiedź na pytanie 1 jest twierdząca to oczywiście
wskazane jest podanie planu ważenia.

Tomek

[marchewa4]

> 2. Czy dodatkowa moneta jest mędrcowi potrzebna?
>
> Z góry zastrzegam, że sam nie znam odpowiedzi na pytanie 2!

Sprobuje udowodnic, ze bez niej sie nie da.
Mamy nastepujace 14 rozroznialnych stanow:
01. (0,0,0)
02. (-1,-1,-1) lub (1,1,1)
03. (-1,-1,0) lub (1,1,0)
04. (-1,-1,1) lub (1,1,-1)
05. (-1,0,-1) lub (1,0,1)
06. (-1,0,0) lub (1,0,0)
07. (-1,0,1) lub (1,0,-1)
08. (-1,1,-1) lub (1,-1,1)
09. (-1,1,0) lub (1,-1,0)
10. (-1,1,1) lub (1,-1,-1)
11. (0,-1,-1) lub (0,1,1)
12. (0,-1,0) lub (0,1,0)
13. (0,-1,1) lub (0,1,-1)
14. (0,0,-1) lub (0,0,1)

Pytanie brzmi czy da sie ulozyc kule na szalkach wagi tak, aby te 14 stanow
rozroznic. Przyjmijmy, ze 1 na danej pozycji oznaczy, ze kule nr x kladziemy na
szalke prawa, -1 ze na lewa, 0, ze w tym wazeniu kula x nie bierze udzialu.
Oczywiste jest, ze przy kazdym wazeniu na obu szalkach musi lezec tyle samo kul
(inaczej wazenie to nie przynosi nam zadnej informacji).
Dla kul od 1 do 14 mozemy wbierac sposrod dwoch mozliwosci.
Musimy poskladac taka kombinacje, zeby na kazdej z trezch pozycji jedynek i
minusjedynek bylo tyle samo. Zauwazcie jednak, ze wartosci niezerowach na
pozycji 1 jest 9. Nie da sie zatem dobrac takich wazen, zeby 1 i -1 bylo tyle
samo.
Mnie to przekonuje, a Was?

Pozdrowienia
M.

[marchewa4]

Wykorzystujac to, co napisalem poprzednio mozna pokazac jak zrobi to majac 15
prawdziwa monete.
Wybierzmy nastepujace 14 stanow:
1. (0,0,0)
2. (1,1,1)
3. (-1,-1,0)
4. (1,1,-1)
5. (-1,0,-1)
6. (1,0,0)
7. (-1,0,1)
8. (1,-1,1)
9. (-1,1,0)
10. (1,-1,-1)
11. (0,1,1)
12. (0,-1,0)
13. (0,1,-1)
14. (0,0,1)

Przy kazdym wazeniu mamy na prawej szali o jedna monete wiecej niz na lewej.
Dodajemy zatem te 15. prawdziwa monete przy kazdym wazeniu na lewa szale i juz
rozroznimy te falszywa.

Podam moze jeszcze wynikajacy z tego plan wazen:
(03,05,07,09,15) <-> (02,04,06,08,10)
(03,08,10,12,15) <-> (02,04,09,11,13)
(04,05,10,13,15) <-> (02,07,08,11,14)

Pozdrowienia
M.

[stomek]

Jeżeli przypiszemy stany do monet to dla każdej monety mamy
narzucony plan ważenia: kiedy nie jest ważona oraz w jaki sposób
zmienia szalkę (ale sami możemy wybrać od której szalki zaczyna).

Faktycznie przy każdym ważeniu mamy dokładnie 5 pozycji zerowych
co oznacza, że musimy ważyć 14-5=9 kul i nie da się na każdą
szalkę położyć równej liczby monet. Potrzebna jest jeszcze jedna
prawdziwa.

Gratulacje. To chyba faktycznie jest dowód oraz odpowiedź na moje
pytanie z postu:
forum.gazeta.pl/forum/72,2.html?f=514&w=8356242&a=8388672
Nie zawsze mając k możliwych wyników "testów" jesteśmy w stanie
skonstruować plan pozwalający jednoznacznie wskazać jedną z k możliwych
odpowiedzi.

W każdym bądź razie wyznaczenie liczby możliwych wyników "testów" pozwala
oszacować z góry rozwiązanie i trochę sugeruje jakie ono będzie. Intuicyjnie
możliwy do uzyskania wynik powinien być chyba bliski temu maximum?
Czy ktoś zna przykłady, w których tak nie jest?

Tomek

P.S.
Właśnie opracowuję kolejną ciekawą zagadką z ważeniem monet,
ale przy pewnych dodatkowych założeniach. Szczegóły już niebawem.

[mesquaki]

Czy ten dowód działa także w przypadku, kiedy nie mamy z góry ustalonego planu
ważenia, ale zmieniamy go w zależności od wyniku wcześniejszego ważenia ?

[mesquaki]

Aha. Działa :)

[tororo]

stomek napisał:

> Zagadka dla miłośników wałkowania wciąż tego samego tematu :-)
> Jest ona "produktem ubocznym" zagadki konkursowej o wybrakowanych
> nabojach, a jej powstanie było inspirowane przez Tororo.

he he ciesze sie

> 2. Czy dodatkowa moneta jest mędrcowi potrzebna?

Jest.
Jesli mozemy wykonac n ważen i nie wiemy czy moneta jest lzejsza czy ciezsza
to wzor na liczbe monet m wsrod ktorych jestesmy w stanie wybrac fałszywa
wynosi

m= (3^n-3)/2
dla 3 prosty rachunek pokazuje ze jest to 12!
4 wazenia pozwalaja na wybor fałszywej monety sposród nie wiecej niz 39 monet.
a 5 wsrod 120 a 6 wsrod 363. Znam "rozkład jazdy" dla 39 monet. Wiekszych nie
spotkałem:))

Jesli zas wiemy czy moneta jest lzejsza czy ciezsza to m=3^n

Pozdr
Tororo

[marchewa4]

tororo napisał:

> m= (3^n-3)/2
> dla 3 prosty rachunek pokazuje ze jest to 12!

Nie zgadzam sie. Mozemy znalezc te falszywa wsrod 13, tyle ze nadal nie wiemy,
czy jest lzejsza czy ciezsza, ale o to nikt nie pytal ;-)

Pozdrowienia
M.

[tororo]

marchewa4 napisał:

> tororo napisał:
>
> > m= (3^n-3)/2
> > dla 3 prosty rachunek pokazuje ze jest to 12!
>
> Nie zgadzam sie. Mozemy znalezc te falszywa wsrod 13, tyle ze nadal nie
wiemy,
> czy jest lzejsza czy ciezsza, ale o to nikt nie pytal ;-)

Masz racje - wzor dotyczy sytuacji kiedy chcemy okreslić równiez czy fałszywa
moneta jest lzejsza czy cięższa.

[lotrzynapl]

Odpowiadam na pytanie 2 - chyba, ze odp. juz padla a ja nie potrafilem jej
wywnioskowac z waszych wywodow :-) Otoz do znalezienia falszywej monety wsrod
14 nie jest potrzebna 15 moneta prawdziwa. Znajdziemy te falszywa ale nie w
kazdym przypadku bedziemy wiedzieli czy jest lzejsza czy ciezsza ale zawsze
bedziemy wiedzieli, ktora to.

pozdr.
ALP

[marchewa4]

lotrzynapl napisał:

> Odpowiadam na pytanie 2 - chyba, ze odp. juz padla a ja nie potrafilem jej
> wywnioskowac z waszych wywodow :-) Otoz do znalezienia falszywej monety wsrod
> 14 nie jest potrzebna 15 moneta prawdziwa. Znajdziemy te falszywa ale nie w
> kazdym przypadku bedziemy wiedzieli czy jest lzejsza czy ciezsza ale zawsze
> bedziemy wiedzieli, ktora to.

Moim zdaniem to niemozliwe ale ... przekonaj mnie. Pokaz, prosze, plan wazen.

M.

[lotrzynapl]

No tak popelnilem blad :( Jednak sie nie da. Sorry, za to :( (zauwazylem
dopiero piszac kolejnosc wazen)

pozdr.
ALP