Автор: Павел Хаустов 
Добрый день!
Скажите пожалуйста, как на тест №11 в задаче №10 (n = 6, k = 2) получить ответ 20 / 15? У нас получается только 18 / 15, если взвешивать две половины монет.
Я поясню нашу стратегию в таком случае. Просто разделяем на две равные части все монеты и надеемся, что вес будет разный. Если разный, то берём ту половину, что тяжелее. Иначе -- нам не повезло :( Рассмотрим все возможные распределения по чашам весов (0 -- нормальная монета, 1 -- фальшивая):
Код:
000 011 (+)
000 101 (+)
000 110 (+)
001 001
001 010
001 100
010 001
010 010
010 100
011 000 (+)
100 001
100 010
100 100
101 000 (+)
110 000 (+)
Получается, что 6 комбинаций из 15 дают нам три настоящие монеты. Наше математическое ожидание равно (3 * 6) / 15 = 18 / 15.
Кроме того, в тесте 16 (n = 21, k = 4) можно узнать стратегию, которая позволяет получить математическое ожидание 45 / 133 (около 0.33834586466)? Наше решение выдаёт 34 / 105 (около 0.32380952381), здесь кроме взвешивания случайной пары монет, мы ничего не смогли придумать.