Войти
+7 (981) 962-15-85
Отзывы
+7 (495) 148-58-11
Курсы
Войти
Отдел продаж:
Звонок в школу:
меню
Курс · 8 уроков

Логика и смекалка

Восемь интерактивных уроков, на которых школьник осваивает приёмы решения логических и олимпиадных задач: от метода «предположим, что…» до выигрышных стратегий в играх.

🕵️

Учимся ловить противоречия: рыцари и лжецы, метод «предположим, что…», задачи «кто солгал».

🧩

Раскладываем всё по полочкам: таблицы соответствий, чётность, принцип Дирихле, инварианты.

⚖️

Планируем на шаги вперёд: взвешивания, переливания, графы и игровые стратегии.

✅

Проверка на каждом шагу: пошаговый разбор задач, подсказки и 72 задания с мгновенной проверкой ответа.

Все уроки на одной странице: проходите по порядку или выбирайте тему. Ответы проверяются сразу — решайте вместе с ребёнком в удобном темпе.

1 · Рыцари и лжецы 2 · Таблица против путаницы 3 · Чёт или нечет 4 · Кролики и клетки 5 · То, что не меняется 6 · Весы и вёдра 7 · Точки и линии 8 · Как выигрывать всегда
Решено заданий: 0
1

Курс «Логика и смекалка», урок 1 из 8

Рыцари и лжецы

Представь остров, где одни жители всегда говорят правду, а другие всегда врут. По внешности их не различить. Как по нескольким фразам понять, кто есть кто? Сегодня ты станешь детективом и научишься ловить лжеца на противоречии.

  • как рассуждать методом «предположим, что…»
  • как находить противоречие в чужих словах
  • как решать задачи, где говорят сразу несколько человек

Разминка подумай 2 минуты

?

Житель острова рыцарей и лжецов сказал: «Я лжец». Может ли так быть?

Ответ: да или нет.

Шаг 1Проверим первый вариант: пусть это рыцарь. Рыцарь всегда говорит правду, значит, фраза «я лжец» верна, и он лжец. Но мы предположили, что он рыцарь. Одновременно рыцарем и лжецом быть нельзя — получилось противоречие.
Шаг 2Проверим второй вариант: пусть это лжец. Лжец всегда врёт, значит, фраза «я лжец» неверна, и он не лжец, а рыцарь. Снова противоречие.
Шаг 3Оба варианта невозможны, а третьего на острове нет. Значит, такую фразу не может сказать никто.

Ответ: нет.

Запомни этот приём — «проверить оба варианта». На нём построен весь урок.

Главная идея

На острове живут жители двух типов. Внешне они ничем не отличаются, различить их можно только по словам.

Рыцари всегда говорят правду. Значит, всё, что сказал рыцарь, — верно.
Лжецы всегда лгут. Значит, всё, что сказал лжец, — неверно.

Мы не знаем заранее, кто перед нами. Поэтому рассуждаем так: предполагаем, что житель — рыцарь, и смотрим, что из этого получится. Если в рассуждении появилась нелепость, предположение было неверным, и житель — лжец.

Что такое противоречие. Это когда два вывода не могут быть верны одновременно. Например, мы предположили «Аня — рыцарь», а в конце рассуждения получили «Аня — лжец». Так быть не может, значит, где-то ошибка — и ошибка в самом предположении.

Самое трудное место — понять, что значит «фраза лжеца неверна». Нельзя просто поставить частицу «не» к каждому слову. Посмотри на примеры:

Фраза лжецаЧто на самом деле (фраза неверна)Типичная ошибка
«Мы оба лжецы»хотя бы один из нас рыцарь (может, один, а может, и оба)«мы оба рыцари»
«Среди нас ровно 2 лжеца»лжецов не 2: их может быть 0, 1, 3…«лжецов 3»
«Оба моих соседа — лжецы»хотя бы один сосед — рыцарь«оба соседа рыцари»
«Хотя бы один из нас лжец»лжецов нет совсем, все рыцари«один из нас рыцарь»
План решения
  1. Выбери одного жителя, с которого начнёшь. Удобнее всего начинать с того, кто говорит о себе или о ком-то одном.
  2. Предположи, что он рыцарь. Раз рыцарь говорит правду, его фраза верна. Запиши, что из неё следует. Например, если он сказал «Боря — лжец», запиши: «Боря — лжец».
  3. Продолжай рассуждать: теперь ты знаешь, кто такой Боря, и можешь разобрать его фразу тем же способом.
  4. На каждом шаге проверяй, нет ли противоречия: не получилось ли, что кто-то одновременно и рыцарь, и лжец, или что условие задачи нарушено.
  5. Если противоречие появилось — предположение неверно, и первый житель лжец. Его фраза неверна: по таблице выше найди, что тогда верно на самом деле, и рассуждай дальше.
  6. Если противоречия нет — не спеши с ответом. Проверь и второй вариант (что житель — лжец). Если подходят оба варианта, по этим фразам тип жителя определить нельзя.
  7. В конце сделай проверку: пройди по всем жителям и убедись, что у каждого рыцаря фраза верна, а у каждого лжеца — неверна.

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. Двое на дороге

Житель А говорит про себя и своего спутника Б: «Мы оба лжецы». Кто такой А и кто такой Б?

Шаг 1Поймём, что утверждает А. Он говорит сразу две вещи: «я, А, — лжец» и «Б — лжец».
Шаг 2Предположим, что А — рыцарь. Рыцарь говорит правду, значит, обе части фразы верны. В частности, верно «А — лжец». Но мы предположили, что А рыцарь. Противоречие.

Почему? Один и тот же житель не может быть одновременно рыцарем и лжецом. Значит, предположение «А — рыцарь» неверно.

Шаг 3Значит, А — лжец. Тогда его фраза «мы оба лжецы» ложна.
Шаг 4Когда фраза «мы оба лжецы» ложна? Когда хотя бы один из двоих — не лжец, то есть рыцарь. Сам А лжец, значит, рыцарь — Б.

Проверка. А — лжец, Б — рыцарь. А сказал «мы оба лжецы». На самом деле Б рыцарь, значит, фраза ложна. Лжец и должен говорить ложь — всё сходится.

Частая ошибка. думать, что раз «мы оба лжецы» — ложь, то «мы оба рыцари». Нет! Для ложности достаточно, чтобы рыцарем был хотя бы один.

Ответ: А — лжец, Б — рыцарь.

СреднеЗадача 2. Три разных мнения

Трое жителей говорят о себе:
А: «Среди нас ровно один лжец».
Б: «Среди нас ровно два лжеца».
В: «Среди нас все трое лжецы».
Кто рыцарь, а кто лжец?

Шаг 1Заметим, что все трое говорят об одном и том же — о количестве лжецов. Но называют разные числа: 1, 2 и 3.
Шаг 2Могут ли две фразы быть верными одновременно? Нет: лжецов не может быть сразу, например, и один, и два. Значит, верной может быть только одна фраза или ни одной.

Почему? Рыцарь — это тот, чья фраза верна. Раз верных фраз не больше одной, то и рыцарей не больше одного.

Шаг 3Проверим вариант «рыцарей нет». Тогда все трое лжецы, лжецов ровно три. Но тогда фраза В «все трое лжецы» верна, и В — рыцарь. Противоречие, этот вариант не подходит.
Шаг 4Остался вариант «рыцарь ровно один». Тогда лжецов ровно два. Кто это сказал? Б. Значит, фраза Б верна: Б — рыцарь, а А и В — лжецы.
ЖительЧто сказалНа самом деле лжецов 2Кто он
Аровно 1 лжецложьлжец ✓
Бровно 2 лжецаправдарыцарь ✓
Ввсе 3 лжецыложьлжец ✓

Проверка. в таблице у каждого рыцаря фраза верна, у каждого лжеца — ложна.

Ответ: Б — рыцарь, А и В — лжецы.

СложнееЗадача 3. Круглый стол

★ Задача со звёздочкой

За круглым столом сидят 10 жителей. Каждый сказал: «Оба моих соседа — лжецы». Сколько рыцарей может быть за столом? Найди наибольшее и наименьшее число.

Подумай, могут ли два рыцаря сидеть рядом и могут ли три лжеца сидеть подряд. Для наименьшего числа рыцарей: сколько лжецов может оказаться между двумя соседними рыцарями?

Шаг 1Переведём фразу рыцаря. Он говорит правду, значит, оба его соседа — лжецы. Вывод: два рыцаря рядом сидеть не могут.
Шаг 2Переведём фразу лжеца. Он лгёт, значит, неверно, что оба соседа лжецы. То есть хотя бы один его сосед — рыцарь.

Что из этого следует? Три лжеца подряд сидеть не могут. У среднего из них оба соседа были бы лжецы, и его фраза «оба соседа лжецы» оказалась бы правдой. А лжец правду не говорит.

Шаг 3Ищем наибольшее число рыцарей. Разбём 10 мест на 5 пар соседних мест: (1, 2), (3, 4), (5, 6), (7, 8), (9, 10). В каждой паре сидят соседи, поэтому в ней не больше одного рыцаря. Пар 5 — значит, рыцарей не больше 5.
Шаг 4Проверим, что 5 бывает. Посадим по очереди: рыцарь, лжец, рыцарь, лжец… У каждого рыцаря соседи — лжецы, его фраза верна. У каждого лжеца соседи — рыцари, его фраза неверна. Всё сходится, наибольшее число — 5.
Шаг 5Ищем наименьшее число рыцарей. Попробуем обойтись тремя рыцарями. Пойдём вокруг стола: рыцарь, потом группа лжецов, потом следующий рыцарь, снова группа лжецов, третий рыцарь и последняя группа лжецов (она сидит между третьим и первым рыцарем — стол ведь круглый). Групп лжецов получается столько же, сколько рыцарей, — 3. В каждой группе не больше 2 лжецов, потому что три лжеца подряд сидеть не могут. Значит, лжецов не больше 3 × 2 = 6, а всего людей не больше 3 + 6 = 9. Но за столом 10 человек — троих рыцарей мало. Если рыцарей 2, людей не больше 2 + 2 × 2 = 6; если 1 — не больше 3; если рыцарей нет, все 10 — лжецы, и три лжеца подряд обязательно найдутся. Всё это не подходит.
Шаг 6Значит, рыцарей хотя бы 4. Осталось найти пример с 4 рыцарями: Р Л Л Р Л Л Р Л Р Л (по кругу).
Р1Л2Л3Р4Л5Л6Р7Л8Р9Л10
Синие кружки — рыцари (Р), белые — лжецы (Л). У каждого рыцаря оба соседа — лжецы, у каждого лжеца есть сосед-рыцарь.

Проверка. пройди по кругу на схеме. Возле каждого синего кружка (рыцаря) — два белых. Возле каждого белого (лжеца) есть хотя бы один синий. Места 10 и 1 тоже соседи!

Ответ: наименьшее число рыцарей — 4, наибольшее — 5.

Запомни

1. Предположи, что житель рыцарь, и найди противоречие или его отсутствие.

2. Проверяй оба варианта: иногда подходят оба, иногда ни один.

3. Отрицание «все такие» — это «хотя бы один не такой».

4. Если несколько фраз противоречат друг другу, верной может быть только одна.

Интересный факт

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

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

Аня сказала: «Боря — лжец». Боря сказал: «Мы с Аней одного типа». Кто из них рыцарь?

Ответ: имя.

Шаг 1Предположим, Аня — рыцарь. Тогда её фраза верна: Боря — лжец.
Шаг 2Проверим фразу Бори. Он сказал «мы одного типа». На деле Аня рыцарь, Боря лжец — типы разные, фраза ложна. Боря лжец и соврал — противоречия нет.
Шаг 3Проверим второй вариант: Аня — лжец. Тогда её фраза ложна, и Боря — рыцарь. Боря сказал «мы одного типа», а на деле они разные — фраза ложна. Но рыцарь не может лгать. Противоречие.

Ответ: рыцарь — Аня.

2

В комнате 5 жителей. Каждый сказал: «Среди нас ровно 3 рыцаря». Сколько рыцарей в комнате?

Ответ: число.

Шаг 1Все пятеро сказали одну и ту же фразу об одной и той же комнате. Такая фраза либо верна, либо неверна — сразу для всех. Если она верна, то каждый, кто её сказал, говорил правду, значит, все — рыцари. Если неверна — все солгали, значит, все — лжецы. Смешанного варианта быть не может.
Шаг 2Пусть все рыцари. Тогда рыцарей 5, а фраза «ровно 3 рыцаря» неверна. Рыцари так сказать не могли — не подходит.
Шаг 3Пусть все лжецы. Тогда рыцарей 0, и фраза «ровно 3 рыцаря» действительно ложна. Всё сходится.

Ответ: 0.

3

8 жителей стоят в хороводе. Каждый сказал: «Мой сосед справа — лжец». Сколько среди них рыцарей?

Ответ: число.

Шаг 1Если житель — рыцарь, его фраза верна: справа от него стоит лжец.
Шаг 2Если житель — лжец, его фраза неверна: справа от него стоит рыцарь.
Шаг 3Идём по кругу: после рыцаря всегда лжец, после лжеца всегда рыцарь. Они строго чередуются: Р Л Р Л Р Л Р Л.
Шаг 4При чередовании рыцарей и лжецов поровну: 8 : 2 = 4.
Р1Л2Р3Л4Р5Л6Р7Л8
Рыцари и лжецы чередуются, поэтому их поровну.

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

Ответ: 4.

4

Первый из двух жителей сказал: «Хотя бы один из нас — лжец». Сколько рыцарей среди этих двоих?

Ответ: число.

Шаг 1Предположим, первый — лжец. Тогда среди двоих точно есть лжец (он сам), и фраза «хотя бы один из нас лжец» верна. Но лжец не говорит правду. Противоречие.
Шаг 2Значит, первый — рыцарь, и его фраза верна: среди двоих есть лжец.
Шаг 3Сам первый рыцарь, значит, лжец — второй.

Ответ: рыцарь один — 1.

5

Аня: «Боря — лжец». Боря: «Вика — лжец». Вика: «Аня и Боря — оба лжецы». Кто из троих рыцарь?

Ответ: одно имя.

Шаг 1Предположим, Аня — рыцарь. Тогда Боря — лжец (так сказала Аня).
Шаг 2Боря лжец, значит, его фраза «Вика — лжец» ложна: Вика — рыцарь.
Шаг 3Вика рыцарь, значит, её фраза верна: Аня и Боря оба лжецы. Но мы начали с того, что Аня рыцарь. Противоречие.
Шаг 4Значит, Аня — лжец. Её фраза ложна: Боря — рыцарь. Фраза Бори верна: Вика — лжец.

Проверка. Вика (лжец) сказала «Аня и Боря оба лжецы». На деле Боря рыцарь, фраза ложна — так и должно быть.

Ответ: рыцарь — Боря.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

Четверо жителей сказали:
первый: «Среди нас ровно один лжец»,
второй: «Среди нас ровно два лжеца»,
третий: «Среди нас ровно три лжеца»,
четвёртый: «Среди нас ровно четыре лжеца».
Сколько среди них лжецов?

Ответ: число.

Шаг 1Все четыре фразы называют разное количество лжецов, поэтому верной может быть не больше одной фразы. Значит, рыцарей 0 или 1.
Шаг 2Пусть рыцарей нет. Тогда лжецов четверо, и фраза четвёртого верна — он рыцарь. Противоречие.
Шаг 3Значит, рыцарь ровно один, а лжецов ровно три. Это сказал третий — он и есть рыцарь.

Ответ: лжецов 3.

2

За круглым столом сидят 12 жителей, и каждый сказал: «Оба моих соседа — лжецы». Какое наименьшее число рыцарей может быть за столом?

Ответ: число.

Шаг 1Вспомним выводы из разбора задачи 3. Рыцарь сказал правду: оба его соседа лжецы, поэтому два рыцаря рядом не сидят. Лжец соврал: у него есть сосед-рыцарь, поэтому три лжеца подряд не сидят. Значит, между двумя соседними рыцарями сидит группа из 1 или 2 лжецов.
Шаг 2Пусть рыцарей 3. Тогда групп лжецов между ними тоже 3, и в каждой не больше 2 человек. Всего людей не больше 3 + 3 × 2 = 9, а за столом 12. Не хватает. При меньшем числе рыцарей людей помещается ещё меньше.
Шаг 3Значит, рыцарей хотя бы 4. Пример: Р Л Л Р Л Л Р Л Л Р Л Л. У каждого рыцаря оба соседа лжецы, у каждого лжеца один сосед — рыцарь.

Ответ: 4.

3

В хороводе стоят 2026 жителей. Каждый сказал: «Мой сосед слева — лжец». Сколько рыцарей в хороводе?

Ответ: число.

Шаг 1Слева от рыцаря стоит лжец (рыцарь сказал правду). Слева от лжеца стоит рыцарь (лжец соврал).
Шаг 2Значит, рыцари и лжецы чередуются, как в задаче 3 из «Проверь себя».
Шаг 3При чередовании их поровну: 2026 : 2 = 1013.

Ответ: 1013.

Верно: 0 из 3

2

Курс «Логика и смекалка», урок 2 из 8

Таблица против путаницы

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

  • как составлять таблицу для задачи на соответствие
  • как из одного плюса получить сразу несколько минусов
  • как решать задачи, где кто-то говорит неправду

Разминка подумай 2 минуты

?

У Маши, Даши и Саши есть кошка, собака и попугай — у каждой по одному питомцу. У Маши не кошка и не попугай. У Даши не кошка. У кого кошка?

Ответ: имя.

Шаг 1Смотрим на Машу: у неё не кошка и не попугай. Из трёх питомцев остаётся только собака.
Шаг 2Смотрим на Дашу: у неё не кошка. Собака уже у Маши. Остаётся попугай.
Шаг 3Саше достаётся последний питомец — кошка.

Ответ: у Саши.

Главная идея

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

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

В клетку ставим − (минус), если точно не подходит, и + (плюс), если точно подходит.

Таблица помогает благодаря двум правилам:

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

Как это выглядит на разминке. Условия «у Маши не кошка и не попугай», «у Даши не кошка» дают минусы:

КошкаСобакаПопугай
Маша−−
Даша−
Саша

В строке «Маша» пустой осталась одна клетка — «Собака». Других вариантов нет, ставим туда плюс. По правилу 2 ставим минусы в столбце «Собака» у Даши и Саши. Теперь у Даши пустая только клетка «Попугай» — плюс, и минус у Саши в этом столбце. Саше остаётся «Кошка»:

КошкаСобакаПопугай
Маша−+−
Даша−−+
Саша+−−

Перебор вариантов. Бывают условия, из которых минус сразу не поставишь: «Рита старше Олега на два класса». Тогда выписываем все пары классов, которые подходят к этому условию, и проверяем каждую пару по остальным условиям. Пара, которая нарушает хоть одно условие, отпадает.

Задачи «кто солгал». Если известно, сколько человек сказали правду, по очереди предполагаем виновным каждого подозреваемого. Для каждого случая проверяем все фразы и считаем, сколько из них верны. Подходит тот случай, где число верных фраз совпадает с условием.

План решения
  1. Найди в задаче две группы, между которыми нужно найти соответствие (например, фамилии и профессии).
  2. Нарисуй таблицу: первая группа — слева в начале строк, вторая — сверху над столбцами.
  3. Прочитай условия по одному. Каждое условие вида «у Маши не кошка» — это минус в клетке на пересечении строки «Маша» и столбца «Кошка».
  4. Найди строку или столбец, где пустой осталась только одна клетка. Поставь в неё плюс.
  5. Сразу поставь минусы во всех остальных клетках строки и столбца этого плюса. Затем снова ищи строку или столбец с одной пустой клеткой.
  6. Если условие сравнивает («старше», «выше», «сразу после»), выпиши все подходящие к нему варианты и проверь каждый по остальным условиям. Неподходящие вычеркни.
  7. Если известно, что правду сказал только один (или только двое), по очереди считай виновным каждого подозреваемого, проверь все фразы и посчитай верные.
  8. В конце проверь ответ по всем условиям задачи.

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. Кузнецов, Столяров и Слесарев

Кузнецов, Столяров и Слесарев работают кузнецом, столяром и слесарем. Ни у кого фамилия не совпадает с профессией. Столяров — не слесарь. Кто кем работает?

Шаг 1Рисуем таблицу: строки — фамилии, столбцы — профессии.
Шаг 2Условие «фамилия не совпадает с профессией» даёт три минуса: Кузнецов — не кузнец, Столяров — не столяр, Слесарев — не слесарь. Ещё один минус: Столяров — не слесарь.
КузнецСтолярСлесарь
Кузнецов−
Столяров−−
Слесарев−
Шаг 3В строке «Столяров» осталась одна пустая клетка — «Кузнец». Ставим плюс. По правилу 2 в столбце «Кузнец» у остальных ставим минусы.
Шаг 4Теперь в строке «Слесарев» пустая только клетка «Столяр» — плюс. Кузнецову остаётся «Слесарь».
КузнецСтолярСлесарь
Кузнецов−−+
Столяров+−−
Слесарев−+−

Проверка. ни у кого фамилия не совпадает с профессией, и Столяров не слесарь.

Ответ: Столяров — кузнец, Слесарев — столяр, Кузнецов — слесарь.

СреднеЗадача 2. Четыре класса

Олег, Павел, Рита и Света учатся в 7, 8, 9 и 10 классах — все в разных. Рита старше Олега на два класса. Света учится не в 10 классе. Павел младше Светы. Кто в каком классе?

Здесь условия не прямые («старше», «младше»), поэтому сразу поставить плюсы не получится. Воспользуемся перебором.

Шаг 1Разберём условие «Рита старше Олега на два класса». Какие пары классов подходят? 7 и 9, 8 и 10. Других нет: класса 11 и 6 в задаче нет.

Итак, два варианта: Олег в 7, Рита в 9 — или Олег в 8, Рита в 10.

Шаг 2Проверим вариант 1: Олег — 7, Рита — 9. Павлу и Свете остаются 8 и 10. Павел младше Светы, значит, Павел в 8, Света в 10. Но Света учится не в 10 классе! Противоречие — вариант не подходит.
Шаг 3Проверим вариант 2: Олег — 8, Рита — 10. Павлу и Свете остаются 7 и 9. Павел младше: Павел — 7, Света — 9. Света не в 10 — хорошо.

Проверка. Рита (10) старше Олега (8) на два класса ✓; Света не в 10 ✓; Павел (7) младше Светы (9) ✓.

Ответ: Павел — 7, Олег — 8, Света — 9, Рита — 10.

СложнееЗадача 3. Кто разбил вазу

Ваза разбита, подозреваются трое. Коля: «Это не я». Миша: «Это Коля». Петя: «Это не Миша». Известно, что правду сказал только один из них. Кто разбил вазу?

Мы не знаем, кто лжёт, поэтому перебираем, кто виноват, и в каждом случае проверяем все фразы.

Шаг 1Пусть вазу разбил Коля. Коля говорит «не я» — это ложь. Миша говорит «это Коля» — правда. Петя говорит «не Миша» — правда (виноват Коля). Верных фраз две, а должна быть одна. Не подходит.
Шаг 2Пусть вазу разбил Миша. Коля: «не я» — правда. Миша: «это Коля» — ложь. Петя: «не Миша» — ложь. Верная фраза одна. Подходит!
Шаг 3Для надёжности проверим Петю. Коля: «не я» — правда. Миша: «это Коля» — ложь. Петя: «не Миша» — правда. Верных две. Не подходит.
Шаг 4Удобно записать всё в таблицу:
ВиноватКоля: «не я»Миша: «Коля»Петя: «не Миша»Правдивых
Коляложьправдаправда2
Мишаправдаложьложь1 ✓
Петяправдаложьправда2

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

Ответ: вазу разбил Миша.

Запомни

1. Строки — одна группа, столбцы — другая. В каждой строке и каждом столбце ровно один плюс.

2. Поставил плюс — ставь минусы во всей строке и во всём столбце.

3. Если условия «старше», «выше», «раньше» — перебери несколько вариантов.

4. Если «кто-то солгал», перебери всех подозреваемых и посчитай правдивые фразы.

Интересный факт

Самая известная задача такого типа — «Загадка Эйнштейна»: пять домов, пять национальностей, пять напитков и вопрос «Кто держит рыбку?». Говорят, её решает только 2% людей. На самом деле с таблицей её решает почти каждый — нужно лишь терпение.

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

Аня, Вера и Галя пришли в красном, синем и зелёном платьях. Аня не в красном и не в зелёном. Вера не в зелёном. Кто в зелёном платье?

Ответ: имя.

Шаг 1У Ани не красное и не зелёное — остаётся синее.
Шаг 2У Веры не зелёное. Синее уже занято Аней. Остаётся красное.
Шаг 3Гале достаётся последнее — зелёное.

Ответ: Галя.

2

Беседуют Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Ни у кого из нас цвет волос не совпадает с фамилией». Какой цвет волос у Рыжова?

Ответ: одно слово (например, «блондин»).

Шаг 1Условие «не совпадает с фамилией»: Белокуров — не блондин, Чернов — не брюнет, Рыжов — не рыжий.
Шаг 2Брюнет разговаривает с Белокуровым, значит, Белокуров — не брюнет (сам с собой он не говорит). Белокуров не блондин и не брюнет — значит, рыжий.
Шаг 3Чернов не брюнет, и рыжий уже занят. Чернов — блондин.
Шаг 4Рыжову остаётся цвет — брюнет.

Ответ: брюнет.

3

Дима, Женя, Ира и Коля заняли в забеге места с 1 по 4. Дима не первый и не последний. Женя прибежал сразу после Димы. Ира не первая. Какое место занял Коля?

Ответ: число.

Шаг 1Дима не первый и не четвёртый — значит, он второй или третий. Разберём оба случая.
Шаг 2Дима 2-й. Женя сразу после него — 3-й. Остались места 1 и 4 для Иры и Коли. Ира не первая — она 4-я, а Коля 1-й.
Шаг 3Дима 3-й. Женя — 4-й. Остались места 1 и 2. Ира не первая — она 2-я, а Коля 1-й.
Шаг 4В обоих случаях Коля первый.

Интересно: полную расстановку мы не узнали, но на вопрос ответили точно.

Ответ: 1.

4

В трёх коробках лежат 5, 7 и 9 конфет. В синей коробке больше, чем в красной, а в зелёной меньше, чем в красной. Сколько конфет в красной коробке?

Ответ: число.

Шаг 1Выстроим коробки по порядку: зелёная меньше красной, красная меньше синей.
Шаг 2Получается: зелёная < красная < синяя. Красная — посередине.
Шаг 3Среднее из чисел 5, 7, 9 — это 7.

Ответ: 7.

5

Пирог пропал. Аня: «Это Боря». Боря: «Это Галя». Вика: «Это не я». Галя: «Боря лжёт». Правду сказал ровно один. Кто съел пирог?

Ответ: имя.

Перебираем подозреваемых и для каждого проверяем все четыре фразы. Обрати внимание на Галю: «Боря лжёт» верно, когда фраза Бори ложна.

СъелАня: «Боря»Боря: «Галя»Вика: «не я»Галя: «Боря лжёт»Правдивых
Аняложьложьправдаправда2
Боряправдаложьправдаправда3
Викаложьложьложьправда1 ✓
Галяложьправдаправдаложь2

Ровно одна правдивая фраза получается только в строке «Вика».

Ответ: Вика.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

Алла, Боря, Вадим и Гоша больше всего любят разные предметы: математику, физику, историю и химию. Боря не любит ни историю, ни химию. Гоша не любит ни математику, ни химию. Алла не любит ни физику, ни химию, а ещё Алла сидит за партой рядом с любителем математики. Какой предмет любит Гоша?

Ответ: название предмета.

Шаг 1Столбец «химия»: минусы у Бори, Гоши и Аллы. Значит, химию любит Вадим.
Шаг 2Алла сидит рядом с любителем математики — значит, сама она математику не любит. Ещё она не любит физику и химию. Остаётся история.
Шаг 3Гоша не любит математику и химию, история занята Аллой. Гоше остаётся физика, а Боре — математика.
МатематикаФизикаИсторияХимия
Алла−−+−
Боря+−−−
Вадим−−−+
Гоша−+−−

Ответ: физика.

2

Пять ребят разного роста. Ася выше Бори, Боря выше Вовы, Гена ниже Вовы, Дима выше Аси. Кто третий по росту, если считать от самого высокого?

Ответ: имя.

Шаг 1Выпишем цепочки: Ася выше Бори, Боря выше Вовы. Получаем: Ася, Боря, Вова.
Шаг 2«Гена ниже Вовы» — ставим Гену в конец: Ася, Боря, Вова, Гена.
Шаг 3«Дима выше Аси» — ставим Диму в начало: Дима, Ася, Боря, Вова, Гена.
Шаг 4Считаем от самого высокого: 1 — Дима, 2 — Ася, 3 — Боря.

Ответ: Боря.

3

Три подруги — Лена, Оля и Таня — живут на 2, 5 и 8 этажах. Лена живёт выше Оли. Таня живёт не на 8 этаже и не на 2. На каком этаже живёт Оля?

Ответ: число.

Шаг 1Таня не на 8 и не на 2 — значит, на 5.
Шаг 2Лене и Оле остаются 2 и 8 этажи.
Шаг 3Лена выше Оли, значит, Лена на 8, Оля на 2.

Ответ: 2.

Верно: 0 из 3

3

Курс «Логика и смекалка», урок 3 из 8

Чёт или нечет

Может ли кузнечик вернуться домой за 25 прыжков? Можно ли разменять деньги нужными монетами? Бывают задачи, где считать ничего не надо — достаточно понять, чётное число получится или нечётное. Узнаем, как одна маленькая идея закрывает целые классы задач.

  • как чётность суммы помогает доказать «нельзя»
  • что такое чередование и почему оно ломается на нечётном
  • как считать «пары», не пересчитывая всё дважды

Разминка подумай 2 минуты

?

По кругу стоят 5 шестерёнок, каждая сцеплена с двумя соседними. Может ли такая система вращаться?

Ответ: да или нет.

Шаг 1Если две шестерёнки сцеплены, они крутятся в разные стороны.
Шаг 2Пусть шестерёнка 1 крутится по часовой стрелке. Тогда 2 — против, 3 — по, 4 — против, 5 — по часовой.
Шаг 3Но шестерёнка 5 сцеплена ещё и с шестерёнкой 1. Они должны крутиться в разные стороны, а у нас обе по часовой. Противоречие — система заклинит.

При чётном числе шестерёнок (например, 6) направления сошлись бы, и система вращалась бы.

Ответ: нет.

Главная идея

Чётные числа делятся на 2 без остатка: 0, 2, 4, 6, 8… Нечётные на 2 не делятся: 1, 3, 5, 7, 9… Сказать про число «чётное» или «нечётное» — значит назвать его чётность.

Удобно представлять число как кучку предметов. Чётную кучку можно разложить по парам без остатка. В нечётной один предмет всегда остаётся без пары.

Отсюда правила сложения. Складываем две кучки и смотрим, остался ли предмет без пары:

СкладываемЧто получаетсяПримерПочему
чётное + чётноечётное4 + 6 = 10пары + пары = только пары
чётное + нечётноенечётное4 + 5 = 9одна лишняя штука так и осталась без пары
нечётное + нечётноечётное3 + 5 = 8две лишние штуки вместе составили пару

С вычитанием то же самое: 9 − 4 = 5 (нечётное − чётное = нечётное), 9 − 3 = 6 (нечётное − нечётное = чётное).

Из этих правил получаются три вывода, которые решают все задачи урока:

Вывод 1. Сумма нескольких нечётных чисел чётная, если их чётное количество, и нечётная, если их нечётное количество. Проверь: 1 + 3 + 5 = 9 (три числа — сумма нечётная), 1 + 3 + 5 + 7 = 16 (четыре числа — сумма чётная). Каждые два нечётных числа вместе дают чётное, и «лишнее» может остаться, только если количество нечётное.

Вывод 2. Если к числу прибавить чётное число или вычесть чётное число, чётность не изменится: 9 + 4 = 13 и 9 − 6 = 3 — всё ещё нечётные.

Вывод 3. Если что-то всё время чередуется (по часовой — против часовой, вправо — влево, белая клетка — чёрная), то вернуться к тому, с чего начали, можно только за чётное число шагов. После 1 шага мы на «другом», после 2 — снова на «своём», после 3 — на «другом» и так далее.

План решения
  1. Найди в задаче число, которое меняется при каждом действии. Например: количество прыжков, сумма чисел на доске, количество перевёрнутых стаканов.
  2. Определи, чётное это число или нечётное в начале.
  3. Разбери одно действие (один прыжок, одну замену знака, один ход) на конкретном примере. На сколько изменилось число? Если на чётное — по выводу 2 чётность осталась прежней. Если на нечётное — она поменялась.
  4. Определи, каким должно быть это число, когда цель задачи достигнута, и какая у него чётность. Например, «все стаканы стоят правильно» — значит, перевёрнутых 0, а 0 чётное.
  5. Сравни. Если чётность при действиях не меняется, а в начале и в цели она разная, — цели не достичь, ответ «нельзя».
  6. Если чётности в начале и в цели совпадают, чётность не мешает. Это ещё не значит «можно» — попробуй подобрать пример, который показывает, как это сделать.

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. Кузнечик

Кузнечик прыгает по прямой, каждый раз на 1 см влево или вправо. Может ли он через 25 прыжков оказаться в исходной точке?

−4−3−2−1012341 см1 см
Кузнечик стоит в точке 0 и каждым прыжком сдвигается на 1 влево или вправо.
Шаг 1Чтобы вернуться в начало, кузнечик должен сколько-то раз прыгнуть вправо и столько же раз влево. Иначе он окажется правее или левее старта.
Шаг 2Например, 3 прыжка вправо и 3 влево — всего 6 прыжков. 10 вправо и 10 влево — 20 прыжков.
Шаг 3Всего прыжков получается «какое-то число + такое же число», то есть число, умноженное на 2. Такое число всегда чётное.
Шаг 425 — нечётное число. Значит, вернуться за 25 прыжков нельзя.

Ответ: нельзя.

СреднеЗадача 2. Плюсы и минусы

Между числами 1, 2, 3, …, 10 ставят знаки «+» или «−». Можно ли получить в результате 0?

Шаг 1Сначала поставим везде «+»: 1 + 2 + 3 + … + 10 = 55. Это нечётное число.
Шаг 2Теперь заменим один «+» на «−», например перед числом 4. Было +4, стало −4. Сумма уменьшилась на 8, то есть на 4 × 2.

Почему? Когда меняем знак перед числом, сумма уменьшается на удвоенное это число. Удвоенное число всегда чётное.

Шаг 3Отнимая чётное число, мы не меняем чётность (правило 2). Значит, после любой замены знаков сумма останется нечётной, как 55.
Шаг 4Ноль — чётное число. Нечётная сумма нулём быть не может.

Частая ошибка. пытаться перебирать все расстановки знаков. Их больше пятисот! Чётность решает задачу за минуту.

Ответ: нельзя.

СреднеЗадача 3. Перевёрнутые стаканы

На столе 7 стаканов, все стоят донышком вверх. За один ход можно перевернуть ровно 2 любых стакана. Можно ли поставить все стаканы правильно?

Шаг 1Будем следить за числом стаканов, которые стоят донышком вверх («неправильных»). Сейчас их 7.
Шаг 2Посмотрим, что бывает за один ход. Переворачиваем два стакана:
Какие стаканы перевернулиКак меняется число неправильных
оба неправильныеуменьшается на 2
оба правильныеувеличивается на 2
один такой, один другойне меняется
Шаг 3В любом случае число неправильных стаканов меняется на чётное число или не меняется. Значит, его чётность сохраняется.
Шаг 4Сначала неправильных 7 — нечётное число. Значит, их всегда будет нечётное количество: 7, 5, 3, 1, 3…
Шаг 5А нам нужно, чтобы неправильных было 0 — это чётное число. Получить его нельзя.

Ответ: нельзя.

СложнееЗадача 4. Дружный класс

В классе 25 учеников. Может ли быть так, что каждый дружит ровно с пятью одноклассниками?

Шаг 1Представим, что каждый ученик записал на листочке имена своих 5 друзей. Всего имён на всех листочках: 25 × 5 = 125.
Шаг 2Посмотрим на одну дружбу, например Пети и Васи. Петя записал на своём листочке Васю, а Вася на своём — Петю. Получается, одна дружба попала в записи два раза. Так с каждой дружбой.
Шаг 3Значит, количество записей = 2 × (количество дружб). Это число обязательно чётное.
Шаг 4У нас получилось 125 — нечётное. Противоречие, так быть не может.

Проверка. если бы каждый дружил с 4 одноклассниками, записей было бы 25 × 4 = 100 — чётное, и чётность уже не мешала бы.

Ответ: не может.

Запомни

1. Сумма нечётных чисел чётна тогда и только тогда, когда их чётное количество.

2. Прибавление или вычитание чётного числа чётность не меняет.

3. Если свойство чередуется, замкнуть круг можно только за чётное число шагов.

4. Если каждую пару посчитали дважды, итог обязательно чётный.

Интересный факт

Идея чётности защищает твои данные. Когда файл передаётся по интернету, к нему добавляют «бит чётности». Если по дороге одна цифра исказилась, чётность изменится, и компьютер сразу поймёт, что файл пришёл с ошибкой.

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

Какой остаток при делении на 2 даёт сумма 1 + 3 + 5 + … + 99 (все нечётные числа от 1 до 99)?

Ответ: число 0 или 1.

Шаг 1Посчитаем, сколько нечётных чисел от 1 до 99. Среди чисел от 1 до 100 ровно половина нечётные: 100 : 2 = 50.
Шаг 2Складываем 50 нечётных чисел. 50 — чётное количество, значит, сумма чётная.
Шаг 3Чётное число при делении на 2 даёт остаток 0.

Для любопытных: сама сумма равна 2500.

Ответ: 0.

2

На доске написаны числа 1, 2, 3, …, 10. За ход стирают любые два числа и записывают их разность (из большего вычитают меньшее). В конце осталось одно число. Какой остаток при делении на 2 оно даёт?

Ответ: число 0 или 1.

Шаг 1Следим за суммой всех чисел на доске. Сначала она 55 — нечётная.
Шаг 2Пусть стёрли числа 7 и 3 и написали 4. Сумма уменьшилась на 7 + 3 − 4 = 6. В общем случае она уменьшается на удвоенное меньшее число — это чётное число.
Шаг 3Значит, чётность суммы не меняется: сумма всегда нечётная.
Шаг 4В конце на доске одно число, и оно само — сумма. Значит, оно нечётное, остаток 1.

Ответ: 1.

3

В тетради 96 листов, страницы пронумерованы от 1 до 192. Вася вырвал 25 листов и сложил все 50 номеров страниц на них. Могла ли у него получиться сумма 2026?

Ответ: да или нет.

Шаг 1На каждом листе две страницы с соседними номерами: 1 и 2, 3 и 4, 57 и 58…
Шаг 2Из двух соседних чисел одно чётное, другое нечётное. Их сумма нечётная (3, 7, 115…).
Шаг 3Вася сложил 25 таких нечётных сумм. 25 — нечётное количество, значит, итог нечётный.
Шаг 42026 — чётное число, получиться оно не могло.

Ответ: нет.

4

Между цифрами 1 2 3 4 5 6 7 8 9 ставят «+» или «−» (перед единицей знака нет). Какой наименьший неотрицательный результат можно получить?

Ответ: число.

Шаг 1Если везде поставить «+», получится 1 + 2 + … + 9 = 45 — нечётное число. Если перед каким-то числом поставить «−» вместо «+», результат уменьшится на это число дважды (например, было +5, стало −5, разница 10). Это чётное изменение, и по выводу 2 чётность не меняется. Значит, результат при любых знаках нечётный.
Шаг 2Ноль получить нельзя (он чётный). Наименьшее неотрицательное нечётное число — 1.
Шаг 3Проверим, что 1 получить можно: 1 + 2 + 3 + 4 − 5 + 6 + 7 − 8 − 9 = 1.

Ответ: 1.

5

Можно ли разменять 25 рублей девятью монетами достоинством 1, 3 и 5 рублей?

Ответ: да или нет.

Шаг 1Проверим чётность: все монеты нечётные, монет 9 — нечётное количество. Сумма получится нечётной.
Шаг 225 — тоже нечётное. Чётность не мешает, значит, надо искать пример.
Шаг 3Пробуем: 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 + 1 = 25. Монет ровно 9.

Частая ошибка. решить, что раз урок про «нельзя», то ответ всегда «нельзя». Чётность помогает доказать невозможность, но если она не мешает — ищи пример.

Ответ: да.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

Произведение 22 целых чисел равно 1. Может ли их сумма равняться нулю?

Ответ: да или нет.

Шаг 1Произведение целых чисел равно 1 только если каждое из них равно 1 или −1. (Если есть число, например, 2, произведение уже не 1.)
Шаг 2Чтобы сумма была нулём, единиц и минус единиц должно быть поровну: по 11 штук.
Шаг 3Посчитаем произведение: 11 множителей −1. Нечётное количество минусов даёт минус: произведение равно −1, а не 1.
Шаг 4Противоречие.

Ответ: нет.

2

Кузнечик прыгает по прямой: первый прыжок на 1 см, второй на 2 см, третий на 3 см и так далее, каждый раз в любую сторону. За какое наименьшее число прыжков он может вернуться в исходную точку?

Ответ: число.

Шаг 11 прыжок: кузнечик на расстоянии 1 см, не вернулся.
Шаг 22 прыжка (1 и 2 см): чтобы вернуться, прыжки должны быть равны, а 1 ≠ 2. Не получится.
Шаг 33 прыжка (1, 2, 3 см): вправо на 1, вправо на 2, влево на 3. 1 + 2 = 3 — вернулся!
0123+1+2−3
Прыжки: вправо на 1, вправо на 2, влево на 3 — кузнечик снова в точке 0.

Ответ: 3.

3

На столе 11 монет гербом вверх. За ход переворачивают ровно 2 монеты. Какое наибольшее число монет может лежать гербом вниз?

Ответ: число.

Шаг 1Следим за числом монет гербом вверх. Переворачиваем 2 монеты: если обе были гербом вверх, таких монет станет на 2 меньше; если обе гербом вниз — на 2 больше; если одна так, другая иначе — число не изменится. Изменение всегда на чётное число, значит, чётность сохраняется (так же было в задаче про стаканы).
Шаг 2Сначала гербом вверх 11 монет — нечётное число. Значит, их всегда нечётное количество, то есть хотя бы 1.
Шаг 3Гербом вниз тогда не больше 11 − 1 = 10.
Шаг 4Пример на 10: пять раз переворачиваем по две новые монеты.

Ответ: 10.

Верно: 0 из 3

4

Курс «Логика и смекалка», урок 4 из 8

Кролики и клетки

Сколько носков нужно достать в темноте, чтобы точно получить пару? Почему в любой школе найдутся двое с днём рождения в один день? Все эти задачи решаются одним принципом, названным в честь математика Дирихле. Он звучит как шутка, но работает безотказно.

  • что такое принцип Дирихле и как найти в задаче «кроликов» и «клетки»
  • как рассуждать о «самом неудачном случае»
  • как применять принцип в задачах про числа и фигуры

Разминка подумай 2 минуты

?

В ящике вперемешку лежат чёрные и белые носки. В комнате темно. Какое наименьшее число носков нужно достать, чтобы среди них наверняка нашлась пара одного цвета?

Ответ: число.

Шаг 1Проверим 2 носка. Может не повезти: один чёрный, один белый. Пары нет — двух мало.
Шаг 2Возьмём 3 носка. Цветов всего два. Первые два носка могут быть разными, но третий обязательно совпадёт по цвету с одним из них.

Ответ: 3.

Главная идея

Представь: 3 кролика нужно рассадить в 2 клетки. Как ни сажай, в какой-то клетке окажутся хотя бы два кролика. Почему? Если бы в каждой клетке сидело не больше одного кролика, то в двух клетках поместилось бы не больше двух кроликов. А их три — один лишний обязательно подсядет к кому-то.

Это и есть принцип Дирихле: если кроликов больше, чем клеток, то в какой-то клетке сидят хотя бы два кролика.

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

ЗадачаКроликиКлеткиКролик попадает в клетку, если…
13 человек и дни рождения13 человек12 месяцевчеловек родился в этом месяце
носки двух цветовноски2 цветаносок этого цвета

Если нужно больше двух в одной клетке. Пусть в 5 клетках сидят 11 кроликов. Если бы в каждой клетке было не больше 2 кроликов, поместилось бы не больше 5 × 2 = 10. А кроликов 11 — значит, где-то сидят хотя бы трое. Правило: если кроликов больше, чем «клетки × 2», в какой-то клетке хотя бы трое; если больше, чем «клетки × 3», — хотя бы четверо.

Слова «наверняка» и «гарантировать» значат: при любом раскладе, даже самом неудачном. Поэтому, когда спрашивают «сколько нужно взять, чтобы наверняка…», представь, что тебе ужасно не везёт: попадаются только ненужные предметы. Посчитай, сколько предметов можно взять, так и не получив нужного, и прибавь один. Этот лишний предмет уже точно подойдёт.

План решения
  1. Определи, кто в задаче «кролики» (что распределяем), а кто «клетки» (группы, по которым распределяем). Посмотри на примеры в таблице выше.
  2. Посчитай, сколько кроликов и сколько клеток.
  3. Если нужно доказать, что где-то окажутся хотя бы двое, проверь: кроликов больше, чем клеток? Если да — доказано.
  4. Если нужно доказать, что где-то окажутся хотя бы трое, проверь: кроликов больше, чем «клетки × 2»? (Для четверых — больше, чем «клетки × 3».)
  5. Если спрашивают «сколько нужно взять, чтобы наверняка…», придумай самый неудачный расклад: какие предметы могут попадаться, пока нужного ещё нет? Посчитай их и прибавь 1.
  6. Проверь, что на 1 предмет меньше не хватит: опиши расклад, при котором нужного всё ещё нет.

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. Дни рождения

В классе 13 учеников. Докажи, что хотя бы у двоих день рождения в одном месяце.

Шаг 1Кролики — 13 учеников. Клетки — 12 месяцев. Каждый ученик «попадает» в месяц своего дня рождения.
Шаг 2Предположим, что ни в каком месяце не родились двое, то есть в каждом месяце не больше одного ученика.
Шаг 3Тогда учеников было бы не больше 12. Но их 13 — противоречие.
Шаг 4Значит, в каком-то месяце родились хотя бы двое.
янвфевмарапрмайиюниюлавгсеноктноядек
Двенадцать клеток-месяцев. Даже если в каждый месяц «сесть» по одному ученику, тринадцатому придётся попасть в уже занятый месяц.

СреднеЗадача 2. Самый неудачный случай

В ящике 10 чёрных и 10 белых носков. Сколько носков нужно достать в темноте, чтобы среди них наверняка было 2 чёрных?

Шаг 1Представим самый неудачный случай. Какие носки нам меньше всего нужны? Белые. Пусть сначала попадаются только белые — все 10 штук.
Шаг 2Белых больше нет. Значит, следующие носки обязательно чёрные. Нам нужно 2 чёрных — достаём ещё 2.
Шаг 3Всего: 10 + 2 = 12 носков.
Шаг 4Проверим, что 11 не хватит. Можно достать 10 белых и 1 чёрный — это 11 носков, а чёрный только один.
10 белых — самый неудачный случай+2 чёрных
Сначала могут попасться все 10 белых, и только потом — 2 чёрных.

Частая ошибка. ответить «3», как в разминке. Там было нужно два носка любого одинакового цвета, а здесь — два именно чёрных.

Ответ: 12.

СреднеЗадача 3. Ошибки в диктанте

В классе 30 учеников. На диктанте Ваня сделал 13 ошибок, а все остальные — меньше. Докажи, что хотя бы трое учеников сделали одинаковое число ошибок.

Шаг 1Ваню отложим в сторону. Остаются 29 учеников — это кролики.
Шаг 2Сколько ошибок могли сделать остальные? Меньше 13, то есть 0, 1, 2, …, 12. Это 13 разных вариантов — это клетки.
Шаг 3Предположим, что никакое число ошибок не встречается трижды: в каждой клетке не больше 2 учеников.
Шаг 4Тогда учеников не больше чем 13 × 2 = 26. А их 29 — противоречие.
Шаг 5Значит, в какой-то клетке хотя бы 3 ученика: трое сделали одинаковое число ошибок.

Почему не взяли Ваню? Потому что у него число ошибок (13) больше ни у кого не встречается — он точно не входит в тройку.

СложнееЗадача 4. Точки в квадрате

В квадрат со стороной 1 бросили 51 точку. Докажи, что какие-то 3 из них можно накрыть квадратиком со стороной 0,2.

Шаг 1Сначала разберёмся, что значит «накрыть квадратиком»: положить на большой квадрат маленький квадрат со стороной 0,2 так, чтобы три точки оказались под ним. Здесь клетки не даны — их нужно придумать самим. Разрежем большой квадрат на маленькие квадратики со стороной 0,2. Вдоль одной стороны поместится 1 : 0,2 = 5 квадратиков.
Шаг 2Всего квадратиков 5 × 5 = 25. Это клетки. Кролики — 51 точка.
Шаг 3Если бы в каждом квадратике было не больше 2 точек, точек было бы не больше 25 × 2 = 50. А их 51.
Шаг 4Значит, в каком-то квадратике хотя бы 3 точки. Этот квадратик и накрывает их.
Запомни

1. Кроликов больше, чем клеток, — где-то двое вместе.

2. Кроликов больше, чем «клетки × 2», — где-то хотя бы трое; больше, чем «клетки × 3», — хотя бы четверо.

3. «Сколько взять, чтобы наверняка»: самый неудачный случай + 1.

4. Клетки часто приходится придумать самому: месяцы, цвета, остатки, части фигуры.

Интересный факт

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

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

В мешке 5 красных, 7 синих и 9 зелёных шаров. Какое наименьшее число шаров нужно достать не глядя, чтобы среди них наверняка был зелёный?

Ответ: число.

Шаг 1Самый неудачный случай: попадаются все не зелёные шары — 5 красных и 7 синих, всего 12.
Шаг 2Больше не зелёных шаров нет, значит, 13-й шар точно зелёный.
Шаг 3Двенадцати не хватит: могли достаться все красные и синие.

Ответ: 13.

2

Тот же мешок: 5 красных, 7 синих, 9 зелёных. Сколько шаров нужно достать, чтобы наверняка нашлись 2 шара одного цвета?

Ответ: число.

Шаг 1Клетки — 3 цвета. Самый неудачный случай: все шары разного цвета. Так можно достать 3 шара (красный, синий, зелёный).
Шаг 2Четвёртый шар обязательно совпадёт по цвету с одним из них.

Ответ: 4.

3

В школе 400 учеников. Какое наибольшее число учеников с днём рождения в один и тот же день можно гарантировать (считаем, что в году 366 дней)?

Ответ: число.

Шаг 1Кролики — 400 учеников, клетки — 366 дней. 400 больше 366, значит, двое с общим днём рождения точно найдутся.
Шаг 2Можно ли гарантировать троих? Для этого учеников должно быть больше, чем 366 × 2 = 732. А их всего 400.
Шаг 3Значит, может случиться, что в каждый день родились не больше двух. Троих гарантировать нельзя.

Ответ: 2.

4

Из чисел 1, 2, 3, …, 20 выбирают несколько. Какое наименьшее количество нужно выбрать, чтобы среди них наверняка нашлись два числа с суммой 21?

Ответ: число.

Шаг 1Придумаем клетки: разобьём числа на пары с суммой 21. Это (1, 20), (2, 19), …, (10, 11) — всего 10 пар.
Шаг 2Самый неудачный случай: из каждой пары взяли только одно число, например 1, 2, …, 10. Это 10 чисел, и пары с суммой 21 среди них нет.
Шаг 3Одиннадцатое число попадёт в пару, из которой одно число уже взято, — и они вместе дадут 21.
1202193184175166157148139121011в каждой «клетке» числа дают в сумме 21
Десять клеток-пар. Из каждой можно взять одно число, но одиннадцатое обязательно попадёт в пару к уже взятому.

Ответ: 11.

5

Какое наименьшее количество целых чисел нужно взять, чтобы среди них наверняка нашлись два с одинаковым остатком от деления на 7?

Ответ: число.

Шаг 1При делении на 7 бывают остатки 0, 1, 2, 3, 4, 5, 6 — всего 7 вариантов. Это клетки.
Шаг 2Самый неудачный случай: 7 чисел с разными остатками, например 0, 1, 2, …, 6.
Шаг 3Восьмое число даст остаток, который уже встречался.

Ответ: 8.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

В классе 35 учеников. Какое наибольшее число k можно гарантировать: обязательно найдутся k учеников, родившихся в одном месяце?

Ответ: число.

Шаг 1Клетки — 12 месяцев. Если бы в каждом месяце родились не больше двух, учеников было бы не больше 12 × 2 = 24. А их 35 — значит, трое в одном месяце найдутся.
Шаг 2Можно ли гарантировать четверых? Если в каждом месяце не больше трёх, помещается 12 × 3 = 36 учеников. 35 меньше 36, так что может случиться, что четверых в одном месяце нет.

Ответ: 3.

2

В ящике по 10 носков красного, синего и зелёного цвета. Сколько носков нужно достать в темноте, чтобы наверняка было 3 носка одного цвета?

Ответ: число.

Шаг 1Самый неудачный случай: всех цветов поровну, но не больше двух каждого. Это 2 + 2 + 2 = 6 носков.
Шаг 2Седьмой носок станет третьим носком какого-то цвета.

Ответ: 7.

3

Из чисел 1, 2, …, 100 выбирают несколько. Какое наименьшее количество нужно выбрать, чтобы наверняка нашлись два соседних числа (отличающихся на 1)?

Ответ: число.

Шаг 1Клетки — пары соседних чисел: (1, 2), (3, 4), …, (99, 100). Их 50.
Шаг 2Самый неудачный случай: из каждой пары одно число, например все нечётные 1, 3, 5, …, 99. Это 50 чисел, и соседних среди них нет.
Шаг 3Пятьдесят первое число попадёт в пару, где одно число уже есть, и получится два соседних.

Ответ: 51.

Верно: 0 из 3

5

Курс «Логика и смекалка», урок 5 из 8

То, что не меняется

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

  • что такое инвариант и как его искать
  • как раскраска доски превращает сложную задачу в простую
  • как остатки от деления помогают в задачах на процессы

Разминка подумай 2 минуты

?

Лист бумаги разрезали на 4 части. Затем одну из частей снова разрезали на 4 части и так далее. Сколько частей будет после 10 разрезаний?

Ответ: число.

Шаг 1Посмотрим, что делает одно разрезание. Был 1 кусок, из него стало 4. Значит, частей стало на 3 больше.
Шаг 2В начале 1 часть. После 1 разрезания — 4, после 2 — 7, после 3 — 10. Каждый раз +3.
Шаг 3После 10 разрезаний: 1 + 3 × 10 = 31.

Ответ: 31.

Главная идея

Во многих задачах описан процесс — действие, которое повторяют много раз: режут лист, стирают числа и пишут новые, перекрашивают хамелеонов. Одно такое действие называют шагом. Спрашивают: можно ли в итоге получить нужный результат?

Перепробовать все варианты не получится — их слишком много. Поэтому ищут инвариант — величину, которая не меняется ни при каком шаге.

Пример из жизни. Ты перекладываешь яблоки из одной корзины в другую. Как ни перекладывай, общее число яблок не меняется — это инвариант. Если сначала было 10 яблок, в конце не может оказаться 11: такой результат недостижим.

Отсюда главное правило: если у инварианта в начале одно значение, а у нужного результата — другое, результат получить нельзя.

Остаток от деления — частый инвариант, вспомним, что это такое. Разделить 50 на 3 с остатком — значит найти, сколько раз 3 целиком помещается в 50 и что останется: 50 = 16 × 3 + 2, остаток 2. Если к числу прибавлять по 3, остаток от деления на 3 не меняется: 5 = 1 × 3 + 2, 8 = 2 × 3 + 2, 11 = 3 × 3 + 2. Ведь каждая добавленная тройка просто «укладывается» ещё раз целиком.

Что чаще всего бывает инвариантом:

ИнвариантКогда встречается
сумма всех чиселстирают два числа и пишут их сумму — сумма на доске та же
чётностькаждый шаг меняет число на 2 или не меняет (урок 3)
остаток от деления на 3, 4…каждый шаг добавляет 3 части, 4 части…
количество чёрных и белых клеток под фигурамидоминошка 1 × 2 всегда закрывает одну чёрную и одну белую клетку шахматной доски
План решения
  1. Разберись, что происходит за один шаг. Возьми конкретный пример и запиши, что было до шага и что стало после. Например: «был 1 кусок — стало 4 куска».
  2. Посмотри, что не изменилось или изменилось предсказуемо: сумма чисел, количество, чётность, остаток от деления. Проверь догадку ещё на одном-двух примерах шагов.
  3. Посчитай значение этой величины в самом начале.
  4. Посчитай, каким это значение должно быть, если нужный результат получен.
  5. Если значения разные, результат недостижим — ответ «нельзя».
  6. Если значения совпадают, инвариант не мешает. Тогда нужно показать, как именно получить результат (привести пример).

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. Разрезаем лист

Лист бумаги разрезают на 4 части, потом любую часть снова на 4 и так далее. Может ли получиться ровно 50 частей?

1 часть4 части7 частей
Каждое разрезание превращает один кусок в четыре — частей становится на 3 больше.
Шаг 1Одно разрезание добавляет 3 части. Выпишем, сколько частей бывает: 1, 4, 7, 10, 13, 16, …
Шаг 2Разделим эти числа на 3 с остатком: 1 = 0 × 3 + 1, 4 = 1 × 3 + 1, 7 = 2 × 3 + 1. Остаток всегда 1.

Почему? Мы начинаем с остатка 1 и каждый раз добавляем 3. Прибавление тройки не меняет остаток от деления на 3. Это и есть инвариант.

Шаг 3Разделим 50 на 3: 50 = 16 × 3 + 2. Остаток 2, а должен быть 1.
Шаг 4Значит, 50 частей получить нельзя.

Проверка. а 100 частей получить можно: 100 = 33 × 3 + 1, остаток 1. Нужно сделать 33 разрезания.

Ответ: нельзя.

СреднеЗадача 2. Доска без углов

У шахматной доски 8 × 8 вырезали две противоположные угловые клетки (левую нижнюю и правую верхнюю). Можно ли покрыть оставшиеся 62 клетки доминошками 1 × 2 без наложений?

Шаг 1Сначала проверим площадь: 62 клетки : 2 = 31 доминошка. По площади всё подходит, значит, нужна идея хитрее.
Шаг 2Вспомним, что доска раскрашена в шахматном порядке. Соседние клетки всегда разного цвета.
Шаг 3Доминошка закрывает две соседние клетки, значит, всегда одну тёмную и одну светлую — как её ни положи.
Шаг 4Если бы 31 доминошка покрыла доску, она закрыла бы 31 тёмную и 31 светлую клетку — поровну.
Шаг 5Посчитаем цвета. На целой доске 32 тёмных и 32 светлых клетки. Противоположные угловые клетки одного цвета (идя от угла к противоположному углу по диагонали, цвета клеток не чередуются). Вырезав их, получаем 30 клеток одного цвета и 32 другого — не поровну.
Шаг 6Противоречие: доминошки всегда закрывают цвета поровну, а на доске цветов не поровну.

Ответ: нельзя.

СложнееЗадача 3. Хамелеоны

★ Задача со звёздочкой

На острове живут 13 серых, 15 коричневых и 17 малиновых хамелеонов. Когда встречаются два хамелеона разного цвета, оба перекрашиваются в третий цвет. Могут ли когда-нибудь все хамелеоны стать одного цвета?

Пусть встретились серый и коричневый. Как изменится разность между количеством серых и коричневых? А между серыми и малиновыми? На какие числа могут меняться разности?

Шаг 1Разберёмся на примере, что происходит при одной встрече. Встретились серый и коричневый. Они оба стали малиновыми. Итог: серых стало на 1 меньше, коричневых — на 1 меньше, малиновых — на 2 больше.
Шаг 2Посчитаем количества до и после встречи. Ещё посчитаем разности — на сколько одних хамелеонов больше, чем других. В таблице «К − С» означает «коричневых минус серых», «М − К» — «малиновых минус коричневых», «М − С» — «малиновых минус серых»:
СерыеКоричневыеМалиновыеК − СМ − КМ − С
Сначала131517224
Встретились серый и коричневый121419257
Остатки от деления на 3—2 → 22 → 21 → 1
Шаг 3Разность «коричневые − серые» не изменилась (была 2, стала 2). Разности с малиновыми выросли на 3 (2 → 5, 4 → 7).

Почему? У двух цветов, которые встретились, количество уменьшилось одинаково, поэтому разность между ними та же. А малиновых стало на 2 больше, тогда как серых (или коричневых) — на 1 меньше. Разница между ними выросла на 2 + 1 = 3.

Шаг 4Итак, при любой встрече каждая разность либо не меняется, либо меняется на 3. Вспомним «Главную идею»: если число меняется на 3, его остаток от деления на 3 остаётся тем же (в таблице: 2 → 5 — остаток 2 и 2; 4 → 7 — остаток 1 и 1). Значит, остатки разностей — наш инвариант.
Шаг 5Что должно быть в конце? Если все хамелеоны одного цвета, два других цвета исчезли: их по 0. Разность между ними 0 − 0 = 0, а 0 делится на 3 (остаток 0).
Шаг 6Сейчас разности 2, 2 и 4. Их остатки от деления на 3: 2, 2 и 1. Остатка 0 нет ни у одной, и появиться он не может.

Ответ: не могут.

Запомни

1. Видишь процесс «можно ли получить» — ищи инвариант: сумму, чётность, остаток.

2. Если инвариант в начале и в конце разный — получить нельзя.

3. В задачах о доске и фигурах попробуй раскраску: сколько клеток каждого цвета закрывает одна фигура.

4. Если инвариант не мешает, это ещё не значит «можно» — нужен пример.

Интересный факт

В знаменитой игре «Пятнашки» ровно половина расстановок фишек нерешаема. В 1880-х годах предлагали большие призы тому, кто соберёт позицию с переставленными фишками 14 и 15. Никто не выиграл: математики доказали с помощью инварианта (чётности перестановки), что это невозможно.

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

Лист разрезают на 5 частей, потом любую из частей снова на 5 и так далее. Сколько частей будет после 7 разрезаний?

Ответ: число.

Шаг 1Одно разрезание: из 1 куска стало 5, то есть частей стало на 4 больше.
Шаг 2В начале 1 часть, после 7 разрезаний: 1 + 4 × 7 = 29.

Ответ: 29.

2

В том же процессе (каждый раз кусок режут на 5 частей) может ли получиться ровно 2026 частей?

Ответ: да или нет.

Шаг 1Число частей: 1, 5, 9, 13, … — каждый раз +4. При делении на 4 все они дают остаток 1.
Шаг 2Разделим 2026 на 4: 2026 = 506 × 4 + 2. Остаток 2, а должен быть 1.

Ответ: нет.

3

У доски 6 × 6 вырезали две угловые клетки на одной диагонали. Какое наибольшее число доминошек 1 × 2 можно разместить на оставшихся клетках без наложений?

Ответ: число.

Шаг 1На доске 6 × 6 всего 36 клеток: 18 тёмных и 18 светлых.
Шаг 2Угловые клетки на одной диагонали — одного цвета. Вырезали две клетки одного цвета: этого цвета осталось 16, другого — 18.
Шаг 3Каждая доминошка закрывает одну тёмную и одну светлую клетку. Клеток одного цвета всего 16, значит, доминошек не больше 16.
Шаг 416 доминошек разместить действительно можно.
Вырезаны две клетки одного цвета: тёмных осталось 16, светлых 18. Жёлтая доминошка закрывает одну тёмную и одну светлую клетку.

Ответ: 16.

4

На доске написаны числа 1, 2, 3, …, 10. За ход стирают любые два числа и записывают их сумму. В конце осталось одно число. Какое?

Ответ: число.

Шаг 1Что происходит за ход: например, стёрли 3 и 7, написали 10. Сумма всех чисел на доске не изменилась. Это инвариант.
Шаг 2В начале сумма 1 + 2 + … + 10 = 55.
Шаг 3В конце на доске одно число, и оно равно сумме, то есть 55.

Ответ: 55.

5

На доске числа 1, 2, 3, …, 10. За ход стирают два числа a и b и записывают число a + b − 1. Какое число останется в конце?

Ответ: число.

Шаг 1Пример хода: стёрли 3 и 7, написали 3 + 7 − 1 = 9. Сумма всех чисел уменьшилась на 1.
Шаг 2Так происходит при каждом ходе: сумма уменьшается ровно на 1.
Шаг 3Сколько будет ходов? Каждый ход уменьшает количество чисел на 1 (два стёрли, одно написали). Было 10 чисел, осталось 1 — значит, ходов 9.
Шаг 4В начале сумма 55, после 9 ходов: 55 − 9 = 46.

Ответ: 46.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

★ Задача со звёздочкой

На доске записаны числа 1, 2, 3, 4, 5, 6, 7. За ход можно к любым двум числам прибавить по 1. Какое наименьшее число может получиться, если сделать все семь чисел равными?

Числа только увеличиваются, значит, общее значение не меньше 7. Теперь посмотри на сумму всех чисел: на сколько она растёт за ход и может ли она стать нечётной?

Ответ: число.

Шаг 1Числа только растут. Число 7 уменьшить нельзя, значит, общее значение не меньше 7.
Шаг 2Посмотрим на сумму. В начале 1 + 2 + … + 7 = 28 — чётная. Каждый ход добавляет 1 + 1 = 2, значит, сумма всегда остаётся чётной.
Шаг 3Проверим 7: если все семь чисел равны 7, сумма 7 × 7 = 49 — нечётная. Не подходит.
Шаг 4Проверим 8: сумма 7 × 8 = 56 — чётная, подходит. Нужно прибавить к числам 1, 2, 3, 4, 5, 6, 7 соответственно 7, 6, 5, 4, 3, 2, 1.
Шаг 5Покажем, как это сделать. Ходы: к паре (1, 2) — 6 раз, к паре (1, 3) — 1 раз, к паре (3, 4) — 4 раза, к паре (5, 6) — 2 раза, к паре (5, 7) — 1 раз.

Проверка. число 1 получило 6 + 1 = 7 ✓, число 2 — 6 ✓, число 3 — 1 + 4 = 5 ✓, число 4 — 4 ✓, число 5 — 2 + 1 = 3 ✓, число 6 — 2 ✓, число 7 — 1 ✓. Все стали равны 8.

Ответ: 8.

2

★ Задача со звёздочкой

На острове 7 серых, 8 коричневых и 9 малиновых хамелеонов (правила как в разборе: встретились двое разного цвета — оба стали третьего). Могут ли все хамелеоны стать одного цвета?

Действуй как в разборе про хамелеонов: найди разности между количествами и посмотри на их остатки от деления на 3.

Ответ: да или нет.

Шаг 1Вспомним разбор задачи 3. При встрече двух хамелеонов разность между количествами этих двух цветов не меняется, а разность каждого из них с третьим цветом меняется на 3. Если число меняется на 3, его остаток от деления на 3 остаётся прежним. Значит, остатки всех разностей не меняются.
Шаг 2Найдём разности: 8 − 7 = 1, 9 − 8 = 1, 9 − 7 = 2. Остатки от деления на 3: 1, 1, 2.
Шаг 3Чтобы все стали одного цвета, одна из разностей должна стать 0 (остаток 0). Но остатка 0 нет и появиться он не может.

Ответ: нет.

3

Лист режут на части: каждый раз один кусок разрезают либо на 4, либо на 7 частей. Какое из чисел — 2024, 2025 или 2026 — может получиться?

Ответ: одно из трёх чисел.

Шаг 1Разрезание на 4 части добавляет 3 части, на 7 частей — 6 частей. И 3, и 6 делятся на 3.
Шаг 2Значит, остаток от деления числа частей на 3 не меняется. В начале 1 часть — остаток 1.
Шаг 3Проверим числа: 2024 = 674 × 3 + 2 (остаток 2); 2025 = 675 × 3 (остаток 0); 2026 = 675 × 3 + 1 (остаток 1).
Шаг 4Подходит только 2026. Получить его можно, сделав 675 разрезаний на 4 части.

Ответ: 2026.

Верно: 0 из 3

6

Курс «Логика и смекалка», урок 6 из 8

Весы и вёдра

Среди монет затесалась фальшивка, а у тебя только чашечные весы без гирь. Или есть вёдра на 3 и 5 литров, а нужно ровно 4. Такие задачи учат планировать: думать на несколько шагов вперёд и выжимать максимум из каждого действия.

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

Разминка подумай 2 минуты

?

Есть 3 одинаковые на вид монеты, одна из них фальшивая и легче настоящих. Какое наименьшее число взвешиваний на чашечных весах без гирь нужно, чтобы наверняка её найти?

Ответ: число.

Шаг 1Кладём одну монету на левую чашу, одну — на правую, третью оставляем на столе.
Шаг 2Если одна чаша поднялась выше, на ней лежит лёгкая, то есть фальшивая монета.
Шаг 3Если весы в равновесии, на чашах настоящие монеты, а фальшивая — та, что на столе.
Шаг 4В любом случае мы нашли фальшивую монету за одно взвешивание.

Ответ: 1.

Главная идея

В этом уроке три вида задач: взвешивания монет, переливания воды и взвешивания гирями. Разберём каждый по порядку.

1. Взвешивания: поиск фальшивой монеты

Чашечные весы — это коромысло с двумя чашами. Гирь у нас нет, поэтому узнать точную массу нельзя, но можно сравнить, какая чаша тяжелее: тяжёлая чаша опускается, лёгкая поднимается. Если массы равны, весы стоят ровно (равновесие).

Все настоящие монеты весят одинаково. Фальшивая монета в наших задачах легче настоящих. Значит, чаша, на которой она лежит, поднимется.

Кладём на чаши одинаковое число монет. У взвешивания бывает ровно три результата:

Что показали весыГде фальшивая монета
левая чаша подняласьна левой чаше
правая чаша подняласьна правой чаше
равновесиена чашах только настоящие монеты, значит, фальшивая среди тех, что остались на столе

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

Сколько взвешиванийСреди скольких монет наверняка найдём лёгкую фальшивую
13
23 × 3 = 9
33 × 3 × 3 = 27
43 × 3 × 3 × 3 = 81

2. Переливания воды

У нас есть вёдра известного объёма (например, на 3 и на 5 литров), но на них нет делений. Поэтому точно знать, сколько в ведре воды, можно только в таких случаях: ведро пустое, ведро полное или вода получена переливанием «до конца». Разрешены три действия:

Наполнить ведро из крана доверху.
Вылить из ведра всю воду.
Перелить воду из одного ведра в другое — до тех пор, пока первое ведро не опустеет или второе не наполнится доверху.

Пример переливания: в 5-литровом ведре 5 литров, 3-литровое пустое. Переливаем из большого в маленькое. В маленькое влезает только 3 литра, и оно наполняется доверху. В большом остаётся 5 − 3 = 2 литра. Так мы отмерили 2 литра, хотя делений на ведре нет.

Чтобы не запутаться, после каждого действия записываем, сколько литров стало в каждом ведре. Получается таблица: в первом столбце — что сделали, в остальных — сколько воды в каждом ведре после этого действия. Вот первые строки для вёдер на 5 и 3 литра:

Что сделалиВ ведре 5 лВ ведре 3 л
в начале00
наполнили 5-литровое из крана50
перелили из 5-литрового в 3-литровое23

Полная таблица к такой задаче разобрана в задаче 2.

3. Гири

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

Гири на одной чаше с грузом нет. Тогда масса груза равна сумме гирь на другой чаше. Например, гири 2 г и 5 г вместе уравновешивают груз 7 г.

Гири можно класть на обе чаши. Часть гирь кладут к грузу. Тогда масса груза равна «гири на другой чаше минус гири рядом с грузом». Например: на одной чаше гиря 5 г, на другой — груз и гиря 2 г. Равновесие значит: груз + 2 = 5, груз = 3 г. Так двумя гирями 2 г и 5 г взвешивают 3 г. Подробнее — в задаче 3.

План решения
  1. Задачи на взвешивание монет. Раздели монеты на три кучки, как можно более равные. Две кучки с одинаковым числом монет положи на чаши, третью оставь на столе.
  2. Разбери три результата по таблице из «Главной идеи»: поднялась левая чаша, поднялась правая, равновесие. В каждом случае определи, в какой кучке фальшивка.
  3. Повтори то же самое с кучкой, где осталась фальшивка, пока в ней не останется одна монета. Число повторений — это число взвешиваний.
  4. Чтобы понять, хватит ли взвешиваний, сравни число монет с таблицей: 3, 9, 27, 81…
  5. Задачи на переливание. Нарисуй таблицу: первый столбец «Что сделали», затем по столбцу на каждое ведро. Первая строка — «в начале».
  6. Подумай, какое количество нужно получить, и попробуй записать его как разность объёмов вёдер: например, 2 = 5 − 3, 4 = 5 − 1. Это подсказывает, какое переливание сделать.
  7. Выполняй действия по одному (наполнить, вылить, перелить до конца) и после каждого записывай в таблицу, сколько литров в каждом ведре. Остановись, когда в каком-то ведре окажется нужное количество.
  8. Задачи на гири. Выпиши все способы положить гири: только на одну чашу (масса = сумма гирь) и на обе чаши (масса = гири на одной чаше минус гири рядом с грузом). Проверь, какие массы получаются.

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. 9 монет

Среди 9 монет одна фальшивая, она легче. Как найти её за 2 взвешивания?

Шаг 1Взвешивание 1. Делим 9 монет на три кучки по 3 монеты. Две кучки кладём на весы, третью оставляем на столе.
Шаг 2Смотрим на результат. Если одна чаша легче, фальшивая монета в её кучке. Если равновесие — в кучке на столе. В любом случае теперь подозреваемых только 3 монеты.
Шаг 3Взвешивание 2. Из этих трёх монет кладём по одной на каждую чашу, третью оставляем. Дальше как в разминке: лёгкая чаша — там фальшивая, равновесие — фальшивая на столе.
9 монет1-е взвешивание3332-е взвешивание111
Две кучки на весы, одна на стол. Жёлтым — кучка, в которой оказалась фальшивая монета.

СреднеЗадача 2. Отмерить 4 литра

Есть два ведра: на 3 литра и на 5 литров, и кран с водой. Воду можно наливать из крана, выливать и переливать из ведра в ведро. Как набрать ровно 4 литра?

С чего начать. Нам нужно 4 литра. Заметим, что 4 = 5 − 1: если из полного 5-литрового ведра отлить ровно 1 литр, останется 4. Как отлить ровно 1 литр? Если в 3-литровом ведре уже есть 2 литра, то свободного места в нём 3 − 2 = 1 литр. Перельём в него воду из полного большого ведра — туда уйдёт ровно 1 литр. Остаётся понять, как получить 2 литра: 2 = 5 − 3, это переливание из полного большого ведра в пустое маленькое.

Теперь выполним действия и после каждого запишем, сколько воды в вёдрах:

ДействиеВедро 5 лВедро 3 лПояснение
Наполнили 5-литровое50набрали из крана
Перелили из 5 в 323в 3-литровое влезло 3 л, в большом осталось 5 − 3 = 2
Вылили 3-литровое20освободили маленькое ведро
Перелили 2 л в 3-литровое02теперь в маленьком 2 л, в нём есть место для 1 л
Наполнили 5-литровое52снова набрали из крана
Долили 3-литровое доверху43в маленькое влез только 1 л, в большом осталось 5 − 1 = 4

Ответ: в большом ведре ровно 4 литра, на это ушло 6 действий.

СреднеЗадача 3. Гири на обеих чашах

Есть две гири: 2 г и 5 г. Гири можно класть на любую чашу весов, в том числе на ту же, где лежит груз. Грузы какой массы можно взвесить?

Шаг 1Разберёмся с правилом. Груз всегда лежит на левой чаше. Гири можно положить на правую чашу или на левую рядом с грузом. Весы в равновесии, когда слева и справа одинаковая масса.
Шаг 2Одна гиря справа. Гиря 2 г — груз 2 г. Гиря 5 г — груз 5 г.
Шаг 3Обе гири справа. Справа 2 + 5 = 7 г, значит, груз 7 г.
Шаг 4Гиря 5 г справа, гиря 2 г слева рядом с грузом. Слева: груз + 2 г, справа: 5 г. Равновесие значит груз + 2 = 5, откуда груз = 5 − 2 = 3 г.

Почему? Гиря рядом с грузом как бы «помогает» ему, поэтому самому грузу нужно на 2 г меньше, чем стоит справа.

Шаг 5Гиря 2 г справа, гиря 5 г слева. Груз + 5 = 2 — так не бывает: слева уже больше, чем справа. Этот вариант не подходит.
Слева (с грузом)СправаМасса груза
—2 г2 г
—5 г5 г
—2 г + 5 г7 г
2 г5 г5 − 2 = 3 г

Ответ: можно взвесить 2, 3, 5 и 7 г — четыре разные массы.

СложнееЗадача 4. Сколько взвешиваний нужно всегда

Среди 30 монет одна фальшивая, она легче. Какое наименьшее число взвешиваний гарантированно позволит её найти?

Шаг 1Сначала поймём, почему 3 взвешиваний может не хватить. При каждом взвешивании монеты делятся на три части: левая чаша, правая чаша, стол. Фальшивка окажется в одной из этих частей, и мы не знаем заранее, в какой. Нужно рассчитывать на неудачный случай: фальшивка попадёт в самую большую часть. А самая большая из трёх частей не может быть меньше трети всех монет (если бы все три части были меньше трети, вместе они не набрали бы все монеты).
Шаг 230 монет на три кучки: самая большая хотя бы 10 монет. После второго взвешивания: 10 монет на три кучки, самая большая хотя бы 4. После третьего: 4 монеты на три кучки, самая большая хотя бы 2. Две подозреваемые монеты — ещё не ответ.

Коротко: за 3 взвешивания можно разобраться не больше чем с 3 × 3 × 3 = 27 монетами, а у нас 30.

Шаг 3Теперь покажем, что 4 хватит. 1-е взвешивание: 10 и 10 на весы, 10 на столе → остаётся 10 подозреваемых.
Шаг 42-е: делим 10 на 3, 3 и 4. На весы кладём две кучки по 3 → остаётся 3 или 4 монеты.
Шаг 53-е: если осталось 4 монеты, кладём по 1 на чаши, 2 на стол → остаётся 1 или 2 монеты. (Если осталось 3, фальшивку находим сразу, как в разминке.)
Шаг 64-е: если осталось 2 монеты, кладём их на разные чаши — лёгкая и есть фальшивая.
30 монет1-е взвешивание1010102-е взвешивание3343-е взвешивание1124-е взвешивание11
Жёлтым отмечена кучка, где может оказаться фальшивая монета в самом неудачном случае. После каждого взвешивания подозреваемых остаётся не больше: 10, потом 4, потом 2.

Ответ: 4.

Запомни

1. У весов три исхода — дели на три группы.

2. За n взвешиваний лёгкую фальшивку можно найти среди 3 × 3 × … × 3 (n раз) монет, но не больше.

3. В переливаниях веди таблицу состояний и ищи нужный объём как разность.

4. Если объёмы вёдер оба чётные, нечётное количество воды отмерить нельзя — снова чётность.

Интересный факт

Задача о переливании воды попала в фильм «Крепкий орешек 3»: героям нужно было отмерить 4 галлона с помощью канистр на 3 и 5 галлонов, иначе взорвётся бомба. Решение — ровно то, что ты только что разобрал.

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

Среди 81 монеты одна фальшивая, она легче. Какое наименьшее число взвешиваний гарантированно позволяет её найти?

Ответ: число.

Шаг 1Каждый раз делим на три равные кучки: 81 → 27 → 9 → 3 → 1. Это 4 взвешивания.
Шаг 2Трёх не хватит: за 3 взвешивания можно разобраться только с 27 монетами, а у нас 81.

Ответ: 4.

2

Среди 10 монет одна фальшивая, она легче. Какое наименьшее число взвешиваний гарантированно позволяет её найти?

Ответ: число.

Шаг 1За 2 взвешивания можно найти фальшивку максимум среди 9 монет, а у нас 10. Значит, нужно хотя бы 3.
Шаг 2Покажем, что 3 хватит. 1-е: на весы по 3 монеты, на столе 4. Остаётся 3 или 4 подозреваемые.
Шаг 32-е и 3-е: если осталось 3 — хватит одного взвешивания; если 4 — кладём по 1 на чаши, 2 на стол, и последним взвешиванием сравниваем оставшиеся две.

Ответ: 3.

3

Есть вёдра на 4 и 6 литров и кран. Какой из объёмов — 1, 2, 3 или 5 литров — можно отмерить?

Ответ: число.

Шаг 1Наливаем из крана только полные вёдра: 4 или 6 литров — чётные числа.
Шаг 2Когда переливаем и выливаем, количество воды в вёдрах получается сложением и вычитанием чётных чисел, а такие суммы и разности всегда чётные. Значит, в вёдрах всегда чётное число литров.
Шаг 3Нечётные 1, 3, 5 получить нельзя. А 2 литра можно: наполнить 6-литровое, перелить в 4-литровое, в большом останется 6 − 4 = 2.

Ответ: 2.

4

Есть гири 1 г, 2 г, 4 г и 8 г. Гири кладут только на одну чашу. Какая наибольшая масса, если нужно взвешивать все целые массы от 1 г до неё?

Ответ: число (граммы).

Шаг 1Больше, чем все гири вместе, взвесить нельзя: 1 + 2 + 4 + 8 = 15 г.
Шаг 2Проверим, что любую массу от 1 до 15 можно собрать. Например: 3 = 2 + 1, 5 = 4 + 1, 6 = 4 + 2, 7 = 4 + 2 + 1, 11 = 8 + 2 + 1, 13 = 8 + 4 + 1, 14 = 8 + 4 + 2.
Шаг 3Так получается каждое число от 1 до 15.

Ответ: 15.

5

Есть гири 1 г и 3 г, их можно класть на обе чаши весов. Сколько разных целых масс можно взвесить?

Ответ: число.

Шаг 1Гиря 1 г — масса 1 г.
Шаг 2Гиря 3 г — масса 3 г.
Шаг 3Обе гири на одну чашу — 4 г.
Шаг 4Хитрый случай: гирю 3 г кладём на одну чашу, а груз и гирю 1 г — на другую. Весы в равновесии, если груз + 1 = 3, то есть груз 2 г.
3 ггруз1 ггруз + 1 г = 3 г, значит, груз = 2 г
Гиря 1 г лежит на одной чаше с грузом.

Итого массы 1, 2, 3, 4 г.

Ответ: 4.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

★ Задача со звёздочкой

Восьмилитровое ведро полно воды, а вёдра на 5 и 3 литра пустые. Воду можно только переливать из ведра в ведро (выливать и доливать из крана нельзя). За какое наименьшее число переливаний можно разделить воду поровну: 4 литра и 4 литра?

Веди таблицу состояний «8 л / 5 л / 3 л». Начни с переливания из 8-литрового ведра в 5-литровое и не возвращайся к уже встречавшимся состояниям.

Ответ: число.

Переливаем всегда «до конца»: пока одно ведро не опустеет или другое не наполнится — иначе мы не знаем, сколько перелили.

ШагЧто делаем8 л5 л3 л
—начало800
1из 8 в 5350
2из 5 в 3323
3из 3 в 8620
4из 5 в 3602
5из 8 в 5152
6из 5 в 3 (влез 1 л)143
7из 3 в 8440

После 7 переливаний в 8-литровом и 5-литровом вёдрах по 4 литра. Компьютерный перебор всех вариантов подтверждает, что быстрее не получится.

Ответ: 7.

2

Среди 243 монет одна фальшивая, она легче. Какое наименьшее число взвешиваний гарантированно позволяет её найти?

Ответ: число.

Шаг 1Посчитаем, сколько раз 243 делится на 3: 243 → 81 → 27 → 9 → 3 → 1. Пять делений.
Шаг 2Каждое деление — одно взвешивание (две кучки на весы, одна на столе). Итого 5 взвешиваний.
Шаг 3Четырёх не хватит: за 4 взвешивания можно разобраться только с 81 монетой.

Ответ: 5.

3

Есть гири 1 г, 3 г и 9 г, их можно класть на обе чаши. Какая наибольшая масса, если нужно взвешивать все целые массы от 1 г до неё?

Ответ: число (граммы).

Шаг 1Больше, чем все гири вместе, взвесить нельзя: 1 + 3 + 9 = 13 г.
Шаг 2Проверим, что все массы от 1 до 13 получаются. Запись «9 − 3 − 1» значит: гиря 9 г на одной чаше, а груз вместе с гирями 3 г и 1 г — на другой.
МассаКак взвесить
11
23 − 1
33
43 + 1
59 − 3 − 1
69 − 3
79 + 1 − 3
89 − 1
99
109 + 1
119 + 3 − 1
129 + 3
139 + 3 + 1

Ответ: 13.

Верно: 0 из 3

7

Курс «Логика и смекалка», урок 7 из 8

Точки и линии

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

  • что такое граф, вершина и степень вершины
  • почему вершин нечётной степени всегда чётное число
  • как понять, можно ли нарисовать фигуру одним росчерком

Разминка подумай 2 минуты

?

Встретились 5 друзей, и каждый пожал руку каждому. Сколько было рукопожатий?

Ответ: число.

Шаг 1Каждый из 5 друзей пожал руки остальным 4. Если сложить, получится 5 × 4 = 20.
Шаг 2Но рукопожатие Ани с Борей — это то же самое рукопожатие, что Бори с Аней. Мы посчитали его два раза: и у Ани, и у Бори.
Шаг 3Значит, на самом деле рукопожатий вдвое меньше: 202 = 10.
12345
Друзья — вершины, рукопожатия — рёбра. Из каждой вершины выходит 4 ребра, а всего рёбер 10.

Ответ: 10.

Главная идея

Граф — это рисунок из точек и линий. Точки называют вершинами, линии между ними — рёбрами. Граф рисуют, чтобы наглядно показать, кто с кем или что с чем связано. Как нарисованы точки и какой формы линии — неважно; важно только, какие вершины соединены.

ЗадачаВершины (точки)Рёбра (линии)
рукопожатиялюдирукопожатие между двумя людьми
дорогигородадорога между двумя городами
турниркомандыматч между двумя командами

Степень вершины — это число рёбер, которые выходят из вершины. Например, если Аня пожала руки троим, то из точки «Аня» выходят 3 линии, и степень этой вершины равна 3. На рисунке ниже красные числа — степени вершин.

A3B3C2D3E1
Граф: 5 вершин и 6 рёбер. Красные числа — степени вершин. Их сумма 3 + 3 + 2 + 3 + 1 = 12 — ровно вдвое больше числа рёбер.

Главный факт.Сумма степеней всех вершин равна удвоенному числу рёбер. Почему? У каждого ребра два конца. Когда мы считаем степени, каждое ребро засчитывается один раз у одного своего конца и ещё раз у другого. На рисунке выше: 6 рёбер, а сумма степеней 3 + 3 + 2 + 3 + 1 = 12 = 6 × 2.

Следствие. Удвоенное число всегда чётное, поэтому сумма степеней всегда чётная. Если в задаче сумма степеней получилась нечётной — такого графа не бывает.

«Каждый с каждым». Пусть 5 команд и каждая сыграла с каждой. Из каждой вершины выходят рёбра ко всем остальным 4 вершинам, степень каждой 4. Сумма степеней 5 × 4 = 20, рёбер вдвое меньше: 10. Правило: число рёбер = (число вершин) × (число вершин − 1) : 2.

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

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

Сколько нечётных вершинМожно ли одним росчерком
0можно, начинать с любой вершины
2можно, но начинать нужно в одной нечётной вершине, а закончится рисунок в другой
4нельзя; нужно 2 росчерка (у каждого росчерка два конца — начало и конец)
6нельзя; нужно 3 росчерка
План решения
  1. Реши, что будет вершинами (люди, города, команды), а что рёбрами (рукопожатия, дороги, матчи). Если вершин немного, нарисуй граф.
  2. Посчитай степень каждой вершины: сколько рёбер из неё выходит.
  3. Нужно найти число рёбер? Сложи степени всех вершин и раздели сумму на 2.
  4. Спрашивают «может ли быть так»? Посчитай сумму степеней. Если она нечётная — так быть не может.
  5. Все соединены со всеми? Число рёбер = (число вершин) × (число вершин − 1) : 2.
  6. Спрашивают, можно ли нарисовать одним росчерком или пройти по всем дорогам по одному разу? Посчитай нечётные вершины и посмотри в таблицу выше.

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. Турнир

В турнире 6 команд, каждая сыграла с каждой по одному разу. Сколько было матчей?

Шаг 1Вершины — 6 команд, рёбра — матчи. Каждая команда сыграла со всеми остальными 5 командами, значит, степень каждой вершины 5.
Шаг 2Сумма степеней: 6 × 5 = 30.
Шаг 3Каждый матч посчитан дважды (у обеих команд), поэтому матчей 302 = 15.
123456
Каждая из 6 вершин соединена с 5 другими. Всего рёбер-матчей 15.

Проверка. можно пересчитать по порядку: команда 1 сыграла 5 новых матчей, команда 2 — ещё 4 новых (с первой уже посчитали), команда 3 — 3, затем 2, 1 и 0. Итого 5 + 4 + 3 + 2 + 1 = 15.

Ответ: 15 матчей.

СреднеЗадача 2. Дороги в стране

В стране 7 городов. Может ли быть так, что из каждого города выходит ровно 3 дороги в другие города?

Шаг 1Вершины — 7 городов, рёбра — дороги. Степень каждой вершины 3.
Шаг 2Сумма степеней: 7 × 3 = 21.
Шаг 3Сумма степеней должна быть равна удвоенному числу дорог, то есть должна быть чётной. А 21 — нечётное число.
Шаг 4Противоречие. Значит, так быть не может.

Узнаёшь? Это та же чётность из урока 3. Для сравнения — вот 6 городов, где из каждого выходит 3 дороги. Здесь сумма степеней 6 × 3 = 18, чётная, и всё получается.

Для сравнения: с 6 городами так можно. Сумма степеней 6 × 3 = 18, дорог 9.

Ответ: не может.

СреднеЗадача 3. Кёнигсбергские мосты

В городе Кёнигсберге (сейчас Калининград) было 7 мостов, соединяющих берега реки и два острова. Можно ли прогуляться, пройдя по каждому мосту ровно один раз?

Шаг 1Превратим карту в граф. Посмотри на рисунок: A — верхний берег, B — нижний берег, C и D — острова. Каждый участок суши станет вершиной, каждый мост — ребром между участками, которые он соединяет. Получаем 4 вершины и 7 рёбер.
Шаг 2Посчитаем степени: A — 3 моста, B — 3, C — 5, D — 3.
Шаг 3Теперь главное рассуждение. Пусть мы идём по маршруту и проходим через какой-то участок суши (не начинаем и не заканчиваем в нём). Мы пришли туда по одному мосту и ушли по другому. Каждый визит использует два моста.

Почему? Значит, у участка, через который мы только проходим, мосты разбиваются на пары «пришёл — ушёл», и их чётное число. Нечётное число мостов может быть только у участков, где маршрут начинается или заканчивается.

Шаг 4Начало и конец — это не больше двух вершин. Значит, в графе, который можно обойти, нечётных вершин не больше двух.
Шаг 5У Кёнигсберга нечётных вершин четыре (3, 3, 5, 3). Прогулка невозможна.
A3C5D3B3
Граф Кёнигсберга. Красные числа — степени вершин: 3, 5, 3, 3. Все четыре нечётные, а для прогулки нечётных может быть не больше двух.

Эту задачу в 1736 году решил великий математик Леонард Эйлер. С неё и началась теория графов.

Ответ: нельзя.

СложнееЗадача 4. Открытый конверт

Можно ли нарисовать «открытый конверт» (домик: квадрат с двумя диагоналями и крышей-треугольником сверху), не отрывая карандаш и не проводя дважды одну линию?

Шаг 1Отметим все вершины: верх крыши, два верхних угла квадрата, центр (где пересекаются диагонали) и два нижних угла.
Шаг 2Посчитаем, сколько линий выходит из каждой вершины:
ВершинаКакие линииСтепень
верх крыши2 ската крыши2
верхний уголскат крыши, верхняя сторона, боковая сторона, диагональ4
центр4 половинки диагоналей4
нижний уголнижняя сторона, боковая сторона, диагональ3
Шаг 3Нечётная степень только у двух нижних углов. По правилу из задачи 3 рисунок одним росчерком возможен.

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

Шаг 4Вот один из возможных маршрутов — проводи линии в порядке номеров:
12345678910стартфиниш
Один из возможных маршрутов: проводим линии в порядке номеров от 1 до 10, начиная в левом нижнем углу и заканчивая в правом нижнем.

Ответ: можно, если начать в нижнем углу.

Запомни

1. Сумма степеней = 2 × число рёбер, поэтому вершин нечётной степени чётное число.

2. Если все вершины соединены со всеми, рёбер (число вершин) × (число вершин − 1) : 2.

3. Фигуру можно нарисовать одним росчерком, если нечётных вершин 0 (начинай откуда угодно) или 2 (начинай в нечётной).

4. Если нечётных вершин 4, понадобится 2 росчерка; если 6 — 3 росчерка, и так далее.

Интересный факт

Навигатор в телефоне ищет путь именно по графу: перекрёстки — вершины, улицы — рёбра с длинами. А соцсети изучают граф знакомств, где миллиарды вершин. В нём в среднем любые два человека связаны цепочкой всего из нескольких знакомых.

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

В турнире 10 команд, каждая сыграла с каждой по одному разу. Сколько было матчей?

Ответ: число.

Шаг 1Каждая из 10 команд сыграла с 9 остальными: степень каждой вершины 9.
Шаг 2Сумма степеней: 10 × 9 = 90.
Шаг 3Каждый матч посчитан дважды, поэтому матчей 902 = 45.

Ответ: 45.

2

В графе 6 вершин, их степени: 1, 2, 2, 3, 3, 5. Сколько в нём рёбер?

Ответ: число.

Шаг 1Сложим степени: 1 + 2 + 2 + 3 + 3 + 5 = 16.
Шаг 2Сумма степеней равна удвоенному числу рёбер, значит, рёбер 162 = 8.
53а3б2а2б1
Пример такого графа. Число в вершине — её степень (буквы «а» и «б» различают вершины с одинаковой степенью). Рёбер 8.

Ответ: 8.

3

В классе 15 учеников. Может ли каждый дружить ровно с тремя одноклассниками?

Ответ: да или нет.

Шаг 1Вершины — ученики, рёбра — дружбы. Степень каждой вершины 3.
Шаг 2Сумма степеней: 15 × 3 = 45 — нечётное число.
Шаг 3А сумма степеней всегда чётная. Противоречие.

Ответ: нет.

4

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

Пример такого рисунка: у четырёх углов степень 3 (красные), у центра — 4.

Ответ: число.

Шаг 1Вспомним «Главную идею». Через вершину, где рисунок только проходит, идёт чётное число линий. Поэтому каждая нечётная вершина обязательно будет началом или концом какого-то росчерка. У одного росчерка всего два конца — начало и конец.
Шаг 2Нечётных вершин 4, а один росчерк «обслуживает» только 2 из них. Значит, росчерков нужно хотя бы 4 : 2 = 2, и двух хватает (как это сделать, смотри в проверке ниже).
Шаг 3Между двумя росчерками карандаш отрывают один раз.

Проверка. вот как нарисовать квадрат с диагоналями за 2 росчерка. Первый: левый верхний угол → правый верхний → правый нижний → левый нижний → левый верхний → центр → правый нижний. Второй: правый верхний угол → центр → левый нижний.

Ответ: 1.

5

В компании каждый знаком ровно с 4 другими, а всего пар знакомых 30. Сколько человек в компании?

Ответ: число.

Шаг 1Сумма степеней = 2 × число рёбер = 2 × 30 = 60.
Шаг 2У каждого человека степень 4. Значит, людей 60 : 4 = 15.

Ответ: 15.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

В Кёнигсберге решили построить новые мосты. Какое наименьшее число мостов нужно добавить, чтобы по всем мостам можно было пройти ровно по одному разу (начало и конец могут быть в разных местах)?

Ответ: число.

Шаг 1Сейчас нечётных вершин 4: A (3), B (3), C (5), D (3). Для прогулки их должно быть не больше 2.
Шаг 2Новый мост добавляет по 1 к степени двух вершин. Построим мост между A и B: у A станет 4, у B станет 4 — обе чётные.
Шаг 3Теперь нечётные только C (5) и D (3) — ровно две. Прогулка возможна: начинаем в C, заканчиваем в D (или наоборот).
Шаг 4Без новых мостов нельзя (это разобрали в задаче 3), значит, достаточно одного.

Ответ: 1.

2

Сколько диагоналей у выпуклого десятиугольника? (Диагональ — отрезок, соединяющий две вершины, которые не являются соседними.)

Ответ: число.

Шаг 1Из одной вершины десятиугольника можно провести отрезки к 9 другим вершинам. Две из них соседние — к ним идут стороны. Остаётся 7 диагоналей.
Шаг 2Вершин 10, из каждой 7 диагоналей: 10 × 7 = 70.
Шаг 3Каждая диагональ соединяет две вершины и посчитана дважды. Диагоналей 702 = 35.
Из одной вершины выходит 7 диагоналей (красные): к двум соседним вершинам идут стороны, а не диагонали.

Ответ: 35.

3

В стране 100 городов, и из каждого выходит ровно 4 дороги. Сколько всего дорог в стране?

Ответ: число.

Шаг 1Сумма степеней: 100 × 4 = 400.
Шаг 2Каждая дорога посчитана дважды (у двух городов), поэтому дорог 4002 = 200.

Ответ: 200.

Верно: 0 из 3

8

Курс «Логика и смекалка», урок 8 из 8

Как выигрывать всегда

Двое по очереди берут спички. Кто взял последнюю — победил. Оказывается, в таких играх исход часто известен ещё до первого хода: один из игроков может выиграть при любой игре соперника. Сегодня узнаем, кто именно и как ему действовать. Здесь пригодится всё, чему мы научились в курсе.

  • что такое выигрышные и проигрышные позиции
  • как находить стратегию, рассуждая с конца
  • как симметрия и инварианты помогают в играх

Разминка подумай 2 минуты

?

На столе 10 конфет. Двое по очереди берут 1 или 2 конфеты. Кто взял последнюю — выиграл. Кто выигрывает при правильной игре: первый или второй?

Ответ: первый или второй.

Шаг 1Рассуждаем с конца. Если перед твоим ходом 1 или 2 конфеты, забираешь всё и выигрываешь.
Шаг 2Если перед твоим ходом 3 конфеты, ты проиграл: возьмёшь 1 — соперник заберёт 2, возьмёшь 2 — соперник заберёт 1.
Шаг 3Значит, выгодно оставлять сопернику 3 конфеты. А чтобы это получилось, до этого — 6, а ещё раньше — 9.

Почему? Если соперник взял 1 конфету, берёшь 2. Если он взял 2 — берёшь 1. Вместе всегда 3, и ты снова оставляешь число, делящееся на 3.

Шаг 4Первый игрок берёт 1 конфету и оставляет 9. Дальше он дополняет каждый ход соперника до 3: 9 → 6 → 3 → 0. Последнюю конфету забирает первый.

Ответ: первый.

Главная идея

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

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

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

Секрет победы: всегда оставляй сопернику проигрышную позицию.

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

Спичек перед твоим ходомПозицияПочему
0проигрышнаяходить нечем: последнюю спичку уже взял соперник, он выиграл
1, 2 или 3выигрышнаязабираешь все спички и выигрываешь
4проигрышнаявозьмёшь 1, 2 или 3 — останется 3, 2 или 1, и соперник заберёт всё
5, 6 или 7выигрышнаявозьми столько, чтобы осталось 4: у соперника проигрышная позиция
8проигрышнаяпосле любого твоего хода останется 5, 6 или 7 — соперник оставит тебе 4

Проигрышные позиции: 0, 4, 8, 12, 16… Они идут через 4, потому что за один круг (твой ход + ход соперника) можно всегда вместе взять ровно 4 спички: соперник взял 1 — ты берёшь 3, он взял 2 — ты 2, он взял 3 — ты 1. Шаг равен «наибольшее число, которое можно взять, + 1».

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

Ещё два приёма.

Симметрия. Если после твоего хода всё на столе «одинаковое с двух сторон» (например, две равные кучки камней), можно просто повторять ход соперника на другой стороне. Тогда у тебя всегда будет ответный ход, а соперник первым останется без хода.

Счёт ходов. Бывает, что каждый ход меняет что-то ровно на 1 (например, разлом шоколадки добавляет один кусок). Тогда число ходов до конца игры заранее известно, как бы ни играли. Первый игрок делает ходы с номерами 1, 3, 5… (нечётные), второй — 2, 4, 6… (чётные). Если всего ходов нечётное число, последний ход сделает первый, если чётное — второй.

План решения
  1. Разберись, когда игра заканчивается и кто в этот момент выигрывает (взявший последний предмет или, наоборот, проигрывает).
  2. Составь таблицу позиций, как в «Главной идее»: начни с 0, 1, 2… предметов и для каждого количества реши, выигрышная это позиция или проигрышная.
  3. Найди, через сколько повторяются проигрышные позиции. В играх «можно взять от 1 до какого-то числа» шаг равен этому наибольшему числу + 1.
  4. Посмотри на начальное количество. Если оно проигрышное, выигрывает второй игрок. Если нет — первый: первым ходом он берёт столько, чтобы осталось ближайшее проигрышное количество.
  5. Дальше победитель на каждый ход соперника отвечает так, чтобы вместе они взяли ровно «шаг» (в игре «1–3 спички» — вместе 4).
  6. Если на столе «две одинаковые половины» (равные кучки, круглый стол), попробуй симметрию. Если каждый ход меняет количество ровно на 1, посчитай число ходов и посмотри на его чётность.

Разбираем задачи от простой к сложной

Сначала попробуй решить сам, а потом открой решение и сравни.

ПростоЗадача 1. 20 спичек

На столе 20 спичек. Можно брать 1, 2 или 3. Кто взял последнюю — выиграл. Кто победит при правильной игре?

Шаг 1По таблице из «Главной идеи» проигрышные позиции — числа, которые делятся на 4 без остатка: 4, 8, 12, 16, 20.
Шаг 2В начале на столе 20 спичек — это проигрышная позиция для того, кто ходит, то есть для первого игрока.
Шаг 3Как действует второй игрок: на каждый ход первого он берёт столько, чтобы вместе получилось 4. Первый взял 1 — второй берёт 3; первый взял 2 — второй 2; первый взял 3 — второй 1.
Шаг 4Тогда после ходов второго остаётся 16, 12, 8, 4, 0 спичек. Последнюю спичку забирает второй.
01234567891011121314151617181920
Красным отмечены проигрышные позиции — если перед твоим ходом столько спичек, при правильной игре соперника ты проиграешь.

Ответ: побеждает второй.

СреднеЗадача 2. Две кучки

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

Шаг 1Стратегия второго игрока — симметрия: сколько камней первый взял из одной кучки, столько же второй берёт из другой.
Шаг 2Тогда после каждого хода второго кучки снова равны.
Шаг 3Может ли первый взять последний камень? После его хода кучки обязательно становятся неравными: он берёт только из одной кучки. Значит, камни после его хода ещё остаются.
Шаг 4А второй всегда может ответить симметрично. Поэтому последний камень заберёт второй.
7 и 7первый: −37 и 4второй: −34 и 4
Первый взял 3 камня из правой кучки — второй берёт 3 из левой, и кучки снова равны.

А если кучки разные, например 5 и 8, выигрывает первый: он уравнивает кучки (берёт 3 из восьми) и дальше играет симметрично.

Ответ: побеждает второй.

СреднеЗадача 3. Монеты на круглом столе

Двое по очереди кладут одинаковые монеты на круглый стол так, чтобы они не перекрывались. Кто не может положить монету — проиграл. Кто победит?

Шаг 1Первый кладёт монету точно в центр стола.
Шаг 2Дальше на каждый ход второго первый кладёт монету симметрично относительно центра. Это значит: мысленно проводим прямую от монеты второго через центр стола и дальше, на ту же длину. В этой точке, напротив монеты второго, первый и кладёт свою монету.

Почему? Стол симметричен. Если второй нашёл свободное место, то место напротив тоже свободно — ведь до этого все монеты лежали парами симметрично. А центр уже занят, поэтому второй не может занять место, симметричное самому себе.

Шаг 3Значит, первый всегда может сделать ход. Места закончатся на ходу второго.

Ответ: побеждает первый.

СложнееЗадача 4. Шоколадка

Шоколадка 4 × 6 долек. За ход ломают любой кусок по прямой линии на два. Кто не может сделать ход (остались отдельные дольки) — проиграл. Кто победит?

Шаг 1Посмотрим, что делает один ход: один кусок становится двумя. Значит, число кусков увеличивается ровно на 1.
Шаг 2В начале 1 кусок. В конце игры — отдельные дольки: 4 × 6 = 24 куска.
Шаг 3Чтобы из 1 куска получить 24, нужно ровно 24 − 1 = 23 хода. И неважно, как ломать!
Шаг 4Ходы делают по очереди: 1-й ход — первый игрок, 2-й — второй, 3-й — первый… Нечётные ходы делает первый. 23-й ход нечётный — его делает первый игрок.
Шаг 5После 23-го хода ломать нечего, и второй не может сделать ход.
1 кусок2 куска…24 дольки
Каждый разлом увеличивает число кусков ровно на 1. Из 1 куска до 24 долек — 23 разлома.

Ответ: побеждает первый, как бы ни играли.

Запомни

1. Рассуждай с конца: найди проигрышные позиции и оставляй их сопернику.

2. В играх «бери от 1 до какого-то числа» проигрышны позиции, которые делятся на это число + 1 (например, «бери 1–3» — делятся на 4).

3. Симметрия: если можно повторять ход соперника зеркально — повторяй.

4. Если число ходов заранее известно, победителя определяет его чётность.

Интересный факт

Самая известная игра со стратегией — «Ним» с несколькими кучками. В 1901 году математик Чарльз Бутон нашёл формулу выигрыша через двоичную запись чисел. А в 1951 году в Великобритании построили компьютер Nimrod, который играл в Ним и обыгрывал людей, — одна из первых «умных» машин в истории.

Проверь себя 5 вопросов

Введи ответ и нажми «Проверить» (или Enter). Разбор откроется после ответа.

1

На столе 32 конфеты, можно брать от 1 до 4. Кто взял последнюю — выиграл. Сколько конфет должен взять первый игрок первым ходом, чтобы выиграть?

Ответ: число.

Шаг 1Можно брать до 4, значит, выгодно дополнять ходы соперника до 1 + 4 = 5. Проигрышные позиции — числа, делящиеся на 5: 5, 10, 15, 20, 25, 30.
Шаг 2Ближайшее к 32 такое число — 30. Чтобы оставить сопернику 30, первый берёт 32 − 30 = 2.
Шаг 3Дальше на каждый ход соперника первый отвечает так, чтобы вместе было 5.

Ответ: 2.

2

На столе 21 спичка, можно брать от 1 до 3. Кто взял последнюю спичку — ПРОИГРАЛ. Кто победит при правильной игре?

Ответ: первый или второй.

Шаг 1Теперь брать последнюю плохо. Если перед тобой 1 спичка — ты проиграл: обязан её взять.
Шаг 2Если перед тобой 2, 3 или 4 спички, оставь сопернику 1 — и выиграешь. Если 5 — проиграл: после твоего хода останется 2, 3 или 4.
Шаг 3Проигрышные позиции: 1, 5, 9, 13, 17, 21 — каждый раз +4.
Шаг 421 — проигрышная позиция для первого. Второй дополняет ходы первого до 4: 21 → 17 → 13 → 9 → 5 → 1, и последнюю спичку вынужден взять первый.

Ответ: второй.

3

Две кучки: 5 и 8 камней. За ход берут сколько угодно из одной кучки. Кто взял последний камень — выиграл. Сколько камней нужно взять первым ходом?

Ответ: число.

Шаг 1Из задачи 2 знаем: равные кучки — проигрышная позиция для того, кто ходит.
Шаг 2Значит, первый должен сделать кучки равными: из кучки 8 взять 8 − 5 = 3 камня.
Шаг 3Дальше он играет симметрично и побеждает.

Ответ: 3.

4

Начинаем с 0. Игроки по очереди прибавляют к числу любое число от 1 до 10. Кто первым получит 100 — выиграл. Какое число должен прибавить первый игрок первым ходом?

Ответ: число.

Шаг 1Это игра того же типа, только предметы не забирают, а прибавляют. Рассуждаем с конца. Кто получил 100 — выиграл.
Шаг 2Кто получил 89, тоже выигрывает: соперник прибавит от 1 до 10 и получит число от 90 до 99, а ты добавишь до 100.
Шаг 3Точно так же выигрывают числа 78, 67, 56, 45, 34, 23, 12, 1 — каждый раз на 11 меньше.
Шаг 4Первый прибавляет 1 и получает выигрышное число. Дальше на ход соперника отвечает так, чтобы вместе было 11.
11223344556677889100
Красным отмечены числа, которые выгодно называть самому: 1, 12, 23, 34, 45, 56, 67, 78, 89, 100. Шаг — 11.

Ответ: 1.

5

Шоколадка 6 × 8 долек. За ход ломают любой кусок по прямой на два. Кто не может сделать ход — проиграл. Кто победит?

Ответ: первый или второй.

Шаг 1Каждый ход добавляет 1 кусок. Из 1 куска нужно получить 6 × 8 = 48 долек — это 48 − 1 = 47 ходов.
Шаг 247 — нечётное число. Нечётные ходы делает первый, значит, последний, 47-й ход — его.

Ответ: первый.

Верно: 0 из 5

Домашнее задание

Эти задачи чуть сложнее. Не спеши открывать разбор — сначала попробуй несколько вариантов.

1

На столе 50 камней, можно брать от 1 до 5. Кто взял последний — выиграл. Сколько камней должен взять первый игрок первым ходом?

Ответ: число.

Шаг 1Дополняем ходы соперника до 1 + 5 = 6. Проигрышные позиции делятся на 6: 6, 12, …, 42, 48.
Шаг 2Ближайшее к 50 — 48. Первый берёт 50 − 48 = 2 и дальше дополняет ходы соперника до 6.

Ответ: 2.

2

Шоколадка 5 × 5 долек. За ход ломают любой кусок по прямой на два. Кто не может сделать ход — проиграл. Кто победит?

Ответ: первый или второй.

Шаг 1Долек 5 × 5 = 25, ходов всегда 25 − 1 = 24.
Шаг 224 — чётное число. Чётные ходы делает второй игрок, значит, последний, 24-й ход — его.

Ответ: второй.

3

Начинаем с 0. Игроки по очереди прибавляют число от 1 до 6. Кто первым получит 60 — выиграл. Какое число должен прибавить первый игрок первым ходом?

Ответ: число.

Шаг 1Можно прибавлять от 1 до 6, значит, дополняем ходы соперника до 7.
Шаг 2Выигрышные числа идут от 60 вниз с шагом 7: 60, 53, 46, 39, 32, 25, 18, 11, 4.
Шаг 3Первый прибавляет 4, а дальше на каждый ход соперника отвечает так, чтобы вместе было 7.

Ответ: 4.

Верно: 0 из 3