Комментарии
Задача: среди 13 шариков один отличен от других по весу, надо выявить его за 3 взвешивания на весах с чашками.
Решение: решения у задачи нет, это сделать невозможно (в инете "решений" полно, а еще больше коментов к ним, которые их опровергают).
Доказательство (что нет решения): пусть у нас количество подозрительных шаров обозначено через Х (в начале Х=13, надо сделать Х=1). и пусть мы пока не знаем, тежелее искомый или легче (в начале мы не знаем). тогда взвешивание уменьшает количество подозрительных шаров не более чем в два раза (если рассматривать сразу все варианты где может быть искомый). значит после первого взвешивания Х будет не менее 7 и к тому же мы по прежнему не знаем, тяжелее или легче искомый. поэтому согласно тому же принципу получаем, что после второго взвешивания Х будет не менее 4. таким образом, надо из 4 (или более) шаров за одно оставшееся взвешивание выбрать искомый. к тому времени мы уже будем знать, легче он или тяжелее, но это нам не поможет, так как из 4 шаров за одно взвешивание выбрать в любом случае ничего нельзя, это очевидно.
Итого: максимум что можно сделать за три взвешивания это определить ПАРУ шаров, из который ровно один – искомый и попутно определить тяжелее он или легче. то есть, подготовить все к тому, чтобы решить задачу за 4 взвешивания :)
Примечание: доказать что взвешивание уменьшает количество подозрительных шаров не более чем в два раза при отсутствии информации про разность масс можно как "на пальцах", так и элементарными неравенствами с одним неизвестным. если информация есть, то количество подозрительных можно уже уменьшить до 1/3 (то есть, уменьшая 4 в три раза, мы получаем число большее 1, а значит 2 как минимум шарика, а взвешиваний-то уже тю-тю, ебок :).
Общий результат таков: если сравнить задачи со взвешиванием когда знак разности масс известен и когда нет, то в решении вторых будет на 1 взвешивание больше требоваться, независимо от количества шаров.
← Вернуться к журналу «байкeр из склепа»
- —