Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

Логические задачи, перебор

Содержание

В этом уроке решаем логические задачи: кто есть кто, кто сказал правду, сколько чисел можно составить из цифр, как найти фальшивую монету. Раньше вы рисовали схему-отрезок — так было и в задачах на движение. Здесь вместо отрезка мы рисуем карту вариантов: таблицу или список, где каждый вариант виден и ни один не потерян.

Карта вариантов: каждая клетка отвечает «да или нет»

Начнем с задачи, к которой вернемся во втором разделе: Таня, Коля и Вера заняли в забеге первое, второе и третье места. Таня не первая. Коля не первый и не третий. Кто какое место занял, и единственный ли это ответ? Иксератопс отвечает сразу: «Таня не первая — значит, вторая». Проверим по карте.

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

Теперь читаем условие и отмечаем клетки. «Таня не первая» — в клетке «Таня, 1» ставим «−». «Коля не первый и не третий» — две клетки: «Коля, 1» и «Коля, 3» получают «−». Остальные клетки пока пустые.

Таблица забега: строки Таня, Коля, Вера, столбцы 1, 2, 3 место. Условие дало три минуса: Таня не первая, Коля не первый и не третий. У Коли свободна одна клетка — второе место
Условие перенесено на карту: три клетки получили «−», шесть пока пустые

Определение

Таблица «кто есть кто» — таблица, в которой строки — объекты (люди), столбцы — варианты (места, занятия, цвета). Знак «+» в клетке значит «подходит», знак «−» — «не подходит».

Правило

Если у каждого ровно один вариант и варианты у всех разные, то в каждой строке и в каждом столбце таблицы стоит ровно один «+».

Условие «не …» дает «−» в одной клетке. Условие «… — это …» дает «+» в клетке и «−» во всех остальных клетках ее строки и ее столбца.

Одна свободная клетка в строке — это ответ

Решим задачу из введения по карте: каждый «+» гасит свой столбец, а следующий ставим там, где свободна ровно одна клетка.

Три шага заполнения таблицы: Коля второй, значит Таня третья, значит Вера первая. Итог: Вера 1, Коля 2, Таня 3
Каждый «+» гасит свой столбец, и в соседней строке остается одна свободная клетка

Алгоритм

  1. Начертите таблицу: строки — объекты, столбцы — варианты.
  2. Перенесите условие: «−» за каждое «не», «+» за каждое прямое утверждение.
  3. Найдите строку или столбец, где свободна ровно одна клетка, поставьте в нее «+».
  4. Поставьте «−» в остальные клетки строки и столбца этого «+», вернитесь к шагу 3.
  5. Когда в каждой строке один «+», проверьте ответ по всем условиям.

Задача 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) Виноват Матвей: Кирилл солгал, Леонид сказал правду, Матвей солгал. Ложных два — не подходит.

Ответ: горшок опрокинул Леонид.

Проверка трех гипотез: виноват Кирилл — ложных высказываний 2, виноват Леонид — 1, виноват Матвей — 2. Подходит Леонид, где солгал ровно один
Строка — гипотеза, столбец — утверждение: условию подходит только строка с одним «−»

Правило

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

Рыцари и лжецы: если он правдив, что тогда

На острове живут рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. Встретились двое, Ян и Зоя, и каждый что-то сказал. Разберем, кто есть кто.

Вариантов всего четыре: каждый из двоих — рыцарь или лжец. Карта — четыре строки, и в каждой проверяем оба высказывания.

Задача 4

Ян сказал: «Зоя — лжец». Зоя сказала: «Мы оба рыцари». Кто есть кто?

Решение.

1) Оба рыцари: Ян сказал «Зоя — лжец», а она рыцарь, — рыцарь солгал. Противоречие.

2) Ян рыцарь, Зоя лжец: слова Яна верны; слова Зои «мы оба рыцари» ложны, как и положено лжецу. Противоречий нет.

3) Ян лжец, Зоя рыцарь: слова Зои «мы оба рыцари» ложны, а она рыцарь. Противоречие.

4) Оба лжецы: слова Яна «Зоя — лжец» верны, а он лжец. Противоречие.

Ответ: Ян — рыцарь, Зоя — лжец.

Четыре варианта для Яна и Зои. Подходит только Ян рыцарь, Зоя лжец: слова Яна верны, слова Зои ложны
Из четырех вариантов без противоречий только один: Ян — рыцарь, Зоя — лжец

Правило

Перебирают все варианты «рыцарь/лжец». Верить словам на острове нельзя: «Мы оба рыцари» может сказать и лжец. Вариант подходит, если каждый рыцарь в нем сказал правду, а каждый лжец — неправду.

Перебор по порядку: ничего не пропустить и не повторить

Сколько трехзначных чисел можно составить из цифр 1, 5, 8, если цифры в числе не повторяются? Иксератопс выписывает как придется: 158, 851, 518, 185, 815… и уже не помнит, было ли 581. Так легко пропустить число или записать дважды.

Решавр строит карту перебора. Первая цифра — сначала самая маленькая, 1; к ней по порядку все возможные продолжения: 158, 185. Потом первая цифра 5: 518, 581. Потом 8: 815, 851. В каждой группе вторая цифра пробежала все оставшиеся цифры по порядку — значит, ничего не пропущено.

Числа из цифр 1, 5, 8 без повторов: по первой цифре три группы, в каждой по два числа, 2 + 2 + 2 = 6
Три группы по первой цифре, в каждой по два числа: всего 6, без пропусков и повторов

Правило

Организованный перебор — перебор по порядку: зафиксировать первый элемент, перебрать все продолжения по возрастанию (или по алфавиту), затем перейти к следующему первому элементу.

Числа 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. Способов три».

Перебор: 20 рублей монетами по 2 и по 5. Подходят три строки из пяти: монет по 5 — 0, 2, 4. Способов: 3
Перебор по числу пятирублевых монет: подходят три строки из пяти, а Иксератопс нашел только одну и на ней остановился

Показать разбор

Скрыть

Прав Решавр. Пятирублевых 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 взвешивания.

Первое взвешивание 8 монет: 3 на левой чаше, 3 на правой, 2 на столе. Три исхода: легче левая чаша, легче правая чаша или равновесие. После него остается группа не больше чем из 3 монет
Три исхода взвешивания: после него остается группа не больше чем из 3 монет

Правило

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

Одно взвешивание различает до 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 разные — порядок важен. Матч команд А и Б тот же, что матч Б и А, — порядок не важен.

Может ли логическая задача иметь несколько ответов или ни одного?

Может. Если все гипотезы приводят к противоречию, в условии ошибка. Если подходят несколько вариантов, условия не хватает, и в ответ записывают все подходящие варианты.

Награды за урок
5
5
1
Количество опыта, полученного за урок 5
Ускорьте прогресс с полным доступом

Переходите к следующим темам и закрепляйте пройденное на практике.

  • Более 330 000 пользователей по всей России, из них 39 000 учителей.
  • Повышение среднего балла по предмету до 20 % после месяца занятий.
  • Всплеск интереса к учебе и более глубокое понимание предметов.
Не потеряйте прогресс!

Создайте бесплатный аккаунт — и откройте больше возможностей:

  • Отслеживайте прогресс освоения тем
  • Получайте персональные подборки полезных уроков и заданий
  • Проводите работу над ошибками после занятий

Спросить Зави Спросить Зави
Получить еще подсказку

Верно! Посмотрите пошаговое решение

Предложить улучшение