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

В восьмой главе фанфика между Гарри Поттером и Гермионой Грейнджер происходит своеобразное "состязание интеллектов", и как его часть Поттер предлагает своей собеседнице следующую игру.

Игра "2-4-6".
- Есть игра, основанная на известном эксперименте «Задание 2-4-6». Суть игры в следующем. Существует известное только мне правило, которому подчиняются определённые тройки чисел. 2-4-6 — это один из примеров тройки, подходящей под правило. А вообще… давай, я запишу правило на бумажке, просто, чтобы ты знала, что оно зафиксировано, сверну листок и отдам его тебе…

— Правила игры такие, — продолжал он. — Ты сообщаешь мне тройку чисел, и если эта последовательность описывается правилом, то я говорю «да», а в противном случае — «нет». Я — Природа, правило — один из моих законов, и ты изучаешь меня. Ты уже знаешь, что тройке 2-4-6 соответствует «да». Когда ты проведёшь все тесты, какие захочешь, то есть назовёшь столько троек, сколько посчитаешь нужным, остановись и попробуй угадать правило, а затем можешь развернуть листочек и посмотреть, права ты или нет. Суть игры понятна?



Естественно, Гермиона Грейнджер в эту игру проигрывает. Трудность в том, что выиграть в эту игру на самом деле нельзя.

Доказательство невозможности выигрыша в игру "2-4-6".
Для краткости уговоримся называть тройки, удовлетворяющие записанному правилу, "хорошими". Докажем, что в описанную выше игру нельзя выиграть за конечное число ходов. Предположим противное. Тогда существует алгоритм, позволяющий за конечное число ходов описать множество всех "хороших" троек. Однако, учитывая тот факт, что никаких ограничений на правило, по которому выбираются тройки, не накладывается, оказывается, что для любого конечного числа ходов k можно предъявить 2 различных правила (и, соответственно, два различных множества хороших троек) так, что этим правилам будут соответствовать одинаковые ответы на первые k вопросов. В силу того, что единственный возможный вариант хода, который предлагается в условии, заключается в проверке, является ли тройка "хорошей", все ходы, предлагаемые алгоритмом, однотипны и заключаются в таких проверках. Предложим теперь два правила, которые этот алгоритм не может различить за k ходов. Зафиксируем k.
Первое правило: "хорошими" являются первые k троек, которые перечисляются в алгоритме (мы предположили, что такой алгоритм существует) и только они.
Второе правило: "хорошими" являются первые k троек, которые перечисляются в алгоритме, а также одна любая тройка, которая в алгоритме не упоминается.
Нетрудно видеть, что предложенный алгоритм не сможет различить эти два правила, причем не только за k вопросов, но и вообще за любое их количество. Однако, мы предполагали, что такой алгоритм позволяет за конечное число описать множество всех "хороших" троек. Противоречие.


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

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

Однако, эту "дырку" достаточно просто "заткнуть", что приведет нас к важной и при этом не очень сложной математической идее - идее счетного множества. Дело в том, что все шаги алгоритма можно пронумеровать - просто указав, каким по счету нужно делать соответствующий ход. Тем самым мы пронумеровали все перечисленные в алгоритме тройки.
Определение: бесконечное множество, элементы которого можно пронумеровать, называется счетным.
Нетрудно видеть, что такие множества бывают - например, множество натуральных чисел можно пронумеровать. Для этого достаточно сказать, что каждое натуральное число - это и есть его номер. Замечу, что номера "бесконечность" не бывает. Возникает вопрос - а все ли множества чисел либо пустые (т.е. не содержат ни одного элемента), либо конечные, либо счетные? Ответ на этот вопрос дает следующее утверждение.

Множество всех десятичных дробей (в том числе бесконечных) из промежутка (0,1) не является счетным.
Доказательство.
Перейдем от десятичных дробей к двоичным, т.е. дробям, записанным в двоичной системе счисления. Тогда каждая дробь из указанного промежутка имеет вид 0,x1x2x3x4..., где числа x1, x2 и так далее - либо нули, либо единицы. Предположим, что нам удалось как-то занумеровать все двоичные дроби из промежутка от 0 до 1. Выпишем их по порядку:
a_1=0,x(1,1)x(1,2)x(1,3)...
a_2=0,x(2,1)x(2,2)x(2,3)...
a_3=0,x(3,1)x(3,2)x(3,3)...
...
Приведем теперь пример дроби, которой нет в этом списке: положим
b=0,z(1)z(2)z(3)..., где z(j)=1-x(j,j), т.е. если в дроби a_j на месте номер j стоит 0, то в b на этом месте стоит 1 и наоборот. Нетрудно видеть, что b лежит между 0 и 1. Однако, ни для какого из a_k не может быть верно равенство a_k=b, так как у этих двух дробей различаются числа на k-том месте после запятой. Значит, у числа b нет номера. Противоречие.


Из этого утверждения уже понятно, как нужно дополнить наше утверждение о невозможности выиграть в игру 2-4-6, чтобы в нем не было логических пробелов.

Добавление к доказательству о невозможности выиграть в 2-4-6.
В силу того, что все шаги алгоритма занумерованы, множество троек, упоминающихся в алгоритме, счетно. Однако, так как никаких ограничений на то, какими могут быть числа в тройке, не наложено, то последнее число в тройке может быть, в частности, любым числом вида 6+x, где х лежит в промежутке (0,1). Но мы уже доказали, что все числа из этого промежутка занумеровать нельзя. Значит, есть хотя бы одно число y такого вида, которое не упоминается в алгоритме. Тройка (2,4,y) - искомая.


Интересные вопросы на подумать:
1. А целые числа - счетное множество?
Ответ: да.

2. А рациональные числа?
Ответ: да.

3. А если сказать, что числа, из которых составляются тройки, могут быть только целыми, то их будет счетное множество?
Ответ: да.

4. А в таком случае можно выиграть в 2-4-6?
Ответ: за конечное число шагов - все равно нельзя.

5. Как доказать все сформулированное выше?

@темы: расстановка палочек над Т, Тексты - мои, Наука, Книги