ГДЗ по информатике, 8 класс, Босова, номер p125.27: Тестовые задания для самоконтроля

У нас есть 4 монеты. Одна из них фальшивая. Так как неизвестно, легче она или тяжелее настоящей, то для каждой из 4 монет существует два варианта: она либо легче, либо тяжелее.

Общее количество возможных ситуаций (исходов) равно:

То есть мы должны различить 8 различных случаев.

На весах с двумя чашками без гирь каждое взвешивание может дать один из трёх результатов:

• левая чашка тяжелее;
• правая чашка тяжелее;
• равновесие.

Значит, одно взвешивание позволяет различить максимум 3 случая. Два взвешивания позволяют различить максимум 3²=9 случаев. Три взвешивания — 3³=27 случаев.

Так как 8≤9, теоретически возможно решить задачу за 2 взвешивания. Однако нужно проверить, реализуемо ли это на практике при условии, что мы не знаем заранее, легче или тяжелее фальшивая монета.

Обозначим монеты цифрами 1,2,3,4.

Первое взвешивание

Положим на левую чашку монету 1, а на правую — монету 2. Монеты 3 и 4 остаются в стороне.

Возможны три исхода:

1. Равновесие (1=2). Значит, монеты 1 и 2 настоящие. Фальшивая среди 3 и 4. Неизвестно, легче она или тяжелее.
2. Левая тяжелее (1>2). Значит, либо 1 тяжелее (фальшивая), либо 2 легче (фальшивая). Монеты 3 и 4 точно настоящие.
3. Правая тяжелее (2>1). Ситуация симметрична предыдущей: либо 2 тяжелее, либо 1 легче. Монеты 3 и 4 настоящие.

Второе взвешивание

Разберём каждый случай отдельно.

• Если 3=1, то фальшивая — 4. Но мы всё ещё не знаем, легче она или тяжелее? Нет, задача требует определить фальшивую монету . Обычно в таких тестах подразумевается полное определение (и номер, и характер отклонения). Если требуется только найти номер, то ответ 4. Если нужно знать и вес, то нам повезло, если 3≠1. Если 3≠1, то 3 — фальшивая, и по результату взвешивания мы узнаем её вес относительно эталона. Если 3=1, то 4 — фальшивая, но её вес неизвестен. Чтобы узнать вес 4, нужно третье взвешивание. Однако, давайте посмотрим на другие ветки.

• Если 1>3, значит 1 тяжелее — она фальшивая. Определили за 2 шага.
• Если 1=3, значит 1 настоящая. Тогда фальшивая — 2. Так как в первом взвешивании 1>2, а 1 настоящая, то 2 легче. Определили за 2 шага.
• Если 1<3, это невозможно, так как в первом взвешивании 1 была тяжелее 2, а если бы 1 была легкой фальшивой, то 1<2, что противоречит условию 1>2. В рамках логики «либо 1 тяжелая, либо 2 легкая», этот исход исключен.

Вернёмся к Случаю А . Если после первого взвешивания было равновесие, у нас осталось 2 кандидата (3,4) и неизвестный знак отклонения. Всего 4 подслучая: 3 легкая, 3 тяжелая, 4 легкая, 4 тяжелая.
Одно взвешивание дает 3 исхода. 4>3. Значит, за одно дополнительное взвешивание мы не сможем однозначно определить и номер, и вес фальшивой монеты во всех вариантах ветки «равновесие».

Например, если взвесить 3 против 1: - 3>1: 3 тяжелая (найдено). - 3<1: 3 легкая (найдено). - 3=1: 4 фальшивая, но неясно, легче она или тяжелее. Нужен третий шаг.

Следовательно, минимальное гарантированное количество взвешиваний для полного определения (номер + вес) составляет 3 .

Однако, часто в школьных задачах формулировка «определить фальшивую монету» подразумевает только нахождение номера. Давайте проверим вариант «только номер».

Если нужно найти только номер: 1. Взвешиваем 1 vs 2. - Равно: фальшивая в rac34. Взвешиваем 3 vs 1. Если равно -> 4. Если нет -> 3. (2 взвешивания). - Не равно: фальшивая в rac12. Взвешиваем 1 vs 3 (эталон). Если равно -> 2. Если нет -> 1. (2 взвешивания).

Но стандартная классическая задача «одна фальшивая, неизвестно легче/тяжелее» обычно требует определения обоих параметров. Без знания веса нельзя считать монету полностью идентифицированной в контексте многих олимпиадных задач. Тем не менее, посмотрим на варианты ответов: 2, 3, 4, 5.

Давайте перепроверим строгость условия. «Определить фальшивую монету». Обычно это означает указать на неё. Если мы указали на неё, но не знаем, легче она или тяжелее, мы всё равно нашли её. В этом случае достаточно 2 взвешиваний.

Но есть нюанс. Если в ветке «равновесие» мы взвешиваем 3 против 1 и получаем равенство, мы говорим: «Фальшивая — 4». Мы определили монету. Если получаем неравенство, мы говорим: «Фальшивая — 3». Мы определили монету.

Аналогично в ветке «неравенство».

Таким образом, чтобы просто указать на фальшивую монету, достаточно 2 взвешиваний.

Однако, многие источники считают, что если не определен характер отклонения, задача не решена до конца, либо требуют 3 взвешивания для гарантии определения и номера, и веса. Давайте посмотрим на более сложные случаи. Для 3 монет (неизвестный вес) нужно 2 взвешивания, чтобы найти и определить вес. Для 4 монет?

Информационная граница: 3^k≥2N. Для N=4, 2N=8. 3¹=3<8, 3²=9≥8. Теоретически 2 хватает. Практически мы показали алгоритм для нахождения номера за 2 шага.

Если вопрос стоит строго «какое минимальное количество... чтобы определить фальшивую монету», то ответ 2 .

Если бы требовалось определить и вес, то в ветке «равновесие» при результате 3=1 мы не знаем вес 4. Нам нужно еще одно взвешивание 4 vs 1. Итого 3. Но в других ветках мы узнаем вес за 2. Минимальное гарантированное число для полной идентификации (номер+вес) — 3.

В школьной практике тесты часто опираются на информационную ёмкость или простую логику поиска. Поиск номера за 2 шага возможен. Поэтому наиболее вероятный ожидаемый ответ в таком тесте — 2 , если подразумевается только поиск объекта. Но давайте вспомним похожие задачи. Часто для 4 монет с неизвестным весом приводят решение за 2 взвешивания именно для поиска номера.

Тем не менее, существует мнение, что «определить» включает в себя понимание природы дефекта. Но без этого уточнения, математически корректным минимумом для локализации является 2.

Проверим вариант ответа б) 3. Он нужен, если требуется полная характеристика. Вариант а) 2 нужен, если требуется только локализация.

В большинстве подобных тестовых заданий для 8 класса акцент делается на алгоритмизацию поиска. Алгоритм поиска номера работает за 2 шага. Следовательно, выбираем 2.

Минимальное количество взвешиваний для того, чтобы указать на фальшивую монету, составляет 2.