2. Некоторые комбинаторные примеры

Укажем сначала несколько вопросов об оценках. Пусть дано множество целых чисел от 1 до и две случайно выбранные перестановки этого множества. Каково

математическое ожидание а числа элементов в группе, порожденной этими двумя перестановками.

Аналогично пусть два случайных преобразования множества в себя. Каково математическое ожидание х числа элементов в порожденной ими полугруппе? Будет ли

Эти числа, конечно, не превосходят соответственно В каком отношении находятся между собой и х? Если мы будем исходить из трех или большего числа перестановок и такого же числа преобразований, изменится ли это отношение на обратное?

Во всяком случае для малых эти вопросы можно исследовать эмпирически с помощью машины. Это может быть сделано для умеренного числа, скажем 100, случайно выбранных пар перестановок. Хотя 100 очень мало по сравнению с даже для равного, скажем, 7, средние значения и х могут быть с большой вероятностью хорошо аппроксимированы с помощью такого испытания.

В качестве другого примера таких испытаний или подхода «Монте-Карло» к комбинаторным задачам можно привести задачу о передвижении шахматного коня. Она состоит в определении последовательности ходов, при которой конь побывает на каждом поле доски и притом по одному разу. Эйлер нашел много решений этой задачи, но общий способ нахождения таких маршрутов не известен даже для обычной шахматной доски размером 8X8. Приводящими к цели кажутся некоторые практические указания, например данное Эйлером правило о передвижении коня в места, которые уже почти окружены.

Совершенно очевидно, что счетная машина может пытаться находить решения методом проб и ошибок даже с учетом правил, подобных вышеуказанному, или более сложных, основанных на учете последних ходов в случаях, когда возникает тупик. Память, нужная для этих задач, мала, и казалось бы, что преимущество в скорости, имеющееся у машины, является существенным в ситуациях такого рода, где преимущество «видения», имеющееся у человеческого мозга, очень мало.

Число «попыток», которые можно осуществить на машине в течение нескольких часов, имеет порядок . Результатом такой статистики будет доля успешных попыток

при применении данных правил. Уэллс на счетных машинах в Лос Аламосе получил результаты для этой задачи, сравнивая случай с другими случаями

Эвристические результаты могут быть получены также в комбинаторном аспекте алгебры кванторов на модели проективной алгебры (ср. гл. I, п. 5). Если бесконечное множество, то известно, что, исходя из двух множеств в можно с помощью операций проективной алгебры получить неограниченное число новых множеств. Если конечное множество, состоящее из точек, то возникает вопрос о нахождении базиса, порождающего множество всех подмножеств Конечно, точек образуют такой базис. Но каково минимальное число элементов базиса? Представляют некоторый интерес и проективные алгебры, порожденные двумя фиксированными произвольно выбранными подмножествами из Каково математическое ожидание числа элементов в порожденной таким образом проективной алгебре? Это может быть исследовано на счетной машине для всех малых до 7 или близкого числа. Очевидная симметрия в условиях задачи сводит число подлежащих исследованию случаев вместо примерно до

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

При малых на счетных машинах может быть решен аналогичный вопрос для трехмерного пространства, т. е. где аппроксимация производится с помощью преобразований, приведенных в гл. IV.

Комбинаторная иллюстративная лемма гл. II была проверена Келли для рассмотрением всех случаев. Вероятно, более быстродействующая машина может за сравнительно небольшое время рассмотреть все случаи для

Келли [1] проверил для малых вопрос о том, вытекает ли из изометрии пространств изометрия и В

для конечных А к В с метрикой, в которой расстояние принимает только значения 1 или 2. Эту задачу также стоит исследовать для больших на электронной счетной машине.