среда, 3 июня 2015 г.

КК42

Устройство КК42 работает так: если закинуть в него четыре монетки, то на первый лоток вывалится вторая по весу монетка (т.е. монета веса b, если a<b<c<d), а во второй лоток вывалятся остальные. С меньшим (или большим) числом монет устройство не работает.
Как с помощью устройства КК42 определить самую легкую из семи монет различного веса? Постарайтесь обойтись как можно меньшим числом закидываний монет.

2 комментария:

  1. Cчитаем что монеты как-то отличаются или могут быть помечены. Берем 4 - 2ю откладываем в сторону и заменяем одной новой. Так 3 раза. После 4х ходов имеем 4 монеты №2 (ABCD) и 3 другие (XYZ) - самая легкая и 2 самые тяжелые из всей 7ки.

    Берем 2 из 4х (AB) и 2 из 3х (XY) - выпадает гарантированно 1 из 4х (доп A). Меняем одну из 3х на другую, вешаем ABXZ. Если выпадает A - самая легкая X. Если выпала B, тогда упс... надо еще взвесить ABYZ ;)

    A -> Y, B -> Z.

    Taк что 7 в худшем случае, пардон!

    ОтветитьУдалить
  2. Вместо 7-8 будет 6-7, заодно и по логике проще (намного проще).

    1-4) выбираем средние, оставшиеся называем kmn
    5) убираем любую среднюю, добавляем k, получаем одну из средних, назовём её b1
    6) убираем k, добавляем m, если выпадет b1, то a=n, если нет, то отмечаем выпавшую как b2
    7) убираем m, добавляем n, если выпадет b1 то a=m, если b2 то a=k

    Не вижу как можно найти самую лёгкую монету без того, чтобы метить монеты. Очень любопытно любой способ решения без пометки.

    ОтветитьУдалить