Некоторые способы решения логических задач (Шевченко) 1979  год - старые учебники

ПРЕДИСЛОВИЕ

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

Конечно, выделение логических задач носит до некоторой степени условный характер. Трудно определить, какую задачу следует назвать логической. Кажется, любая задача является таковой, так как для ее решения требуются определенные логические рассуждения. Но все же мы склонны одни задачи называть арифметическими, поскольку в них имеем дело с числовым материалом, другие — геометрическими или алгебраическими в зависимости от того, идет ли в них речь о фигурах или об алгебраических выражениях. Но есть задачи, в которых мы не находим ни геометрических фигур, ни чисел. В них речь идет о высказываниях об объектах, вообще говоря, произвольной природы. Эти задачи,

по традиции, и называют логическими задачами.

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

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

Критические замечания и пожелания просим направлять по адресу: 252054, Киев-54, Гоголевская, 7, Головное издательство издательского объединения «В ища школа», редакция литературы по математике и физике.

• 1. РЕШЕНИЕ ЗАДАЧ СПОСОБОМ ЗДРАВОГО РАССУЖДЕНИЯ

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

Задача 1. Крестьянину нужно перевезти через реку волка, козу и капусту. В лодку можно взять только или волка, или козу, или капусту. Как осуществить перевоз, чтобы волк не съел козу, а коза не съела капусту?

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

Рассмотрим более сложную задачу.

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

Решение. Условия задачи не будут нарушены, если первым рейсом отправятся двое слуг. Переправившись через реку, один из них остается, а другой возвращает лодку. Вторым рейсом переезжают еще двое слуг, и один из них, например слуга генерала Грозного, возвращает лодку и остается со своим генералом на берегу. Третьим рейсом

отправляются через реку генералы Лихой и Строгий. Кому теперь возвращать лодку? Ни один из генералов этого сделать не может, поскольку его слуга не может оставаться в присутствии чужого генерала, если здесь нет своего генерала. Этого не может сделать и ни один из слуг, так как, переправив лодку на противоположный берег, он там будет находиться в присутствии чужого генерала. Выход только один — лодку должен возвращать один из генералов со своим слугой. Четвертым рейсом поедут два генерала, а затем еще двумя рейсами слуга перевезет оставшихся двух слуг.

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

Задача 3. (На студенческом математическом вечере. Шуточный номер — «проверка логического мышления и сообразительности»).

Трое испытуемых студентов садятся друг другу в затылок. (Понятно, что сидящий сзади видит головы двух впереди сидящих товарищей, а сидящий вторым видит голову только одного впереди сидящего. Оборачиваться им запрещено).

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

Испытуемым предлагается в течение короткого времени назвать цвет своего колпака.

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

Решение. Нам нужно рассмотреть различное распределение цветов при надевании колпаков.

1. Совершенно тривиальный случай, если первым двум студентам будут надеты белые колпаки. Так как их только два и сидящий сзади видит их надетыми на головы впереди сидящих, то он определенно скажет, что у него на голове черный колпак. (Безусловно, что после такого заявления сзади сидящего каждый из впереди сидящих может сказать, что у него на голове белый колпак).

2. Наденем на голову первому студенту белый колпак, а второму — черный. Теперь сидящий сзади не может знать,

какого цвета колпак у него на голове, поскольку он может быть либо белым, либо черным. В этом случае сидящий вторым рассуждает так: «Я вижу белый колпак. Если бы и на мне был белый колпак, то сидящий сзади уже заявил бы, что на нем черный колпак. Но он молчит. Значит, он не видит на мне белого колпака. Следовательно, на мне черный колпак».

Таким образом, в этом случае второй студент может вполне определенно заявить, что на нем черный колпак. (После такого заявления и впереди сидящий может сказать определенно, что на нем белый колпак. Сидящий же сзади назвать цвет своего колпака не может).

3. Наденем теперь впереди сидящему студенту черный колпак, а второму и третьему — безразлично какой. В этом случае ни третий, ни второй не могут назвать цвет своего колпака. Сидящий первым будет рассуждать так: «Если бы на мне был белый колпак, то кто-нибудь из сзади сидящих знал бы цвет своего колпака и сказал бы об этом. Но они оба молчат. Значит, на мне нет белого колпака». В этом случае впереди сидящий может определенно заявить, что на нем черный колпак.

Задача 4. Среди семи внешне одинаковых монет есть одна фальшивая — более легкая по весу. Как при помощи двух взвешиваний на чашечных весах (без гирь) найти фальшивую монету?

Решение. Разложим монеты на три кучки — по три, две и две монеты. Затем взвесим монеты в одинаковых кучках (первое взвешивание). Если весы оказались не в равновесии, то в более легкой кучке еще одним взвешиванием находим фальшивую монету. Если же весы в равновесии, то фальшивая монета находится среди трех оставшихся монет. Положим на каждую чашку весов по одной монете. Если весы не в равновесии, то фальшивая монета — более легкая. Если же весы в равновесии, то фальшивая монета — оставшаяся.

При условии, что фальшивая монета более тяжелая по весу, чем нормальная, задача решается аналогично.

Задача 5. Среди 12-ти внешне одинаковых монет есть одна фальшивая, но неизвестно, легче она или тяжелее, чем нормальная монета. Как при помощи трех взвешиваний на чашечных весах (без гирь) найти фальшивую монету?

Решение. Разложим монеты на три кучки — по четыре монеты в каждой. Взвесим монеты в двух кучках (первое взвешивание). Рассмотрим возможные случаи.

1.  Весы находятся в равновесии. В этом случае фальшивая монета находится среди четырех монет оставшейся кучки. Из четырех монет оставшейся кучки мы возьмем на чашку весов только три монеты, а на другую чашку весов положим три нормальные монеты (второе взвешивание). Если весы оказались в равновесии, то.фальшивая монета — четвертая оставшаяся, и третьим взвешиванием мы определяем, тяжелее или легче она, чем нормальная монета. Если же весы находятся не в равновесии, то это второе взвешивание нам определяет, тяжелее или легче фальшивая монета, чем нормальная. Затем третьим взвешиванием мы из трех монет выделяем фальшивую (см. предыдущую задачу).

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

Для дальнейшей работы нам важно ориентироваться, какие монеты и из какой кучки мы будем брать.

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

Если весы оказались в равновесии, то среди монет, лежащих на весах, нет фальшивой, а фальшивая находится среди трех оставшихся монет второй кучки. Значит, фальшивая монета легче нормальной. Теперь третьим взвешиванием легко находим среди трех монет фальшивую, уже зная, что она легче нормальной (см. предыдущую задачу).

Если весы не уравновесились, то нужно рассмотреть еще два случая:

а) Тяжелее оказалась та чашка, на которой лежит монета из второй кучки (напомним, что она одна). Это значит, что монета из второй кучки нормальная, но вместе с ней лежит фальшивая монета из первой кучки (т. е. фальшивая монета тяжелее нормальной). Теперь третьим взвешиванием среди двух монет найдем фальшивую, более тяжелую по весу.