Математические головоломки и развлечения - [106]
Кто смотрит и кто не смотрит телевизор?
* * *
Профессор Априле прислал две фотографии, изображенные на рис. 179.
Рис. 179Дополнительный ряд отверстий у нижнего края этих карточек позволяет безошибочно сортировать их.
Дополнительный ряд отверстий и прорезей у нижнего края каждой карточки позволяет быстро и безошибочно сортировать карты. Булавки, воткнутые в отверстия нижнего ряда, удерживают карты, остающиеся после изъятия части колоды с помощью булавок, воткнутых в отверстия верхнего ряда.
Ответ
Логическая задача решается с помощью перфокарт следующим образом.
Пусть А, В, С, D и Е означают: Абнер, Верил, Клео, Дейл и Эллсуорт. Каждое утверждение считается истинным, если соответствующее лицо смотрит телевизор, в противном случае оно ложно.
Условие 1 позволяет отбросить все карты с комбинацией АВ>-; условие 2 —карты с комбинацией D>-E>-; условие 3 исключает комбинации ВС и В>-С>-; условие 4 исключает комбинации C>-D и CD>-; условие 5 исключает комбинации А>-Е и DE>-. Остается единственная карта с комбинацией A>-B>-CDE>-. Отсюда мы заключаем, что Клео и Дейл смотрят телепередачу, а остальные члены семьи не смотрят ее.
Глава 36. ТЕОРИЯ ГРУПП И КОСЫ
Понятие «группы» — одно из основных понятий современной алгебры, охватывающее общие свойства самых разнообразных объектов различной природы и служащее неоценимым средством исследования в физике. Джеймс Р. Ньюмен сравнивал его с улыбкой Чеширского Кота:[57] когда Чеширский Кот (алгебра в том виде, как ее обычно преподают в школе) исчезает, остается только его абстрактная улыбка. Но улыбка подразумевает нечто веселое, занимательное. Может быть, теория групп покажется нам менее загадочной, если мы не будем воспринимать ее слишком серьезно.
Трое программистов — Эймз, Бейкер и Кумбс — хотят решить, кому из них платить за пиво. Разумеется, они могли бы бросить монетку, но предпочитают случайный выбор, основанный на игре, которая состоит в блуждании по некоторой сети линий. На листе бумаги проведены три вертикальные линии (назовем их основой).
Один из программистов, держа лист так, чтобы его друзья не видели, что он делает, обозначает эти линии наугад буквами А, В и С (рис. 180, а).
Рис. 180Блуждание по линиям «основы» и «утка».
Верхний край листа он загибает так, чтобы буквы не были видны. Второй программист наугад проводит ряд горизонтальных линий (назовем их утком), каждая из которых соединяет какие-нибудь две вертикальные линии (рис. 180, б). Третий программист добавляет еще несколько горизонтальный линий, а у одной из вертикальных линий снизу ставит букву X (рис. 180,в).
Лист бумаги разворачивают. Эймз ставит свой палец в верхнюю точку линии А и начинает обводить ее сверху вниз. Дойдя до начальной или конечной точки линии утка (если точка пересечения вертикальной линии с линией утка лежит внутри горизонтального отрезка, Эймз ее пропускает и следует дальше), он поворачивает и проходит всю эту линию до другого ее конца, после чего снова поворачивает и продолжает спускаться вниз до тех пор, пока снова не встретит начальную или конечную точку другой линии утка. Так продолжается, пока он не достигнет нижней точки какой-нибудь вертикальной прямой. Если его путь (на рис. 180,г он показан пунктирной линией) заканчивается не в точке X, то за пиво платит не он. Затем точно таким же способом по сети прямых путешествуют Бейкер и Кумбс. Путь Бейкера заканчивается в точке X, поэтому за пиво приходится платить ему. Каким бы ни было число линий основы (вертикальных прямых), независимо от того, как проведены линии утка (горизонтальные прямые), пути игроков всегда заканчиваются на различных прямых, и никакие два маршрута никогда не приводят к одной и той же линии.
При более подробном рассмотрении этой игры выясняется, что в основе ее лежит одна из простейших групп — так называемая группа перестановок трех элементов. Что же такое группа? Это некая абстрактная структура, состоящая из множества элементов (а, Ь, с….), относительно природы которых не делается никаких предположений, с единственной бинарной операцией (ее мы обозначим символом о), сопоставляющей каждой паре элементов множества некоторый третий элемент. Чтобы такая структура составляла группу, должны выполняться следующие четыре условия:
1. Каждой паре элементов множества операция ставит в соответствие некоторый элемент того же множества. Это свойство носит название «замкнутости» множества относительно операции.
2. Операция подчиняется «ассоциативному закону»:
(а о Ь) о с = а о (b о с).
3. Существует элемент е (называемый «единицей»), такой, что
а о е = е о а = а.
4. Для каждого элемента а существует обратный элемент а', такой, что
а о а' = а' о а = е.
Если помимо только что названных четырех условий операция подчиняется еще и коммутативному закону:
а о Ь = b о a,
то группа называется коммутативной, или абелевой.
Целые числа — положительные, отрицательные и нуль — образуют группу относительно сложения (это наиболее известный пример группы). Множество целых чисел замкнуто относительно сложения (прибавить 2 к 3, а затем к 4 — то же самое, что прибавить 2 к сумме чисел 3 и 4); «единицей» группы служит 0, а элементом, обратным (или, как говорят еще, противоположным) целому положительному числу, — то же число, взятое со знаком минус. Группа целых чисел относительно сложения — абелева (2 + 3 = 3 + 2). Если в качестве операции выбрать деление, то целые числа не будут образовывать группы: поделив 5 на 2, мы получим 2,5, а это число не принадлежит множеству целых чисел.
