logowanie

matematyka » forum » forum zadaniowe - zadania różne » zadanie

Konkursy, zadanie nr 271

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

andu
postów: 2
2017-07-20 19:38:22

Mamy pięć złotych samorodków nieznacznie różniących się wagą. Ile potrzeba ważeń, na wadze szalkowej bez odważników, by je uporządkować od najcięższej do najlżejszej?
(Ten sam algorytm można zastosować do uporządkowania 5 drużyn lub zawodników w turnieju np tenisowym przy pomocy najmniejszej ilości rozegranych meczów.)


rockstein
postów: 33
2017-11-16 19:29:31

Problem sprowadza się do tego, po ilu ważeniach, czyli bezpośrednich porównaniach mas dwóch obiektów, będzie można uporządkować pięć różnych obiektów pod względem zmniejszających się mas. Jak wiadomo 5 obiektów można uszeregować na 5! sposobów, czyli może być 120 różnych uporządkowań. Z kolei każde ważenie daje jeden z dwóch możliwych wyników, zatem w ważeń może dać 2^w wyników. Stąd wniosek, że najmniejsza ilość ważeń w musi spełniać nierówność:
2^(w-1)<n!<2^w.
Skoro w naszym przypadku n!=120, to 64<120<128, czyli 2^6<120<2^7. Zatem odpowiedź na postawione pytanie brzmi: Aby uporządkować 5 samorodków, z których każde dwa różnią się masą, w kierunku od najcięższego do najlżejszego (lub odwrotnie), potrzeba co najmniej 7 ważeń.
Sądzę jednak, że ta odpowiedź dokładnie odpowiadająca na postawione pytanie, nie w pełni usatysfakcjonuje pytającego, bowiem w dopisku jest mowa o algorytmie postępowania. Otóż są możliwe dwa sposoby postępowania:
Sposób 1.
Porównanie mas i uporządkowanie trzech dowolnie wybranych samorodków (w większości przypadków 3 ważenia), porównanie masy czwartego samorodka ze średnim z pierwszej trójki, a następnie ze skrajnym (2 ważenia), wreszcie porównanie masy piątego samorodka z masą jednego ze środkowych i w niekorzystnym przypadku z masami dwóch przeciwległych (3 ważenia). Jak widać, w większości przypadków będzie potrzeba ośmiu ważeń, mimo że postępowanie jest w pełni racjonalne.
Sposób 2.
Porównujemy masy samorodków S1 i S2 oraz S3 i S4 (2 ważenia), porównujemy samorodki cięższe z obu par, np S2 i S4 (1 ważenie), porównujemy samorodek S5 z lżejszym z poprzedniego ważenia (1 ważenie). Uzyskujemy w ten sposób szkielet nierówności, który daje się ostatecznie uporządkować w 3 następnych ważeniach. Tym sposobem postępowania uzyskujemy wynik w wyliczonej uprzednio, minimalnej ilości 7 ważeń.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj