Логические задачи, перебор
В этом уроке решаем логические задачи: кто есть кто, кто сказал правду, сколько чисел можно составить из цифр, как найти фальшивую монету. Раньше вы рисовали схему-отрезок — так было и в задачах на движение. Здесь вместо отрезка мы рисуем карту вариантов: таблицу или список, где каждый вариант виден и ни один не потерян.
- Карта вариантов: каждая клетка отвечает «да или нет»
- Одна свободная клетка в строке — это ответ
- Кто ошибся: проверяем каждую догадку
- Рыцари и лжецы: если он правдив, что тогда
- Перебор по порядку: ничего не пропустить и не повторить
- Нашли вариант — проверьте, нет ли других
- Взвешивание: три исхода — три группы
- Часто задаваемые вопросы
Карта вариантов: каждая клетка отвечает «да или нет»
Начнем с задачи, к которой вернемся во втором разделе: Таня, Коля и Вера заняли в забеге первое, второе и третье места. Таня не первая. Коля не первый и не третий. Кто какое место занял, и единственный ли это ответ? Иксератопс отвечает сразу: «Таня не первая — значит, вторая». Проверим по карте.
Решавр начинает с таблицы. Строки — имена: Таня, Коля, Вера. Столбцы — места: 1, 2, 3. Каждая клетка отвечает на один вопрос: «Может ли этот человек занять это место?» Ответ на вопрос «кто какое место занял» — это способ поставить в каждую строку и в каждый столбец ровно один «+».
Теперь читаем условие и отмечаем клетки. «Таня не первая» — в клетке «Таня, 1» ставим «−». «Коля не первый и не третий» — две клетки: «Коля, 1» и «Коля, 3» получают «−». Остальные клетки пока пустые.
Определение
Таблица «кто есть кто» — таблица, в которой строки — объекты (люди), столбцы — варианты (места, занятия, цвета). Знак «+» в клетке значит «подходит», знак «−» — «не подходит».
Правило
Если у каждого ровно один вариант и варианты у всех разные, то в каждой строке и в каждом столбце таблицы стоит ровно один «+».
Условие «не …» дает «−» в одной клетке. Условие «… — это …» дает «+» в клетке и «−» во всех остальных клетках ее строки и ее столбца.
Одна свободная клетка в строке — это ответ
Решим задачу из введения по карте: каждый «+» гасит свой столбец, а следующий ставим там, где свободна ровно одна клетка.
Алгоритм
- Начертите таблицу: строки — объекты, столбцы — варианты.
- Перенесите условие: «−» за каждое «не», «+» за каждое прямое утверждение.
- Найдите строку или столбец, где свободна ровно одна клетка, поставьте в нее «+».
- Поставьте «−» в остальные клетки строки и столбца этого «+», вернитесь к шагу 3.
- Когда в каждой строке один «+», проверьте ответ по всем условиям.
Задача 1
Таня, Коля и Вера заняли в забеге первое, второе и третье места. Таня не первая. Коля не первый и не третий. Кто какое место занял?
Решение. 1) По условию: «Таня, 1» — «−»; «Коля, 1» и «Коля, 3» — «−». У Коли свободна одна клетка: Коля — второй (шаг 1 на схеме).
2) Столбец «2»: у Тани и Веры «−». У Тани свободна одна клетка: Таня — третья (шаг 2).
3) Столбец «3»: у Веры «−». У Веры осталось место 1 (шаг 3).
Проверка: Таня третья — не первая, верно; Коля второй — не первый и не третий, верно; места разные. На каждом шаге свободной была ровно одна клетка, поэтому ответ единственный.
Ответ: Вера — первое место, Коля — второе, Таня — третье.
Ошибка
Иксератопс прочитал «Таня не первая» и сразу решил: «Значит, Таня вторая».
Проверим на карте: ставим «Таня, 2» — «+». Тогда в столбце «2» у Коли «−». Но у Коли уже «−» на местах 1 и 3. Вся строка «Коля» в минусах — Коле не досталось ни одного места. Так быть не может.
Ошибка — в выборе наугад: у Тани были свободны два места, 2 и 3, а Иксератопс взял одно, не проверив. Догадку проверяют, доведя карту до конца: Коле не осталось места, значит, Таня не вторая, а третья.
Задача 2
У Ромы, Светы, Юли и Феди есть по одному питомцу, все разные: кошка, собака, попугай, рыбки. У Ромы не кошка и не собака. У Светы попугай. У Юли не кошка. У кого кошка?
Решение. Таблица 4 на 4. 1) «Света, попугай» — «+», остальные клетки столбца «попугай» — «−».
2) У Ромы «−»: кошка, собака, попугай. Свободны только рыбки — «+». Столбец «рыбки»: у Юли и Феди «−».
3) У Юли «−»: кошка, попугай, рыбки. Остается собака. У Феди осталась одна клетка — кошка.
Проверка: каждое из трех условий выполнено, у всех питомцы разные.
Ответ: кошка у Феди.
Ведите карту сами: в интерактиве на каждом шаге выберите клетку, которую можно заполнить, и сверьтесь с эталоном.
Кто ошибся: проверяем каждую догадку
Бывает, что в условии люди что-то утверждают, и часть утверждений ложна. Тогда строки карты — не люди, а гипотезы: «виноват Кирилл», «виноват Леонид», «виноват Матвей». Для каждой гипотезы проверяем, какие утверждения при ней верны.
Задача 3
Опрокинут цветочный горшок, это сделал один из трех мальчиков. Кирилл: «Это сделал Леонид». Леонид: «Это сделал Матвей». Матвей: «Это сделал не я». Известно, что двое сказали правду, а один солгал.
Решение. Проверим все три гипотезы, не останавливаясь на первой.
1) Виноват Кирилл: Кирилл солгал, Леонид солгал, Матвей сказал правду. Ложных утверждений два — не подходит.
2) Виноват Леонид: Кирилл сказал правду, Леонид солгал, Матвей сказал правду. Ложное утверждение одно — подходит.
3) Виноват Матвей: Кирилл солгал, Леонид сказал правду, Матвей солгал. Ложных два — не подходит.
Ответ: горшок опрокинул Леонид.
Правило
Если неизвестно, кто говорит правду, перебирают гипотезы по одной. Для каждой считают верные и ложные утверждения и сравнивают с условием. Ответ — гипотеза, которая подходит.
Рыцари и лжецы: если он правдив, что тогда
На острове живут рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. Встретились двое, Ян и Зоя, и каждый что-то сказал. Разберем, кто есть кто.
Вариантов всего четыре: каждый из двоих — рыцарь или лжец. Карта — четыре строки, и в каждой проверяем оба высказывания.
Задача 4
Ян сказал: «Зоя — лжец». Зоя сказала: «Мы оба рыцари». Кто есть кто?
Решение.
1) Оба рыцари: Ян сказал «Зоя — лжец», а она рыцарь, — рыцарь солгал. Противоречие.
2) Ян рыцарь, Зоя лжец: слова Яна верны; слова Зои «мы оба рыцари» ложны, как и положено лжецу. Противоречий нет.
3) Ян лжец, Зоя рыцарь: слова Зои «мы оба рыцари» ложны, а она рыцарь. Противоречие.
4) Оба лжецы: слова Яна «Зоя — лжец» верны, а он лжец. Противоречие.
Ответ: Ян — рыцарь, Зоя — лжец.
Правило
Перебирают все варианты «рыцарь/лжец». Верить словам на острове нельзя: «Мы оба рыцари» может сказать и лжец. Вариант подходит, если каждый рыцарь в нем сказал правду, а каждый лжец — неправду.
Перебор по порядку: ничего не пропустить и не повторить
Сколько трехзначных чисел можно составить из цифр 1, 5, 8, если цифры в числе не повторяются? Иксератопс выписывает как придется: 158, 851, 518, 185, 815… и уже не помнит, было ли 581. Так легко пропустить число или записать дважды.
Решавр строит карту перебора. Первая цифра — сначала самая маленькая, 1; к ней по порядку все возможные продолжения: 158, 185. Потом первая цифра 5: 518, 581. Потом 8: 815, 851. В каждой группе вторая цифра пробежала все оставшиеся цифры по порядку — значит, ничего не пропущено.
Правило
Организованный перебор — перебор по порядку: зафиксировать первый элемент, перебрать все продолжения по возрастанию (или по алфавиту), затем перейти к следующему первому элементу.
Числа 158 и 851 — разные варианты: порядок цифр важен. А матч «А — Б» и матч «Б — А» — один и тот же: тут порядок не важен, и пару записывают один раз. Например, три команды играют каждая с каждой: АБ, АВ, БВ — 3 матча.
Задача 5
Сколько двузначных чисел можно составить из цифр 0, 3, 7, если цифры могут повторяться?
Решение. 1) Первая цифра не может быть 0 — иначе число не двузначное. Значит, первая цифра 3 или 7.
2) Первая 3: 30, 33, 37. Первая 7: 70, 73, 77.
3) Проверка: в каждой группе вторая цифра пробежала 0, 3, 7 по порядку; число 07 не записано.
Ответ: 6 чисел.
Нашли вариант — проверьте, нет ли других
Найти один подходящий вариант — половина работы. Задача может иметь несколько решений, и спрашивают часто «сколько способов?» или «найдите все». Тогда карту вариантов заполняют до конца и каждый вариант подставляют во все условия: ответ готов, только когда перебраны все варианты.
Кто прав?
Нужно заплатить ровно 20 рублей монетами по 2 рубля и по 5 рублей. Сколькими способами это можно сделать? Монеты одного вида можно не брать совсем.
Иксератопс: «Две монеты по 5 рублей и пять монет по 2 рубля: $5 \cdot 2 + 2 \cdot 5 = 20$. Способ один».
Решавр: «Перебираю число пятирублевых монет по порядку: 0, 1, 2, 3, 4. Для каждого проверяю, делится ли остаток на 2. Способов три».
Показать разбор
Скрыть
Прав Решавр. Пятирублевых 0: остаток 20 рублей — десять монет по 2. Одна: остаток 15 — нечетный, не подходит. Две: остаток 10 — пять монет по 2. Три: остаток 5 — не подходит. Четыре: остаток 0 — двухрублевых нет. Пять пятирублевых — уже 25 рублей, больше нельзя.
Иксератопс остановился на первом найденном способе, а их три.
Решите сами
Средний уровень. Сколько трехзначных чисел больше 400 можно составить из цифр 2, 4, 6 без повторов?
Вызов. Выпишите все трехзначные числа из цифр 0, 1, 2 (цифры могут повторяться), у которых сумма цифр равна 3.
Показать ответы
Скрыть
Средний. Первая цифра 4: 426, 462; первая 6: 624, 642. Числа с первой цифрой 2 меньше 400. Ответ: 4 числа.
Вызов. Первая цифра не 0. Первая 1 — две другие дают в сумме 2: 102, 111, 120. Первая 2 — две другие дают 1: 201, 210. Ответ: 5 чисел.
Взвешивание: три исхода — три группы
Задача 6
Из 8 монет одна фальшивая, она легче. Есть чашечные весы без гирь. За какое наименьшее число взвешиваний ее всегда можно найти?
Решение. 1) Первое взвешивание: 3 монеты на левую чашу, 3 на правую, 2 оставляем на столе. Исходов три. Левая чаша легче — фальшивая среди ее 3 монет. Правая легче — среди ее 3. Равновесие — среди 2 монет на столе.
2) Второе взвешивание. Из 3 монет две кладем на чаши, третью оставляем на столе; из 2 монет кладем по одной на чаши. Легче чаша — фальшивая на ней, равновесие — на столе.
3) Одного взвешивания мало: у него три исхода, а значит, оно различает не больше 3 монет, а их 8. Меньше двух взвешиваний не обойтись.
Ответ: 2 взвешивания.
Правило
Взвешивание на чашечных весах дает три исхода: левая чаша легче, правая легче или равновесие. Поэтому монеты делят на три группы: часть на левую чашу, столько же на правую, остальные оставляют на столе. После взвешивания остается одна группа — не больше трети монет (с округлением вверх).
Одно взвешивание различает до 3 монет, два — до $3 \cdot 3 = 9$, три — до $9 \cdot 3 = 27$. Всего $k$ взвешиваний — до $3^k$ монет. Для 8 монет: $8 \lt 9$, поэтому двух взвешиваний хватает.
Показать, почему для 12 монет двух мало
Скрыть
Два взвешивания различают до 9 монет, а $12 \gt 9$. Какие бы три группы мы ни выбрали, в одной из них окажется не меньше 4 монет; если фальшивая окажется там, одного взвешивания на 4 монеты не хватит. Для 12 монет нужно три взвешивания.
Вывод
Логическая задача решается не догадкой, а картой вариантов: все возможности перед глазами, каждая отмечена «+» или «−». Так вы не пропустите решение. Так же решают, когда составляют расписание, турнир или перебирают пароли.
- «Кто есть кто»: таблица имена × варианты, в каждой строке и столбце один «+».
- Кто сказал правду: строки-гипотезы, число верных утверждений как в условии.
- Рыцари и лжецы: все варианты, рыцарь сказал правду, лжец — неправду.
- Числа, слова, способы: перебор по порядку без пропусков и повторов.
- Фальшивая монета: три группы — три исхода, $k$ взвешиваний различают до $3^k$ монет.
В следующем уроке карта вариантов превратится в дерево: так удобнее считать варианты, когда выбор делается в несколько шагов.
Часто задаваемые вопросы
Посмотрите на столбцы: иногда одна свободная клетка осталась в столбце. Если нет и там, проверьте гипотезы: поставьте «+» в одну из двух клеток и доведите таблицу до конца. Если получилась строка из одних «−», гипотеза неверна, и «+» стоит в другой клетке.
Проверка ловит ошибки переноса условия: «не» прочитали как «да», поставили знак не в ту клетку.
Спросите себя: если поменять местами два элемента, получится другой вариант? Число 15 и число 51 разные — порядок важен. Матч команд А и Б тот же, что матч Б и А, — порядок не важен.
Может. Если все гипотезы приводят к противоречию, в условии ошибка. Если подходят несколько вариантов, условия не хватает, и в ответ записывают все подходящие варианты.
Переходите к следующим темам и закрепляйте пройденное на практике.
- Более 330 000 пользователей по всей России, из них 39 000 учителей.
- Повышение среднего балла по предмету до 20 % после месяца занятий.
- Всплеск интереса к учебе и более глубокое понимание предметов.
Создайте бесплатный аккаунт — и откройте больше возможностей:
- Отслеживайте прогресс освоения тем
- Получайте персональные подборки полезных уроков и заданий
- Проводите работу над ошибками после занятий