hpmor и счетность

пятница, 18 декабря 2015

15:54

Southeast

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

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

Игра "2-4-6"

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

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

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

Ответ:

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

Множество всех десятичных дробей (в том числе бесконечных) из промежутка (0,1) не является счетным.

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

Добавление к доказательству о невозможности выиграть в 2-4-6.

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

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

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

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

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

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