Книга: Программирование игр и головоломок

Доказательства теорем

Доказательства теорем

Компьютер можно использовать для доказательства теорем. Это — трудная задача искусственного интеллекта. Мы снабжаем компьютер правилами вывода, даем формулировку того, что требуется доказать, и исходные аксиомы. Компьютер пытается найти последовательность правил вывода, которые могут привести от исходных данных к требуемым рёзультатам.

Здесь обо всем этом речь не идет. Я предлагаю вам только взглянуть на путь, использованный для доказательства с помощью компьютера знаменитой проблемы четырех красок: любая географическая карта может быть раскрашена четырьмя красками так, что любые две территории, имеющие общую границу, раскрашены, разными красками. Общая идея состоит в том, чтобы доказать вручную или, в случае необходимости, с помощью программы, что проблема будет решена полностью, если будет известно ее решение в некотором конечном числе случаев. Эти случаи исследуются на компьютере. Вот примеры, доступные этому методу.

Внимание: вы должны бороться с проблемой сложности. Если вы не будете принимать никаких мер предосторожности, число подлежащих исследованию случаев может сказаться невероятно большим и работа компьютера станет невозможной: ведь перед вами не вечность… Равновесие между подготовительной работой (доказательством палых теорем) и работой компьютера оценивается в зависимости от ваших возможностей, одновременно в области математических доказательств и в ресурсах вашего микрокомпьютера. К сожалению, не говорите: эта программа отнимает уйму времени, я перепишу ее на ассемблере. Это — худшее из решений. Все, что я вам предлагаю, осуществимо на Бейсике за разумное время. Если ваша программа требует уйму времени, значит, она плохо придумана.

Головоломка 12. Теорема 153.

Этот пример заимствован из [MJB]. Образуем числовую последовательность следующим образом:

— начальный элемент — произвольное натуральное число, кратное трем,

— за любым элементом последовательности следует число, равное сумме кубов всех цифр данного элемента.

Теорема. Любая такая последовательность становится (начиная с некоторого места) постоянной, равной 153.

Пример. Начнем с 33:

33

3? + 3? = 54

5? + 4? = 189

1? + 8? + 9? = 1242

1? + 2? + 4? + 2? = 81

8? + 1? = 153

1? + 5? + З? = 153

1? + 5? + З? = 153

и теперь последовательность стала постоянной.

Используйте ваш компьютер для доказательства этой теоремы.

? Головоломка 13. Варианты.

Нелегко сказать, какую роль в предыдущей теореме играет то, что исходное число кратно трем. Но от вас не потребует чрезмерных усилий в общем случае, что два последовательных числа последовательности имеют равные остатки при делении их на 3. В последовательностях, которые мы стали изучать, все члены последовательности делятся на 3. Можно доказать также, что все члены последовательности, кроме, быть может, первого, делятся на 9.

Если взять натуральное число, не кратное трем, то все члены соответствующей последовательности будут иметь один и тот же остаток при делении на 3. Что, кроме этого, вы можете узнать о поведении этих последовательностей?

Если при переходе к следующему члену последовательности вы будете брать сумму квадратов цифр (вместо того, чтобы брать сумму кубов), то все будет не намного лучше. Можете ли вы доказать следующую теорему: каково бы ни было натуральное число, взятое в качестве первого элемента последовательности, эта последовательность содержит число, не превосходящее 4?

? Головоломка 14. Теорема 6174. Построим последовательность натуральных чисел следующим образом. Начальный элемент — натуральное число с четырьмя цифрами, которые не все равны между собой. Мы переходим от данного члена последовательности к следующему но такому правилу.

Пусть a, b, c, d — четыре цифры, представляющие десятичную запись данного числа. Расположим их в порядке убывания слева направо и получим первое число. Расположим их в обратном порядке и вычтем это второе числа из первого. Это и есть искомый следующий член последовательности.

Теорема. Эта последовательность для любого начального элемента становится (начиная с некоторого места) постоянной, равной 6174.

Пример. Начнем с 7815:

8751 ? 1578 = 7173

7731 ? 1377 = 6354

6543 ? 3456 = 3087

8730 ? 0378 = 8352

8532 ? 2385 = 6174

6174 ? 1467 = 6174

Используйте ваш компьютер для доказательства этой теоремы. Это окажется намного проще, чем в предыдущей головоломке, поскольку имеется всего лишь 9000 чисел с четырьмя цифрами, и нужно исследовать 9000 последовательностей. Но вы можете сделать число испытаний намного меньше этого…

?? Головоломка 15. Господин S и господин P[7].

Вот одна из наиболее классических арифметических головоломок. Выберем два натуральных числа, больших единицы, но меньших ста. Значение их суммы сообщено господину S, значение их произведения — господину P. Ни один из них не знает, какое число сообщено другому. Господин P звонит господину S по телефону.

P. Я не могу найти эти два числа.

S. Я знаю, что вам это и не удалось бы.

P. Ах, так… Но тогда я их знаю!

S. Ну, тогда и я тоже их знаю!

Рассуждение позволяет существенно видоизменить задачу, и даже более того — предъявить решение. Много ли их? Используйте ваш компьютер, чтобы их найти.

Оглавление книги