Algorytmy nie są im obce (aktualizacja)

Konkurs, który organizowany był przez Zespół Szkół Technicznych z Ustronia, podzielony był na dwie części - pisemną oraz praktyczną. Co ciekawe, w pierwszej z nich jedno z zadań było niezwykle wymagające. Jak powiedział nam nauczyciel Piotr Kaczmarzyk (który przygotowywał arkusze), jego rozwiązaniem zajmowali się chętni do podjęcia pracy w siedzibie amerykańskiego giganta Google. Jak brzmi jego treść?

Masz 9 kul, które wyglądają identycznie. Jedna z nich odbiega wagą od pozostałych, których waga jest identyczna. Nie wiemy niestety, czy kula "odmieniec" jest cięższa czy lżejsza. Opisz precyzyjny sposób pozwalający w każdym możliwym przypadku wskazać kulę o innej wadze przy pomocy wagi szalkowej i trzech ważeń. 

Swoją wiedzę informatyczną sprawdzali uczniowie ósmych klas szkół podstawowych oraz trzecich klas gimnazjum, którzy osiągnęli najlepsze rezultaty w eliminacjach przeprowadzanych w poniższych placówkach:

• Zespole Szkolno-Przedszkolnym nr 2 w Wiśle
• Szkole Podstawowej nr 3 w Ustroniu
• Szkole Podstawowej nr 1 w Jaworzynce
• Szkole Podstawowej nr 1 w Wiśle
• Szkole Podstawowej nr 2 w Ustroniu
• Gimnazjum nr 1 w Ustroniu
• Szkole Podstawowej nr 1 w Ustroniu
• Zespole Szkolno-Przedszkolnym w Istebnej
• Szkole Podstawowej nr 1 w Koniakowie
• Szkole Podstawowej nr 2 w Koniakowie-Rastoce

- Nasza szkoła jest od wielu lat jedną z głównych kształcących w zakresie informatyki. Powinniśmy popularyzować wiedzę na temat tego kierunku kształcenia. Dlatego też zorganizowaliśmy analogiczny konkurs dotyczący matematyki. Kształcimy nie tylko informatyków, ale także mechaników i to są wiodące kierunki. W tym roku otwieramy także trzeci kierunek - programistyczny. Jaki będzie nabór - zobaczymy, chociaż póki co nie narzekamy - powiedziała nam Katarzyna Kałuża, dyrektor Zespołu Szkół Technicznych w Ustroniu. Warto dodać, że placówka współpracuje od niedawna z Akademią Techniczno-Humanistyczną z Bielska-Białej, która w konkursie ufundowała jedną z nagród za najlepsze rozwiązanie zadań dotyczących algorytmów.

Gratulacje uczniom i organizatorom konkursu złożył Stanisław Malina (członek Zarządu Powiatu Cieszyńskiego) oraz Przemysław Korcz (burmistrz Ustronia).

Pierwsze miejsce zajął Krzysztof Krysiński ze Szkoły Podstawowej nr 8 w Skoczowie, drugie miejsce przypadło Dawidowi Pilchowi ze Szkoły Podstawowej nr 2 w Wiśle, a trzecie - Mateuszowi Gumoli również ze Szkoły Podstawowej nr 2 w Wiśle. Ponadto, najlepszy wynik punktowy w zadaniach związanych z algorytmami, uzyskał Krzysztof Krysiński z SP8 w Skoczowie.

Aktualizacja

Rozwiązanie zagadki 9. kul znajdziecie za zdjęciami.

Aby uzyskać rozwiązanie zadania, należy przeprowadzić następujące rozumowanie:

Ważenie pierwsze:
Ważymy po 3 kule na każdej z szalek wagi.  Wynik ważenia może być dwojaki: szalki wagi są na tym samym poziomie (wariant A), jedna z szalek wagi jest wyżej lub niżej niż druga (wariant B)

Wariant A wyniku ważenia pierwszego.
Jeżeli szalki wagi są na tym samym poziomie, kulka o innej wadze tzw. „podejrzana kulka” znajduje się w trójce kul, które nie były zważone. Dalej będziemy nazywać ją „podejrzaną trójką".
Dalsza procedura ważenia w tym przypadku jest następująca:
Ważymy 2 kule z ważonej wcześniej szóstki kul i 2 kule z „podejrzanej trójki”.(Ważenie drugie)
a)Jeżeli podczas ważenia drugiego szalki wagi znajdują się na tym samym poziomie, to wiemy już, że pozostała  kula z „podejrzanej trójki” (ta, która nie była na wadze) jest inna.
b)Jeżeli podczas ważenia drugiego szalki  wagi nie znajdują się na tym samym poziomie, to na podstawie obserwacji, czy szalka z 3 kulami z szóstki jest wyżej czy niżej, niż szalka z kulami z „podejrzanej trójki” pozyskujemy informację o tym,  czy „podejrzana kulka” jest cięższa czy lżejsza.
By ustalić, która z kul z „podejrzanej trójki” jest odmienna, pozostaje nam zważyć 2 kule z „podejrzanej trójki” z poprzedniego ważenia. (Ważenie trzecie)
a)Jeżeli szalki wagi znajdą się na tym samym poziomie, „podejrzaną kulą jest ta, która nie znalazła się na wadze.
b)Jeżeli szalki wagi nie znajdują się na tym samym poziomie, musimy ustalić, która z kul jest tą „podejrzaną”. Wykorzystujemy do tego informację uzyskaną podczas ważenia drugiego. Jeżeli ustaliliśmy wtedy, że podejrzana kula jest cięższa niż pozostałe, znajdować się ona będzie na szalce na to wskazującej. Analogicznie rozumujemy w przypadku odwrotnym.
Wariant B wyniku ważenia pierwszego.
Jeżeli podczas ważenia pierwszego szalki wagi nie  znajdują się na tym samym poziomie, to wiemy że pozostała trójka, która nie była ważona, nie zawiera „ podejrzanej kuli”, a my mamy do czynienia z „podejrzaną szóstką”.
Następnie układamy na szalkach wagi trzy kule wcześniej nie ważone i trzy kule z „podejrzanej szóstki”. (Ważenie drugie)
a)Jeżeli szalki wagi podczas ważenia drugiego znajdują się na tym samym poziomie, to wiemy, że „podejrzana kula” znajduje się w trójce kul nieważonych.
Na podstawie obserwacji pierwszego ważenia, gdzie braliśmy 3 kule z „podejrzanej szóstki” ustalamy czy podejrzana kula jest cięższa czy lżejsza ( Jeżeli wzięliśmy 3 kule z „podejrzanej szóstki” z szalki położonej wyżej, „podejrzana kula” jest lżejsza niż pozostałe. Jeżeli wzięliśmy 3 kule z „podejrzanej szóstki” z szalki położonej niżej, „podejrzana kula” jest cięższa niż pozostałe.)       


Skoro ustaliliśmy podczas ważenia drugiego, że „podejrzana kula” znajduję się w trójce kul nieważonych  z „podejrzanej szóstki”, to ważymy 2 kule z tej trójki kul nieważonych (Ważenie trzecie)
Jeżeli szaliki wagi podczas ważenia trzeciego znajdują się na tym samym poziomie, to wiemy, że „podejrzaną kulą” jest kula nie ważona w ważeniu trzecim.
Jeżeli szaliki wagi podczas ważenia trzeciego nie znajdują się na tym samym poziomie, to wiedza o tym, czy „podejrzana kula” jest cięższa, czy lżejsza pozwala wskazać „podejrzaną kulę”. Jeżeli jest cięższa, będzie znajdować się na szalce położonej niżej. Jeżeli jest lżejsza, będzie znajdować się na szalce wagi położonej wyżej.

b) Jeżeli szalki wagi w ważeniu drugim nie  znajdują się na tym samym poziomie, , to na podstawie obserwacji, czy szalka z 3 kulami z „podejrzanej szóstki” jest wyżej lub niżej, pozyskujemy informację o tym,  czy „podejrzana kulka” jest cięższa czy lżejsza. Wiemy już również, że w tych 3 kulach z „podejrzanej szóstki” znajduje się „podejrzana kula”. (w końcu ważyliśmy w ważeniu drugim 3 kule zwykłe z 3 „kulami podejrzanymi”, tymi z „podejrzanej szóstki”)
Następnie kładziemy na szaklach wagi 2 kule z trójki „kul podejrzanych”. (Ważenie trzecie)
Jeżeli szalki wagi są na tym samym poziomie, to wiemy, że „podejrzana kula” jest tą trzecią, której nie położyliśmy na wadze podczas ważenia trzeciego.
Jeżeli szalki wagi nie są na tym samym poziomie, to wiemy, że „podejrzana kula” jest tą lżejszą lub cięższą zgodnie z informacją wadze kulki, jaką uzyskaliśmy podczas ważenia drugiego.

Kluczem jest zrozumienie faktu ze ważąc 6 kul (po trzy) uzyskujemy również informację o kulach nieważonych.
Rozwiązanie przedstawiono siląc się na ogólność, jednak bez jej utraty można po drugim ważeniu założyć wynik i dalej już pisać o kuli cięższej lub lżejszej.

KR