Fałszywa para
Fałszywa moneta pojawiła się po raz pierwszy w zadaniach matematycznych przed 70 laty. W najbardziej znanym klasycznym przykładzie ukrywa się wśród tuzina wyglądających identycznie. Różni się tylko minimalnie ciężarem, ale nie wiadomo, w którą stronę. Należy ją odszukać, wykonując tylko trzy ważenia na wadze dwuszalkowej bez odważników, czyli porównując ciężary monet umieszczanych na szalkach. W sieci jest sporo stron z tym zadaniem, trafiło ono nawet do Wikipedii.
Proponuję wariację na temat.
Monet jest sześć. Wyglądają tak samo, ale prawdziwe są cztery, ważące po 8 gramów. Waga każdej z dwóch fałszywych jest nieco inna, ale obie w sumie ważą 16 gramów. Ile co najmniej razy należy porównywać ciężary monet na wadze dwuszalkowej, aby wskazać obie fałszywe monety?
Komentarze
W klasycznej wersji zadania, tzn. gdy mamy 12 monet i jedna jest fałszywa, za pomocą 3 ważeń należy odnaleźć monetę fałszywą oraz dodatkowo stwierdzić, czy jest ona cięższa czy lżejsza od prawdziwej 🙂
Swego czasu pokusiłem się o rozwiązanie uogólnionej wersji zadania, tzn.: mamy dane n monet, wśród których znajduje się jedna fałszywa. Mając do dyspozycji wagę szalkową i k ważeń należy odnaleźć monetę fałszywą oraz określić czy jest cięższa czy lżejsza od monety prawdziwej.
W tak postawionym problemie naturalne wydaje się znalezienie zależności pomiędzy wartościami n i k, a konkretnie znalezienie odpowiedzi na następujące pytanie: jaka może być maksymalna wartość n, aby dla ustalonej liczby ważeń k istniała strategia odnalezienia monety fałszywej.
Odpowiedź na pytanie: n = (3^k – 1) / 2 + 2 – k
Oczywiście jest to wartość największa z możliwych, tzn. gdy weźmiemy o jedną monetę więcej, to k ważeń może nam nie wystarczyć.
k=3, n=12
k=4, n=38,
k=5, n=118
k=6, n=360
k=7, n=1088
…
Zastanówmy się, ile ważeń możemy potrzebować.
Każde ważenie daje nam trzy możliwe wyniki. Zatem za pomocą jednego ważenia możemy znaleźć jedno z maksymalnie trzech możliwych rozwiązań, za pomocą dwóch ważeń możemy znaleźć jedno z maksymalnie dziewięciu rozwiązań i ogólnie, za pomocą k ważeń możemy znaleźć jedno z maksymalnie 3^k rozwiązań.
Pytanie, ile jest możliwych wszystkich rozwiązań? Monetę cięższą możemy wybrać spośród wszystkich na 6 sposobów, a następnie monetę lżejszą na 5 sposobów (spośród pozostałych 5 monet). Zatem liczba wszystkich układów monet fałszywych wynosi 6*5 = 30. To oznacza, że 3 ważenia, to trochę za mało.
Poniżej przedstawiam strategię, która pozwala znaleźć fałszywe monety w 4 ważeniach.
Monety oznaczamy literami A, B, C, D, E i F.
1 ważenie: porównujemy wagę monet ABC z wagą monet DEF
1a – ABC>DEF (tzn. waga monet ABC jest większa niż waga monet DEF) – wtedy moneta cięższa jest w zbiorze ABC a moneta lżejsza w zbiorze DEF. W tym przypadku w drugim ważeniu porównujemy ciężary monet A i B – i na podstawie wyniku bez problemu określamy, która z monet ABC jest cięższa od pozostałych oraz w trzecim ważeniu porównujemy monety D i E – znajdując monetę lżejszą. Zatem przy braku równowagi w pierwszym ważeniu wystarczą nam tylko 3 ważenia
1b – ABC<DEF – to jest przypadek symetryczny do 1a
1c – ABC=DEF – w tym przypadku obie fałszywe monety trafiły na jedną szalkę w pierwszym ważeniu. W drugim ważeniu możemy porównać ciężary monet A i B – albo są równe, wtedy fałszywe są wśród DEF oraz monety ABC są prawdziwe, albo nie są równe – wtedy fałszywe są wśród ABC oraz monety DEF są prawdziwe. W obu przypadkach za pomocą pozostałych dwóch ważeń łatwo zidentyfikować, która moneta jest jaka.
Teraz zmieniamy nieco podejście. Polecenie brzmiało: "wskaż obie fałszywe monety". To znaczy, że nie trzeba umieć określić, która z tych wskazanych monet jest cięższa, a która lżejsza.
Takie podejście oznacza, że mamy tylko 15 możliwych rozwiązań. A to może oznaczać, że jednak 3 ważenia okażą się wystarczające. Czy tak jest? Nie wiem. Jeszcze… 😉
Wystarczą trzy ważenia.
Tworzymy dwie grupy po trzy monety. (ABC,DEF)
Ważymy je. Mogą zachodzić dwa przypadkI:
1. Grupy monet się równoważą A+B+C=D+E+F
2. Grupy monet są w nierównowadze. A+B+C>D+E+F
1. przypadek
Wiemy, że obie fałszywe monety są w jednej z grup
Wybieramy po dwie monety z obu grup (AB, DE), ważymy
1. Jeżeli są w równowadze, to ważymy monety z dowolnej grupy np. (A,B). Jeżeli są w równowadze to fałszywe są DE.
2. Jeżeli cięższe (lżejsze) są AB to fałszywa jest C i cięższa (lżejsza) z pary AB. Jeżeli cięższe (lżejsze) są DE to fałszywa jest F i cięższa (lżejsza) z pary DE.
——————————————————-
2. przypadek A+B+C<C+D+E
Wiemy, że lżejsza moneta jest w grupie ABC, cięższa w DEF. Teraz wystarczy zważyć
dwie dowolne monety z każdej z grup.
Wychodzą mi 4 porównania. Jeśli „tak” to podaję sposób, jeśli „nie” to szukam dalej 🙂
„Nie”, ale może nie uwzględnia Pan tego, że wystarczy wskazać „fałszywki”, bez wskazywania, która jest cięższa, a która lżejsza.
mp
Udało mi się znaleźć klasyczny problem z ważeniem w serwisie z zadaniami programistycznymi:
http://www.spoj.com/problems/KULE/
Zadanie polega na napisaniu programu, który będzie zadawał pytania o wynik ważenia przekazanych na wage kul oraz po możliwie najmniejszej liczbie zadanych pytań udzieli odpowiedzi, która kula jest fałszywa.
No właśnie, mój sposób wskazuje, która jest, która 🙂 , szukamy więc tego co trzeba …
Co najmniej trzy ważenia.
Nie umiem zejść poniżej 4 w worst case scenario… W pierwszym ważeniu kładziemy po 3 monety, i jak nie ma równowagi, to lżejsza jest tu, a cięższa tam, i po jednym ważeniu potrzeba by je zidentyfikować, a więc 3 ważenia w sumie. Jak jest równowaga, to obie trefne są na jednej szalce. Porównujemy dwie monety w drugim ważeniu z tej samej losowo wybranej szalki, jeśli któraś przeważy, to po kolejnym ważeniu jesteśmy w domu. Ale jak będzie równowaga, to znaczy że monety lżejsza, typowa i cięższa są na drugiej szalce, i w jednym ważeniu ich możemy nie zidentyfikować, potrzeba dwóch.
Moim zdaniem w złośliwym 😉 przypadku potrzebne będą cztery ważenia, w szczęśliwym – tylko dwa. A w większości przypadków – trzy. Pozdrawiam, Ola
1. ważenie – kładę na szalkach po trzy monety: ABC v DEF
Efekt ważenia:
1A) szalki są w równowadze: ABC = DEF; wniosek: obie złe monety są na jednej szalce
1b) szalki nie są w równowadze: ABC > DEF; wniosek: wśród ABC są 2 dobre monety i jedna cięższa, a wśród DEF są 2 dobre monety i jedna lżejsza
2. ważenie po wyniku 1A) – zamieniam miejscami po jednej monecie z każdej szalki: ABF v DEC
Efekt ważenia:
2A) szalki są w równowadze: ABF = DEC; wniosek: zła jest para AB lub para DE
2B) szalki nie są w równowadze: ABF > DEC; wniosek: moneta F jest cięższa; lżejszą monetą jest D lub E
3. ważenie po wyniku 2A) – porównuję ze sobą monety: A v B
Efekt ważenia:
– szalki są w równowadze: A = B; wniosek: złe są monety D i E
– szalki nie są w równowadze: A > B; wniosek: złe są monety A i B
3. ważenie w wariancie 2B) – porównuję ze sobą monety: D v E
Efekt ważenia:
– jeśli D > E, to zła jest moneta E
– jeśli E > D, to zła jest moneta D
——————————
2. ważenie po wyniku 1b) – zamieniam miejscami po jednej monecie z każdej szalki: ABF v DEC
Efekt ważenia:
2a) szalki są w równowadze: ABF = DEC; wniosek: C jest monetą fałszywą cięższą, a druga fałszywa to D lub E
2b) szalki nie są w równowadze: ABF > DEC; wniosek: monety C i F są dobre; wśród AB jest jedna dobra i jedna cięższa, a wśród DE jest jedna dobra i jedna lżejsza
2c) szalki nie są w równowadze: ABF E, to zła jest moneta E
– jeśli E > D, to zła jest moneta D
3. ważenie po wyniku 2b): FC v AD
Efekt ważenia:
– jeśli FC > AD, to A jest dobre, a D jest lżejsze, czyli E jest dobre, a B jest cięższe
– jeśli FC < AD, to A jest cięższe, a D jest dobre, czyli B jest dobre, a E jest lżejsze
– jeśli FC = AD, to AD są obie dobre albo obie złe (4. ważenie rozstrzygnie sprawę)
Zauważyłam, że brakuje fragmentu mojego tekstu. Począwszy od 2c) powinno być tak:
2c) szalki nie są w równowadze: ABF E, to zła jest moneta E
– jeśli E > D, to zła jest moneta D
3. ważenie po wyniku 2b): FC v AD
Efekt ważenia:
– jeśli FC > AD, to A jest dobre, a D jest lżejsze, czyli E jest dobre, a B jest cięższe
– jeśli FC < AD, to A jest cięższe, a D jest dobre, czyli B jest dobre, a E jest lżejsze
– jeśli FC = AD, to AD są obie dobre albo obie złe (4. ważenie rozstrzygnie sprawę)
A można jeszcze tak: porównujemy monety pojedynczo, mamy 3 pary i 3 ważenia, chyba że już w dwóch pierwszych okaże się, że w różnych parach są cięższa i lżejsza moneta. Jeśli w dwóch z trzech ważeń jest równowaga, to mamy obie monety w trzeciej parze, a jeśli powiedzmy moneta a okazuje się cięższa od b, a moneta c od d, to kładziemy po jednej stronie a i b, a po drugiej c i d. i albo a okazuje się cięższa i d lżejsza, albo c cięższa i b lżejsza. Czyli w najgorszym przypadku 4 ważenia wystarczą.
Nie wiem czy dobrze zrozumiałem rozwiązanie, które przedstawił @antyp1958… Pierwsze ważenie, jasne. W drugim zdejmujemy po jednej monecie, i jeśli jest równowaga, to jeszcze jedno ważenie wystarczy. Ale jeśli równowagi nie ma, to wiemy na pewno, że fałszywa jest moneta c albo (bo nie obie jednocześnie) f. Wiemy która w którą stronę, ale nie wiemy, która. Możliwości są, że c i jedna z pary a, b – albo f i jedna z pary d,e. Jeśli porównamy a z b i wyjdzie równowaga, to znaczy że jest f i jedna z pary d, e, i musimy w czwartym ważeniu wykryć, która. Moim zdaniem nie da się jednym ważeniem określić, która z czwórki a, b, d, e będzie tą drugą fałszywą. Każda sytuacja ma awers i rewers, jak to z monetami.
Co do rozwiązania @OliGM, to w punkcie 2B wniosek jest, że moneta f jest cięższa, a któraś z d, e lżejsza… no ale może być też, że moneta c jest lżejsza, a któraś z a, b cięższa. Przy czym przy tym przekładaniu należy zgarnąć od razu całą szóstkę z szalek, żeby po drodze nie mieć informacji z sytuacji pośredniej, bo to będzie dodatkowe ważenie 🙂 Dalej się troszkę pogubiłem, no ale tutaj też są w najgorszym przypadku 4 ważenia.
Coś czuję, że to jeszcze nie koniec tego zadania 🙂
@antyp
Wystarczą trzy ważenia.[??? wyciąłem niepotrzebne zdania z wpisu i policzyłem wazenia]
Tworzymy dwie grupy po trzy monety. (ABC,DEF)
Ważymy je. chodzić dwa przypadkI:
1 wazenie->1. Grupy monet są w równowadze. A+B+C=D+E+F
1. przypadek
Wiemy, że obie fałszywe monety są w jednej z grup
Wybieramy po dwie monety z obu grup (AB, DE), ważymy
2 wazenie wyszło -> ab>de
[1. Jeżeli są w równowadze,……..]
2. Jeżeli cięższe (lżejsze) są AB[załózmy, ze A=B, 3 wazenie] to fałszywa jest C i cięższa (lżejsza) z pary AB.
Jeżeli cięższe (lżejsze) są DE to fałszywa jest F i cięższa (lżejsza) z pary DE [która? D czy E, 4 ważenie, zeby sprawdzić?].
@Antyp1958: Masz błąd w punkcie 2 (nad kreską).
Nie wiesz czy AB brałeś z szalki z dwoma fałszywymi czy wszystkimi dobrymi monetami a w dowodzie przyjąłeś, że z tej z fałszywymi.
@Antyp1958
W sytuacji gdy:
1 ważenie: ABC=DEF
2 ważenie: AB>DE
ciągle mamy 4 możliwe rozwiązania (X+Y- oznacza, że moneta X jest cięższa a Y lżejsza):
A+C-
B+C-
D-F+
E-F+
zostało 3 ważenie i 4 rozwiązania – nie da się tym jednym ważeniem znaleźć rozwiązania.
Ogólnie wydaje mi się, że nie da się znaleźć fałszywej pary w 3 ważeniach. Nie potrafię podać prostego argumentu, wniosek formułuję na podstawie wielu rozważonych możliwości.
Panie Marku, da się w 3 ważeniach?
Da się w 3, jeśli wystarczy wskazać fałszywe monety, bez ustalania relacji między nimi.
m
Problem w tym, że wcale mi nie zależy na ustalaniu relacji między nimi, to jakoś samo wychodzi 🙂 Jakiekolwiek ważenie powiązane jest z tym, że w jego wyniku coś może być cięższe, a coś lżejsze, i trudno nie uwzględniać tej informacji. No nic, zawsze to jakaś podpowiedź, uprasza się o niepodawanie poprawnego rozwiązania jeszcze przez jakiś czas, albo nie będę zaglądał.
Panie Marku.
Napisałem sobie program, który sprawdza kolejno wszystkie możliwe przypadki ważeń i wychodzi mi, że nie da się znaleźć rozwiązania w 3 ważeniach (oczywiście mówiąc o rozwiązaniu mam na myśli parę monet fałszywych, bez konieczności wskazania która jest jaka).
Czy zna Pan rozwiązanie? Jeśli tak, to chciałbym je zobaczyć.
W tej sytuacji nie pozostaje mi nic innego jak… przyznać się do błędu. Pomyliły mi się dwie bardzo podobne wersje zadania.
A mianowicie: trzy ważenia wystarczą, jeśli masy obu fałszywych monet będą wprawdzie różne, ale większe od masy monet prawdziwych.
Przepraszam za zamieszanie.
mp
Zgadza się, jest błąd, ale nie śmiałem nic mówić, bojąc się, że nie mam racji.
Mi wyszło, że możliwych jest 15 kombinacji monet: 6!/(4!2!)=15
natomiast możliwości 3-ech ważeń jest tylko 14.
=równe
+nierówne
-nierówne w drugą stronę:
1.===
2.=++
3.=+-
4.+=+
5.+=-
6.++=
7.+-=
8.==+
9.=+=
10.+==
11.++-
12.+-+
13.-++
14.+++
i koniec, nie ma 15-tej kombinacji.
A już szukałem błędu w swoim programie 🙂
W wersji z dwiema moneta cięższymi (przy założeniu, że obie mają jednakową wagę) komputer wygenerował następujące rozwiązanie z 3 ważeniami:
(1) A ciezsze od B
(2) A ciezsze od C
(3) D ciezsze od E
(3) rozwiazanie: A+D+
(3) D rowne E
(3) rozwiazanie: A+F+
(3) D lzejsze od E
(3) rozwiazanie: A+E+
(2) A rowne C
(2) rozwiazanie: A+C+
(2) A lzejsze od C
(2) rozwiazanie: sprzecznosc
(1) A rowne B
(2) A ciezsze od C
(2) rozwiazanie: A+B+
(2) A rowne C
(3) D ciezsze od E
(3) rozwiazanie: D+F+
(3) D rowne E
(3) rozwiazanie: D+E+
(3) D lzejsze od E
(3) rozwiazanie: E+F+
(2) A lzejsze od C
(3) D ciezsze od E
(3) rozwiazanie: C+D+
(3) D rowne E
(3) rozwiazanie: C+F+
(3) D lzejsze od E
(3) rozwiazanie: C+E+
(1) A lzejsze od B
(2) A ciezsze od C
(2) rozwiazanie: sprzecznosc
(2) A rowne C
(3) D ciezsze od E
(3) rozwiazanie: B+D+
(3) D rowne E
(3) rozwiazanie: B+F+
(3) D lzejsze od E
(3) rozwiazanie: B+E+
(2) A lzejsze od C
(2) rozwiazanie: B+C+
Ech… forum usunęło wcięcia w rozwiazaniu. Jeszcze raz:
(1) A ciezsze od B
—-(2) A ciezsze od C
——–(3) D ciezsze od E
————(3) rozwiazanie: A+D+
——–(3) D rowne E
————(3) rozwiazanie: A+F+
——–(3) D lzejsze od E
————(3) rozwiazanie: A+E+
—-(2) A rowne C
——–(2) rozwiazanie: A+C+
—-(2) A lzejsze od C
——–(2) rozwiazanie: sprzecznosc
(1) A rowne B
—-(2) A ciezsze od C
——–(2) rozwiazanie: A+B+
—-(2) A rowne C
——–(3) D ciezsze od E
————(3) rozwiazanie: D+F+
——–(3) D rowne E
————(3) rozwiazanie: D+E+
——–(3) D lzejsze od E
————(3) rozwiazanie: E+F+
—-(2) A lzejsze od C
——–(3) D ciezsze od E
————(3) rozwiazanie: C+D+
——–(3) D rowne E
————(3) rozwiazanie: C+F+
——–(3) D lzejsze od E
————(3) rozwiazanie: C+E+
(1) A lzejsze od B
—-(2) A ciezsze od C
——–(2) rozwiazanie: sprzecznosc
—-(2) A rowne C
——–(3) D ciezsze od E
————(3) rozwiazanie: B+D+
——–(3) D rowne E
————(3) rozwiazanie: B+F+
——–(3) D lzejsze od E
————(3) rozwiazanie: B+E+
—-(2) A lzejsze od C
——–(2) rozwiazanie: B+C+
I jeszcze rozwiązanie zagadki z dwiema fałszywymi monetami, przy czym tym razem obie fałszywe monety mogą mieć różne wagi.
W rozwiązaniu stosuję następujące oznaczenia:
X?Y? – fałszywe są monety X i Y – i nie wiemy która z nich jest cięższa od drugiej
X+Y+ – fałszywe są monety X i Y – i ich waga jest jednakowa
X1Y2 – fałszywe są monety X i Y – i dodatkowo X jest lżejsze od Y
(1) A ciezsze od B
—-(2) B ciezsze od C
——–(2) rozwiazanie: B1A2
—-(2) B rowne C
——–(3) D ciezsze od E
————(3) rozwiazanie: A?D?
——–(3) D rowne E
————(3) rozwiazanie: A?F?
——–(3) D lzejsze od E
————(3) rozwiazanie: A?E?
—-(2) B lzejsze od C
——–(2) rozwiazanie: A?C?
(1) A rowne B
—-(2) C ciezsze od D
——–(3) D ciezsze od E
————(3) rozwiazanie: D1C2
——–(3) D rowne E
————(3) rozwiazanie: C?F?
——–(3) D lzejsze od E
————(3) rozwiazanie: C?E?
—-(2) C rowne D
——–(3) A ciezsze od C
————(3) rozwiazanie: A+B+
——–(3) A rowne C
————(3) rozwiazanie: E?F?
——–(3) A lzejsze od C
————(3) rozwiazanie: C1D2
—-(2) C lzejsze od D
——–(3) C ciezsze od E
————(3) rozwiazanie: D2C1
——–(3) C rowne E
————(3) rozwiazanie: D?F?
——–(3) C lzejsze od E
————(3) rozwiazanie: D?E?
(1) A lzejsze od B
—-(2) A ciezsze od C
——–(2) rozwiazanie: B2A1
—-(2) A rowne C
——–(3) D ciezsze od E
————(3) rozwiazanie: B?D?
——–(3) D rowne E
————(3) rozwiazanie: B?F?
——–(3) D lzejsze od E
————(3) rozwiazanie: B?E?
—-(2) A lzejsze od C
——–(2) rozwiazanie: B?C?
Rozszalałem się. Oto rozwiązanie zagadki z wpisu (tzn. dwie monety fałszywe, jedna cięższa, druga lżejsza i w sumie ważą tyle co dwie prawdziwe) dla ośmiu monet:
(1) AB ciezsze od CD
—-(2) A ciezsze od B
——–(3) BC ciezsze od DE
————(4) B ciezsze od D
—————-(4) rozwiazanie: A+D-
————(4) B rowne D
—————-(4) rozwiazanie: A+E-
————(4) B lzejsze od D
—————-(4) rozwiazanie: sprzecznosc
——–(3) BC rowne DE
————(4) F ciezsze od G
—————-(4) rozwiazanie: A+G-
————(4) F rowne G
—————-(4) rozwiazanie: A+H-
————(4) F lzejsze od G
—————-(4) rozwiazanie: A+F-
——–(3) BC lzejsze od DE
————(3) rozwiazanie: A+C-
—-(2) A rowne B
——–(3) ABE ciezsze od CFG
————(4) AB ciezsze od CE
—————-(4) rozwiazanie: H+C-
————(4) AB rowne CE
—————-(4) rozwiazanie: E+C-
————(4) AB lzejsze od CE
—————-(4) rozwiazanie: E+D-
——–(3) ABE rowne CFG
————(4) AB ciezsze od DF
—————-(4) rozwiazanie: H+D-
————(4) AB rowne DF
—————-(4) rozwiazanie: G+C-
————(4) AB lzejsze od DF
—————-(4) rozwiazanie: F+C-
——–(3) ABE lzejsze od CFG
————(4) A ciezsze od F
—————-(4) rozwiazanie: sprzecznosc
————(4) A rowne F
—————-(4) rozwiazanie: G+D-
————(4) A lzejsze od F
—————-(4) rozwiazanie: F+D-
—-(2) A lzejsze od B
——–(3) AC ciezsze od DE
————(4) A ciezsze od D
—————-(4) rozwiazanie: B+D-
————(4) A rowne D
—————-(4) rozwiazanie: B+E-
————(4) A lzejsze od D
—————-(4) rozwiazanie: sprzecznosc
——–(3) AC rowne DE
————(4) F ciezsze od G
—————-(4) rozwiazanie: B+G-
————(4) F rowne G
—————-(4) rozwiazanie: B+H-
————(4) F lzejsze od G
—————-(4) rozwiazanie: B+F-
——–(3) AC lzejsze od DE
————(3) rozwiazanie: B+C-
(1) AB rowne CD
—-(2) A ciezsze od E
——–(3) A ciezsze od B
————(3) rozwiazanie: A+B-
——–(3) A rowne B
————(4) F ciezsze od G
—————-(4) rozwiazanie: F+E-
————(4) F rowne G
—————-(4) rozwiazanie: H+E-
————(4) F lzejsze od G
—————-(4) rozwiazanie: G+E-
——–(3) A lzejsze od B
————(3) rozwiazanie: sprzecznosc
—-(2) A rowne E
——–(3) A ciezsze od F
————(4) A ciezsze od G
—————-(4) rozwiazanie: sprzecznosc
————(4) A rowne G
—————-(4) rozwiazanie: H+F-
————(4) A lzejsze od G
—————-(4) rozwiazanie: G+F-
——–(3) A rowne F
————(4) A ciezsze od C
—————-(4) rozwiazanie: D+C-
————(4) A rowne C
—————-(4) rozwiazanie: G?H?
————(4) A lzejsze od C
—————-(4) rozwiazanie: C+D-
——–(3) A lzejsze od F
————(4) A ciezsze od G
—————-(4) rozwiazanie: F+G-
————(4) A rowne G
—————-(4) rozwiazanie: F+H-
————(4) A lzejsze od G
—————-(4) rozwiazanie: sprzecznosc
—-(2) A lzejsze od E
——–(3) A ciezsze od B
————(3) rozwiazanie: sprzecznosc
——–(3) A rowne B
————(4) F ciezsze od G
—————-(4) rozwiazanie: E+G-
————(4) F rowne G
—————-(4) rozwiazanie: E+H-
————(4) F lzejsze od G
—————-(4) rozwiazanie: E+F-
——–(3) A lzejsze od B
————(3) rozwiazanie: B+A-
Ja zastanowiłem się nad jeszcze inną sprawą, mianowicie w zadaniu oryginalnym, z monetami cięższą i o tyle samo lżejszą, ile ważeń trzeba wykonać w najlepszym przypadku, by te monety zidentyfikować. Jedno ważenie to oczywiście za mało. Można w dwóch ważeniach: jeśli w pierwszym umieścimy po jednej monecie a i b i będzie równowaga, a w drugim c i d i to samo, to wiemy, że są to monety e i f. Jeśli umieścimy po dwie monety, ab i cd, i będzie równowaga, to wiemy, że są to monety ab, cd lub ef i teraz wystarczy trafić w dobrą parę, np. porównać a z b – jak równowagi nie będzie, to wiemy nawet dodatkowo, która cięższa, a która lżejsza, czego nie mamy w poprzednim przypadku. Rano myślałem, że nie da się znaleźć w dwóch ważeniach, jeśli zważymy w pierwszym po 3 monety, ale przed chwilą znalazłem i dla tego przypadku zaskakującą możliwość, nie będę podawał, może ktoś się pobawi.
@Wiąz: Czy mógłbyś naszkicować z grubsza swoje rozumowanie z ostatniego wpisu ? Jakie ważenia bierzesz pod uwagę ? Można ważyć pojedynczo, podwójnie albo potrójnie ……
@Spytko dowolne ważenie, nie ważne jest jakie. Masz 3 ważenia czyli masz 3 wyniki tych ważeń. Cokolwiek byś sobie wymyślił masz nadal 3 wyniki, jakakolwiek byś strategie nie wymyślił masz nadal 3 wyniki. Można zamiast wnioskować logicznie, ułożyć tabele wszystkich kombinacji wyników wam i odpowiadające im wyniki. Biorąc pod uwagę, że w tym wypadku nie ważne jest określenie, która moneta jest cięższa lub lżejsza, interesuje nas nie tyle, w którą stronę wychyli się szala, a raczej jeśli się wychodzi ponownie w próbie 3 ważeń, to czy w tą samą stronę, czy przeciwna. Takie rozumowanie prowadzi nas do tabeli z 14 zakodowanymi możliwościami, jakie wypisałem w poście.
@Spytko, jeszcze jedno, w przypadku kiedy obie monety są cięższe lub lżejsze, interesuje nas wychylenie jako takie bo określa jasno czy zła moneta jest po lewej lub prawej stronie ( lub obu stronach) mamy wtedy 3^3 stanów do zakodowania, czyli 27 możliwości. Dla 6 monet i 2 fałszywych daje nam 15 kombinacji, czyli mniej niż 27, a więc możliwe do rozwiązania. Kombinując ze wzorem n!/((n-k)!k!) na ilość kombinacji, można znaleźć inne liczby monet prawdziwych i fałszywych, przy których ich liczba jest mniejsza od na przykład 27, co daje max 3 ważenia.
Rozumiem Twój pomysł (przypomina ten, że nie da się pokryć dominem szachownicy bez rogów 🙂 ). Jednak nie mogę przełknąć tego, że możemy sobie tak po prostu zignorować ilości monet na szalkach. Jeśli przyjęlibyśmy, że jednak jest to istotne to mamy aż 27 różnych kombinacji dla każdej pozycji z Twojej listy 14-stu. Na pewno wiele z tych kombinacji będzie równoważnych a drugie tyle bezsensownych ale jest w czym wybierać. W każdym razie dzięki za odpowiedź, może czegoś nie widzę ale dopóki mnie nie olśni musimy pozostać przy swoich stanowiskach. A może ktoś z forumowiczów pomoże nam rozstrzygnąć spór jakimś nowym argumentem. Albo chociaż głosowanie kto ma racje. Jak będzie np. 5 do 1 dla któregoś z nas to uznamy to za dowód metodą probabilistyczną 🙂
@spytko, nie chodzi tu o ignorowanie liczby możliwych ważeń z różną liczbą monet. Chodzi o to, że mamy 3 ważenia, a każde ważenie może przyjąć 3 stany: =, > lub <. Daje nam to 27 możliwych kombinacji wyników... ale... Wszystko byłoby OK gdyby ważenie wykazywało gdzie jest moneta cięższa (lżejsza). W naszym wypadku tego nie wiemy ponieważ monety są dwie i jedna jest cięższa, a druga lżejsza. Wychylenie szalki w jakąś stronę nic nam nie mówi o tym gdzie jest moneta fałszywa. Natomiast jeśli szalka wychyli się w tę sama stronę lub w przeciwną w naszych 3 ważeniach, może nam coś powiedzieć, prawda? Dlatego ważne jest czy w naszych ważeniach szalki przechylą się w jakąś stronę, przechylą się ponownie w tę samą lub przeciwną stronę lub też będą w równowadze. Mamy 4 monety, dwie z nich są fałszywe, jedna lżejsza druga cięższa. Ważenie a>b nic nam nie mówi poza tym, że a lub b jest fałszywe.
Natomiast gdy w drugim wyniknie, że np. a jest lżejsze niż c, to możemy już wywnioskować, że a jest prawdziwe natomiast b i c fałszywe.
A jeśli drugie ważenie wyszłoby a>c, to wiemy, że a jest fałszywe, natomiast drugą monetą fałszywą jest b lub c lub d – która konkretnie, tego jeszcze nie będziemy wiedzieć.
Mam nadzieję, że przykład wytłumaczył dlaczego liczba możliwych kombinacji 3 ważeń została zredukowana do 14, a nie wynosi 27.
Chyba załapałem rozumowanie @Wiąza…
Taki dowód nie wprost: załóżmy, że istnieje Optymalna Strategia Ważeniowa, czyli OSW, która pozwala na wyznaczenie felernych monet w maksymalnie trzech ważeniach. Czyli mamy pierwszy krok, ważymy, jest wynik, dostosowujemy do niego drugi krok, wreszcie trzeci krok, i teraz mamy już wiedzieć. Otóż możliwości wyboru par monet jest 15. Jak obliczył @Wiąz, mamy tylko 14 różnych możliwości uzyskania sekwencji trzech ważeń, tak więc nawet w naszej OSW, jak sobie wszystko rozpiszemy, ze względu na zasadę szufladkową co najmniej jedna sekwencja +, =, – musi odpowiadać dwóm parom, nawet chyba mieliśmy tam taki przypadek, że było na pewno f, i nie wiedzieliśmy, czy d, czy e, potrzebne było czwarte ważenie.
Ja wskazałem też możliwości rozwiązania w dwóch ruchach – gdybyśmy takie uwzględnili w OSW, to jedna para monet odpowiadałaby więcej niż jednej sekwencji wyników ważeń, wszak w trzecim mamy wszystko jedno: = = +, czy ===, nieważne. A wtedy inne pary byłyby jeszcze bardziej poszkodowane i mniej byłoby dla nich sekwencji wyników ważeń do podziału.
Zmniejszmy liczbę monet do 5 – wtedy w 3 ważeniach się oczywiście da i nie jest bardzo trudno wpaść na OSW. Być może nawet jest więcej OSW, a co najmniej dwie – jedna, że w pierwszym ważeniu porównujemy po jednej monecie, a druga, że po dwie. No ale tutaj jest tylko 10 kombinacji na 14 sekwencji. Za to gdy weźmiemy 4 monety i spróbujemy w dwóch ważeniach, to się nie uda – sekwencji jest pięć (==, =+, +=, ++, +-), a par monet sześć, czyli znów dokładnie o jedną więcej, ciekawe, czy to przypadek. A z trzech monet też się w dwóch ważeniach nie da – tu odpada =, mamy tylko ++ lub +- i jeśli mamy pecha, to w dwóch kolejnych ważeniach ta sama moneta będzie dwa razy cięższa albo dwa razy lżejsza.
@aps1968 napisał:
„czyli znów dokładnie o jedną więcej, ciekawe, czy to przypadek.”
niezupełnie. Nie wiem jak to ma się do par monet, ale liczba tak skonstruowanych ważeń w stosunku do kompletnej liczby możliwości jest ściśle określona. Skoro interesuje nas zmiana wychylenia, a nie konkretna strona tego wychylenia, to zawsze będziemy mieli liczbę dwa razy mniejszą, z tym, że…
Każda kombinacja ma swoją kombinacje przeciwną (wychylenie w drugą stronę) oprócz jednej kombinacji: wszystkie próby ważenia w równowadze.
Dla 3 ważeń mamy liczbę 27 możliwych ważeń, w przypadku zainteresowania tylko zmianą wychylenia mamy (27-1)/2+1=14
ta ‚jedynka’ to uwzględnienie tej jedynej kombinacji bez ‚pary komplementarnej’ czyli wszystkich ważeń w równowadze.
Dla 2 ważeń mamy max 3^2 czyli 9, a dla naszego przypadku:
(9-1)/2+1=5
🙂
P.S. moja teoria na razie legła w gruzach dla parzystej liczby ważeń, ale nad tym zastanowię się później… coś się powtarza?
P.P.S. już wiem gdzie jest szkopuł dla parzystych: na przykład kombinacja ++–, jest symetryczna, więc:
dla nieparzystych ważeń mamy (n-pełna liczba kombinacji):
p=(n-1)/2+1
np=(n-2)/2+2
🙂
P. P. P. S głupoty piszę o tych parzystych ważeniach 🙂
@Wiąz
Jedna liczba jest postulowaną liczbą ważeń, druga liczbą monet. Spodziewamy się, że dla 4 monet moglibyśmy mieć 2 ważenia, a dla 6 – 3. Jednak nie, bo możliwości dla 4 monet mamy 6, a dla 2 ważeń 5, czyli o 1 za mało. Dla 6 monet 15, a 3 ważeń 14, znów o 1 za mało. Dalej jednak nie idzie już tak ładnie i np. dla 10 monet byłoby 45 możliwości, a dla 4 ważeń 41 – o 4 za mało. 4 ważenia powinny jednak zgodnie z tą teorią wystarczyć przy 8 monetach, gdzie możliwości wyboru pary jest 28, a to <41. Ciekawe, czy tak jest w rzeczywistości, trochę to ambitne, żeby 4 ważenia wystarczyły i przy 6, i przy 8 monetach. (Porównuję wyrażenia (3^liczbaważeń+1)/2 i liczbamonet*(liczbamonet-1)/2).
@Wiąz: Dlaczego rozróżniasz takie przypadki jak pozycje 6 i 7. Możemy mieć 6+8 mniejsze od 8+8 oraz 10+8 większe od 8+8 ale to ostatnie możemy zapisać 8+8 mniejsze od 10+8. Nie ma tu kryterium nakazującego którąś z tych dwóch wersji ostatniej nierówności. Idąc tym tropem możemy znacznie skrócić Twoją listę czternastu kombinacji.
@Spytko, szczerze mówiąc za bardzo nie rozumiem o co chodzi… Liczby kombinacji nie można skrócić… niby jak… to jest ściśle określone.
Natomiast jeśli chodzi o prędkość znalezienia monet fałszywych… wszystko zależy od strategii i od ‚miejsca’ monet… inne miejsce, inna strategia mogą dać szybsze lub późniejsze odkrycie, które monety są fałszywe, szczególnie gdy liczba kombinacji umieszczenia monet jest znacznie mniejsza od liczby kombinacji ważeń. Ale samej liczby kombinacji zmienić się nie da…. jest zależna tylko od liczby ważeń i od liczby możliwych wyników każdego ważenia. Jedyne ograniczenie w naszym/moim przypadku to takie, że interesuje mnie zmiana wychylenia szalki, a nie strona tego wychylenia.
@Wiąz
Ja zauważyłem, że w tym rozumowaniu właściwie nigdzie nie było wprost powołania się na to, że one są inne jedna w tę stronę, druga w drugą, tylko że w ogóle jakoś się odróżniają. Jeśli w przykładzie czterech monet i dwóch ważeń założymy, że dwie monety różnią się wagą „na plus”, to damy radę.
Jeśli każda z nich będzie miała inną masę, to porównujemy najpierw dwie monety a i b. Jeśli mają tę samą masę, jesteśmy od razu w domu, jeśli masy różne, to porównujemy następne dwie. Otrzymujemy schemat ważeń:
++ – cięższe a i c
+- – cięższe a i d
-+ – cięższe b i c
— – cięższe b i d
+= albo -= – cięższe a i b
= i cokolwiek – cięższe c i d.
Gdyby cięższe miały mieć tę samą masę, to jeśli w pierwszym ważeniu jest równowaga, porównujemy w drugim którąkolwiek monetę a, b z którąś z pary c, d.
++ – cięższe a i c
+- – cięższe a i d
-+ – cięższe b i c
— – cięższe b i d
=+ – cięższe a i b
=- – cięższe c i d
Wynika stąd, że jest znaczące, w którą stronę mamy wychylenie szalki, bo to pozwala nam odróżnić np. monetę a od b. Tak samo dla sześciu monet. Redukcja 27 możliwości do 14 jest związana z symetrią, i faktycznie przypadek gdy jedna moneta jest cięższa a druga lżejsza jest bardziej „symetryczny”, ale nie wiem, czy tu jest takie proste przełożenie.
No i jednak nie da się odnaleźć dwóch monet, lżejszej i cięższej, spośród ośmiu w czterech ważeniach, mimo że jest tylko 28 możliwych par i aż 41 „zredukowanych” sekwencji wyników.
@aps1968:
„No i jednak nie da się odnaleźć dwóch monet, lżejszej i cięższej, spośród ośmiu w czterech ważeniach, mimo że jest tylko 28 możliwych par i aż 41 “zredukowanych” sekwencji wyników.”
ponieważ… ?
„jednak nie da się” oznacza, że nie znalazłeś sposobu, czy jest jakis dowód.
Wybrópowałeś wszystkie sposoby ważeń, strategie?
Trudno przyjąć na wiarę ten wniosek…
@Wiąz
Nie znalazłem sposobu, bo wszystkie próby ważeń sprowadzały mi się do tego, że jeśli dla 6 monet udałoby się w 3 ważeniach, to dla 8 w 4. A jak wiemy, założenie nie jest prawdziwe. Przypomnę, że chodzi o oryginalne zadanie, w którym wszystko jest tak samo, tylko monet jest 8, a nie 6. Wydaje mi się, że obowiązek udowodnienia, iż jednak się da, spoczywałby na kimś, kto się ze mną nie zgodzi.
Ale to nie obala Twojego rozumowania, bo nierówność o której rozmawiamy być może jest warunkiem koniecznym, a nie wystarczającym. Bardziej interesowałby mnie pogląd, dlaczego w przedstawionym przeze mnie przykładzie dwóch monet cięższych spośród czterech, jednak się w dwóch ważenach _da_ 🙂