Изображения страниц
Текст статьи Рубанов И. С., Канель-Белов А. Я. Математическая сказка // Квант. — 2009. — № 1. — С. 35.
Первая публикация:
Белов А., Рубанов И. С. Математическая сказка // Квант. — 1995. — № 2. — С. 14.
У Царя-бюрократа подданые объединяются в тайные общества. Каждое подможество подданных рассматривается как тайное общество. Для эффективного контроля царь хочет, чтобы на каждое тайное общество кто-то доносил. Однако каждый в состоянии писать доносы только на одно тайное общество. Докажите, что царю для этой цели не хватит людей, даже если население страны бесконечно.
Решение. Назовём человека порядочным, если он доносит только на то тайное общество, членом которого он не состоит.
Порядочные люди существуют. Иначе каждому пришлось бы доносить на общество, состоящее только из него самого (любой, кто доносит на общество, состоящее из единственного другого гражданина, порядочен по определению). Такая ситуация не только противоречит здравому смыслу, но и невозможна математически — другие подмножества окажутся неохваченными.
Кто доносит на множество всех порядочных людей?
Если он порядочен, то он доносит на общество, членом которого состоит, т. е. непорядочен. Если же он непорядочен, то он доносит на общество, членом которого не является, — т. е. порядочен. Противоречие.
Сказка — ложь, да в ней намёк: множество всех подмножеств любого множества имеет большую мощность, чем исходное множество.
Замечание. Если подданных не больше одного, то затея царя не осуществится, если для полноты отчётности он будет требовать, чтобы доносили и на пустое множество.