Задача Льюиса Кэрролла про пиратов
Льюис Кэрролл (настоящее имя — Чарльз Лютвидж Доджсон, 1832–1898) известен не только «Алисой», но и как математик и автор изящных логических задач. Одна из его классических головоломок — о пиратах и «минимуме общего несчастья».
«В ожесточённом бою 70 из 100 пиратов потеряли один глаз, 75 — одно ухо, 80 — одну руку и 85 — одну ногу. Каково минимальное число потерявших одновременно глаз, ухо, руку и ногу?»
Подобные задачи, связанные с вычислением числа элементов в конечных множествах, встречаются и в школьной практике. Решать её можно разными способами, в том числе логически, без формул. Попробуйте сначала решить самостоятельно, прежде чем обратиться к решениям ниже.
Решение 1. Через множества
Сначала попробуем решить задачу используя операции над множествами и формулы алгебры теории множеств.
Обозначим через N(A) количество элементов множества A; I — универсальное множество данной задачи; C(A) — дополнение множества A до I, то есть A + C(A) = I, C(A) = I − A.
В теории множеств используется другая символика: А + В — объединение, АВ — пересечение, А − В — разность множеств, дополнение А обозначают через А с верхней чертой (здесь пишем C(A)).
Пусть A множество одноглазых, B — множество одноухих, C — множество одноруких и D — множество одноногих. Эти множества могут попарно пересекаться. Тогда, например, C(A) означает множество пиратов, сохранивших оба глаза.
Требуется оценить количество элементов пересечения ABCD.
Тогда I = C(A) + C(B) + C(C) + C(D) + ABCD.
Диаграмма Эйлера-Венна для этой задачи представлена ниже.
Отсюда следует, что число элементов множества I не больше суммы числа элементов множеств C(A), C(B), C(C), C(D) и ABCD. Она была бы равна этой сумме, если бы множества C(A), C(B), C(C), C(D) попарно не пересекались.
Число элементов множества C(A) равно 30, множества C(B) — 25, множества C(C) — 20 и множества C(D) — 15. Тогда 100 ≤ 30 + 25 + 20 + 15 + N(ABCD), N(ABCD) ≥ 100 − 90 = 10.
Итак, не менее 10 пиратов лишились и глаза, и уха, и руки, и ноги.
Решение 2. Логическое
Чтобы минимизировать число пиратов с четырьмя ранениями, нужно максимизировать тех, кто уцелел хотя бы в чём-то.
Считаем максимально возможное число «счастливчиков»:
- Пиратов с целыми глазами: 30
- Пиратов с целыми ушами: 25
- Пиратов с целыми руками: 20
- Пиратов с целыми ногами: 15
Если бы эти группы не пересекались, то всего уцелевших в чём-либо было бы максимально: 30 + 25 + 20 + 15 = 90.
Тогда оставшиеся 100 − 90 = 10 пиратов не имеют ни одной неповрежденной части тела. Эти 10 пиратов и есть те, кто потерял одновременно и глаз, и ухо, и руку, и ногу.