Придумай что то интересное

Задача (логика, 5–7 класс): 8 монет и фальшивка

Есть 8 одинаковых на вид монет. Одна из них фальшивая и тяжелее настоящей. Есть чашечные весы без гирь. Нужно найти фальшивую монету ровно за 2 взвешивания.

Подсказка (ключевой принцип): не дели монеты на две кучки — дели на три. Сравнивая две равные кучки, ты получаешь три возможных исхода: левая тяжелее, правая тяжелее, равновесие. Каждый исход — это «ветка», и в ней должно остаться не больше монет, чем можно проверить за оставшиеся взвешивания.

Пришли свой вариант решения — проверю по шагам и покажу, где ветка «не влезает».

Если осилишь эту — вот версия посложнее: 12 монет, фальшивая может быть легче или тяжелее, но неизвестно, в какую сторону. За 3 взвешивания.

Проверил твою схему — она не проходит, и вот ровно где ломается.

Твоя разбивка: A = {1,2}, B = {3,4}, C = {5,6,7} и монета 8 в стороне.

Взвешивание 1: {1,2} против {3,4}.

Сценарий «равновесие»: значит, 1, 2, 3, 4 — настоящие. Фальшивка среди {5, 6, 7, 8} — это 4 монеты, а осталось одно взвешивание. Одно взвешивание даёт максимум 3 исхода (левая тяжелее / правая тяжелее / равновесие), а различить надо 4 варианта. Не хватает.

Сценарий «левая тяжелее»: фальшивка — либо тяжёлая из {1,2}, либо лёгкая из {3,4}. Снова 4 кандидата на одно взвешивание. Тоже тупик. С «правой тяжелее» — симметрично.

То есть схема 2+2+3+1 проваливается в каждой ветке, а не в одной.

Почему так: первое взвешивание должно оставлять не больше 3 кандидатов, ведь 3 — предел одного взвешивания. А 8 монет за 2 взвешивания возможны, потому что $3^2 = 9 \ge 8$.

Рабочее решение: 3 + 3 + 2 (две монеты в стороне).

Взвешивание 1: 1, 2, 3 против 4, 5, 6.

Сценарий 1 — равновесие. Фальшивка — 7 или 8. Взвешивание 2: 7 против 8 → тяжелее та, что фальшивая.

Сценарий 2 — левая чаша тяжелее. Фальшивка среди 1, 2, 3 (и она тяжёлая). Взвешивание 2: 1 против 2.

• 1 тяжелее → фальшивая 1;
• 2 тяжелее → фальшивая 2;
• равновесие → фальшивая 3.

Сценарий 3 — правая чаша тяжелее. Симметрично: фальшивка среди 4, 5, 6. Взвешивание 2: 4 против 5. Тяжелее → она; равновесие → 6.

Проверка: в каждой ветке после первого взвешивания остаётся не больше 3 кандидатов — а значит, второе взвешивание всегда закрывает вопрос. Ровно 2 взвешивания, как требовалось.

Вывод-принцип: делить надо не «пополам», а так, чтобы каждая ветка после взвешивания оставляла ≤ 3 вариантов. Кучки 3+3+2 это обеспечивают, 2+2+3+1 — нет.

Хочешь, разберём версию с 12 монетами, где неизвестно, легче фальшивка или тяжелее? Там первое взвешивание устроено хитрее — 4 против 4.

Справедливое замечание — в прошлом ответе у меня была конкретная ошибка в разборе, признаю.

Где я ошибся: в схеме 2+2+3+1 при взвешивании {1,2} vs {3,4} и перевесе левой чаши кандидатов не 4, а 2 — фальшивка тяжёлая, значит она лежит на перевесившей чаше, то есть это 1 или 2. Второе взвешивание 1 vs 2 их различает. Эту ветку я разобрал неверно.

Но вывод про схему не меняется — она ломается в другой ветке, в равновесии: {1,2} = {3,4} ⇒ монеты 1–4 настоящие, фальшивка среди 5, 6, 7, 8 — это 4 монеты. Осталось одно взвешивание, а оно даёт максимум 3 исхода (левая тяжелее / правая тяжелее / равно). Четыре варианта им не закрыть: например, 5 vs 6 при равновесии оставляет пару 7–8 неразличённой. Вот здесь гарантии нет.

Про «схему, которую сама придумала»: 3+3+2 — это моя схема из предыдущего ответа, и она цела:

• равно → фальшивка среди двух оставшихся, 7 vs 8;
• перевес → фальшивка тяжёлая среди трёх на перевесившей чаше, 1 vs 1 закрывает (равно → третья).

А 2+2+3+1 — твоя схема, и она не проходит именно из-за ветки равновесия, а не из-за перевеса. Так что «сломала» — не то слово: я неверно объяснил, почему она не годится, но сама она не годилась и до этого.

Если хочешь, покажи, как ты закрываешь в ней ветку равновесия, — разберу по шагам.

Ошибку в разборе я признал — тут спорить не буду. Но в логике всё сходится: схема 2+2+3+1 не закрывает ветку равновесия, 3+3+2 закрывает. Если хочешь, доведём задачу до конца.

Здесь основная тема — учёба; пообщаться можно в комьюнити Новой Школы: Telegram и ВКонтакте

Комьюнити — это просто вариант, если захочется поболтать; настаивать не буду. Мне интереснее задача: разберём ветку с 4 монетами или возьмёмся за 12 монет?

Коротко: алгоритм верный. Проверил все 9 ветвей (3 исхода первого взвешивания × по 3 исхода второго) — каждая закрывается третьим взвешиванием, и ни в одной не остаётся двух неразличимых монет.

Проверка по ветвям

Исход 1 — равновесие. 1–8 настоящие, фальшивка среди 9,10,11,12.

• (9,10,11) vs (1,2,3) равно → фальшивка 12; третьим взвешиванием 12 vs 1 узнаём «легче/тяжелее». ✔ (для поиска монеты третье взвешивание даже не нужно)
• (9,10,11) тяжелее → фальшивка тяжёлая среди 9,10,11; 9 vs 10 различает все три. ✔
• легче → симметрично. ✔

Исход 2 — левая (1,2,3,4) тяжелее. Кандидаты перед вторым взвешиванием: тяжёлые 1,2,3,4 и лёгкие 5,6,7,8. Второе: (1,2,5) vs (3,4,6), монеты 7,8 в стороне.

• равно → 1,2,5,3,4,6 настоящие, остаются лёгкие 7 и 8; 7 vs 8 → легче фальшивка. ✔ (2 исхода)
• снова тяжелее → тяжёлая 1 или 2, либо лёгкая 6; 1 vs 2 → при равенстве фальшивка 6. ✔ (3 исхода)
• стало легче → тяжёлая 3 или 4, либо лёгкая 5; 3 vs 4 → при равенстве фальшивка 5. ✔ (3 исхода)

Итого 8 состояний и 8 исходов третьего взвешивания — ни одного «холостого» листа.

Исход 3 — левая легче. Зеркально: равно → тяжёлые 7,8; снова легче → лёгкие 1,2 или тяжёлая 6; стало тяжелее → лёгкие 3,4 или тяжёлая 5. ✔

Сходится по счёту: всего возможно $12 \times 2 = 24$ варианта, три взвешивания дают максимум $3^3 = 27$ исходов. Все 24 варианта уложены ровно в 24 листа — это признак оптимального дерева, а не просто рабочего.

Две придирки по формулировкам, не по сути:

1. В исходе 2 фраза «перевес не изменился — значит, фальшивка там, где была» неточна: проверять надо не «где была», а какие монеты могли дать именно такой перевес. Список кандидатов (тяжёлая 1 или 2, лёгкая 6) в тексте правильный, а объяснение — «по ощущению».
2. В исходе 1 взвешивание 12 vs 1 отвечает не на вопрос «какая монета фальшивая» (это уже ясно), а на вопрос «легче или тяжелее». Если в задаче требуется только найти монету — шаг лишний, на лимит он не влияет.

Симулятор на Python тут действительно уместен: перебрать все 24 варианта и прогнать каждый через дерево — это лучшая проверка, чем доверие к тексту. Написать?

Про подписку, сбои и неудобный интерфейс — это к официальной поддержке: Telegram и ВКонтакте. По оплате лучше писать вместе со взрослым, который платил. А по монетам итог сошёлся: алгоритм на 12 монет я проверил, он рабочий.

Не отмазка — просто по этой теме у меня нет доступа к тому, что происходит в приложении, поэтому и говорить нечего. По делу: алгоритм на 12 монет сошёлся, могу написать симулятор на Python, который переберёт все 24 варианта и проверит дерево. Или давай новую задачу.

Жаль, но решать тебе — уговаривать не буду. Если захочешь вернуться к задаче про 12 монет или разобрать что-то новое, приходи.