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

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, поэтому всего доказано не более теорем.

Ответ. 1) 5; 2) 9; 3)

9.4. На семи карточках написаны три четных и четыре нечетных числа. Судить о четности суммы двух чисел из четырех можно лишь тогда, когда все четыре числа имеют одинаковую четность. Значит, все три четных числа на карточках первого мудреца.

Ответ. 6, 8, 10.

9.5. Если бы оба ответили «Да», у судьи не было бы никаких оснований считать одного из близнецов Джоном. Значит, второй близнец ответил: «Нет». Если Джон – первый, то оба сказали правду, что противоречит условию. Значит, Джон второй. При этом оба брата солгали.