Парад решений2
раскрыть ветку (1)
Да, если по нормальному решать, даже если мы не знаем, фальшивка легче или нет.
Делим на 3 кучки по 4, взвешивам 2 кучкиА так по условию нужно найти, минимальное количество взвешиваний = 2 (а не универсальный алгоритм для худшего случая ):
1. Допустим они равны, знчит фальшивая в оставшейся кучке, рассмотрим ее, взвесим 2 монеты
1.1 Допустим они равны, значит фальшивая среди 2 оставшихся, а одна из уже взвешанных настоящая.
Взвесим 1 из оставшихся и 1 настоящую
1.1.1 они равны, значит 1 осиавшаяся - фальшивая. Конец
1.1.2 они не равны, значит мы взяли фальшивую на шаге 1.1. Конец
1.2 Они различны, значит из 2 взвешанных 1 фальшивая, а остальные настоящие. Возьмем 1 настоящую и 1, взвешанную на шаге 1
1.2.1 Они равны, значит вторая, взвешанная на шаге 1 фальшивая. Конец
1.2.2 Они различны, значит на шаге 1.2 взяли фальшивую. Конец
2. Горстки по 4 оказались различны. Тогда обозначим их так Л1Л2Л3Л4 < Т1Т2Т3Т4. Кроме того есть горстка из настоящих НННН. Взвесим Л1Л2Т1 и Л3Л4Т2.
2.1 Допустим они равны, значит фальшивка либо Т3, либо Т4, в таком случае мы точно знаем, что фальшивка тяжелее настоящей монеты (исходя из самого первого взвешивания). Просто сравним их.
2.1.1 Т3 < Т4, значит фальшивка Т4. Конец.
2.1.2 Т3 > Т4, значит фальшивка Т3. Конец.
2.2 Допустим Л1Л2Т1 < Л3Л4Т2. Тогда либо фальшивка тяжелее и ею является Т2, либо легче и ею может являтся Л1 или Л2. Взвесим Л1 и Л2.
2.2.1 Л1 = Л2, значит фальшивка Т2. Конец
2.2.2 Л1 < Л2, значит фальшивка среди легких, значит она легче, значит это Л1. Конец
2.2.3 Л1 > Л2, значит это Л2 (аналогично 2.2.2). Конец.
2.3 Допустим Л1Л2Т1 > Л3Л4Т2, тогда фальшивка может быть тяжелее - Т1, либо легче - Л3/Л4. Аналогично 2.2 (ситуации симметричны) мы можем выяснить фальшивку следующим взвешиванием. Конец
Итого за 3 взвешивания БЕЗ ДОДУМЫВАНИЯ ИНФЫ, КОТОРОЙ НЕ ДАНО ПО УСЛОВИЮ, мы нашли фальшивку
- Взвешиваем две монеты случайно
* Нам везёт и они разные
- Одну монету оставляем, берем оставшиеся из 10, взвешиваем
* Если в равновесии, то оставленная монета в стороне - фальшивка
* Если в неравновесии, то фальшивка - та монета, которую мы взвесили 2 раза.
показать ответы
1. по условию как раз надо найти минимальное количество взвешиваний, работающее для любых условий.
2. Если точно знать, что монета легче (тяжелее) то таких взвешиваний 3 (но не по описанной вами системе). Если неизвестно, легче или тяжелее, то 4.
2. Если точно знать, что монета легче (тяжелее) то таких взвешиваний 3 (но не по описанной вами системе). Если неизвестно, легче или тяжелее, то 4.
раскрыть ветку (1)
"Условие" можно по разному трактовать. Тут как с итальянской забастовкой. Все понимают, что в условиях невозможно прописать всё, и делают не как написано, а так как подразумевалось, но алгоритм на 2 решения -- хоть и полушуточный, но всё же формально не нарушает условие).
Во-вторых, то, что по вашей, более очевидной схеме требуется 4 взвешивания, никак не говорит, что моя схема - неверна, это просто говорит, что у вас просто менее оптимальное решение, хотя тоже верный.
показать ответы
Если при первом взвешивании весы не уравновесились, то как вы определите, в какой чашке фальшивка?
раскрыть ветку (1)
Скриншоты комментов
62.6K постов41.4K подписчика
Правила сообщества
В сообществе можно размещать ЛЮБЫЕ скрины (комментов) с любого сайта!!
ПРИКРЕПИТЬ ССЫЛКУ НА КОМЕНТ ЕСЛИ ОН С Пикабу желательно, но не обязательно!!!
Если скрин не с пикабу, а со стороннего сайта( Твиттер,. Вк, Одноклассники и т.д.) то ссылка не обязательна.
Для сообщества подходит любой скрин, набранный на клавиатуре, даже если это не диалог (под вид Твита) Так же подходит скрин с картинкой и хотя бы одним комментарием под ним, с любого источника.