Инесса Раскина - Логика для всех. От пиратов до мудрецов

7.10. Решение 1.Предположим, что нет двух друзей, которые послали открытки друг другу. Тогда каждый мог получить не более четырех открыток – только от тех, кому сам не посылал. И даже если все открытки дошли, каждый получил меньше открыток, чем послал. Поэтому и общее число отправленных открыток больше числа полученных. Противоречие.

Решение 2.Предположим, что нет двух друзей, которые послали открытки друг другу. Тогда послано не более 10 · 9: 2 = 45 открыток, но по условию их было послано 5*10 = 50. Противоречие.

7.11.Допустим, что это возможно. Пусть сумма чисел, стоящих в концах отрезков, равна А , сумма чисел, расположенных в серединах отрезков, равна В, а сумма трех чисел вдоль каждого отрезка равна С. Ясно, что А + В = 0 + 1 + 2 +.. + 9 = 45. Каждая концевая точка принадлежит ровно трем отрезкам, а все середины различны. Поэтому, сложив суммы чисел на всех шести отрезках, получим: ЗА + В = 6С. Отсюда 2А + 45 = 6С. Получили противоречие, так как слева нечетное число, а справа четное.

Ответ.Нельзя.

7.12.Вничью игра закончиться не может. Это означает, что ровно у одного из игроков есть выигрышная стратегия. Предположим, что такая стратегия есть у второго игрока. Долька, находящаяся в правом верхнем углу, съедена в любом случае после первого хода. Если у второго есть выигрышная стратегия, то у него есть выигрышный ответный ход на ход первого, состоящий в поедании только правой верхней дольки. Но этот выигрышный ход первый может с тем же успехом сделать сам с самого начала, а далее воспользоваться выигрышной стратегией второго.

7.13. Обсуждение.Задача кажется неприступной. Прежде чем нащупать «узкое место», хочется поэкспериментировать. Но как тут экспериментировать, когда секторов 25, да еще и порядок произвольный? А если секторов поменьше? Если секторов три, их все посетить не удастся, это доказывается коротким перебором. Если четыре, то их все можно посетить. Если пять – снова не удается. Здесь полный перебор уже затруднителен, зато видны две особенности сектора номер пять: если попадешь в пятерку, оттуда никуда не уйдешь; если удается пройти почти все числа, то именно пятерка всегда остается. Интересно, почему?

Решение.Предположим, что кузнечик побывал во всех секторах. Тогда сектор с номером 25 был последним, так как из него кузнечик не сможет переместиться в иной сектор. До этого кузнечик не мог побывать дважды в одном секторе, иначе бы его путь зациклился, и в 25-й сектор он бы не попал. А побывав во всех секторах по разу, кузнечик переместился бы на 1 + 2 +… + 24 = 300 секторов, то есть на число, кратное 25. Значит, он начал свое путешествие в 25-м секторе, что невозможно.

7.14. 1) Предположим, что после построения по росту Вася выше стоящего сразу за ним Никиты более чем на 10 см. Назовем Васю и стоящих перед ним мальчиков высокими, а Никиту и стоящих после него мальчиков низкими. Разница в росте между любым высоким и любым низким мальчиком больше 10 см. Но при первоначальном построении, идя вдоль строя от Васи к Никите, мы на каком-то шаге перейдем от высокого к низкому. Эти два мальчика стояли рядом, поэтому разница в росте между ними не превышает 10 см. Противоречие.

2) Пусть мальчики и девочки построены в пары в порядке убывания роста. Предположим, что в одной из пар мальчик Ваня выше девочки Маши более, чем на 10 см. Тогда рост каждого мальчика, стоящего до Вани, отличается от роста каждой девочки, стоящей после Маши, еще сильнее. Поэтому при первом построении каждый из этих мальчиков, включая Ваню, мог стоять только с кем-то из девочек, стоящих перед Машей, но таких девочек на одну меньше, чем требуется. Противоречие. Если Маша выше Вани, рассуждения аналогичны.

7.15. Слово «надо» употребляется в разных смыслах. Сначала подразумевается «нужное количество ленивых учеников», а потом – «нужное количество прилежных учеников».

8.6. Обсуждение.Пусть А: «У Винни-Пуха хорошее настроение»; Б: «Винни-Пух хорошенько подкрепился». В какую строчку таблицы истинности надо посмотреть? Ответ.Не прав.

8.7. Истинны высказывания в пунктах 1, 3, 4, 5, 7. Ложны высказывания 2, 6, 8.

8.8. Все три высказывания означают, что некузявых ляпусиков не бывает.

Ответ.Равносильны.

8.9. Пусть Д спит. Тогда А и Г спят (из 5). Тогда Б спит (из 1), поэтому В не спит (из 3). Но это противоречит 4.

Значит, Д не спит. Тогда спят Г (из 2) и В (из 4), а Б не спит (из 3). Поэтому А не спит (из 1).

Ответ.В и Г.

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

Пусть при любой рассадке по кругу найдутся два мальчика рядом. Рассмотрим произвольную рассадку и занумеруем детей по кругу по часовой стрелке. А затем посадим детей в таком порядке: 1, 3, 5, 7, 9, 11, 13, 15, 17, 2, 4, 6, 8, 10, 12, 14, 16. По условию после этого найдутся два мальчика рядом. Но раньше они сидели через одного, т. е. в исходном положении был гость, сидевший между ними.

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

8.11. 1) Всего существует 6 теорем указанного вида. Если дать их все, то последняя будет следовать из предыдущих. А 5 можно дать в таком порядке: 1 ⇒ 2, 1 ⇒ 3, 2 ⇒ 3, 3 ⇒ 2, 3 ⇒ 1.

2) Всего существует 12 таких теорем. Как отмечено в предыдущем пункте, с участием утверждений 1, 2 и 3 нельзя давать все 6 возможных теорем. Без ограничения общности можно исключить теорему 2 ⇒ 1. Но с участием утверждений 2, 3 и 4, а также 1, 3 и 4 тоже нельзя давать все 6 возможных теорем. Если пытаться решить обе проблемы исключением лишь одной теоремы, исключать надо 3 ⇒ 4 или 4 ⇒ 3. В любом из случаев остается цепочка из восьми теорем 1 ⇒ 3 ⇒ 2 ⇒ 4 ⇒ 1, из которой придется исключить как минимум одну теорему, и останется не более 9 теорем. Пример на 9 теорем: 1 ⇒ 2, 1 ⇒ 3, 1 ⇒ 4, 2 ⇒ 3, 2 ⇒ 4, 3 ⇒ 4, 4 ⇒ 3, 4 ⇒ 2, 4 ⇒ 1.

3) Пример на теорем:

1 ⇒ 2, 1 ⇒ 3…, 1 ⇒ n,

2 ⇒ 3, 2 ⇒ > 4…, 2 ⇒ n,

n — 1 ⇒ n,

n ⇒ n − 1, n ⇒ n − 2…, n ⇒ 1.

Доказательство максимальности удобно изложить на языке графов. Будем считать утверждения вершинами, а теоремы – ориентированными ребрами. Оставим только ребра, ориентированные в обе стороны. Если бы они образовали цикл, то последняя доказанная в этом цикле теорема следовала бы из предыдущих теорем цикла. Значит, циклов нет. Тогда «двойных» ребер – не более n — 1, поэтому всего доказано не более теорем.