|
Всегда ли это происходит? Является ли магистраль единственным «аттрактором» движения муравья? Никто не знает. Это одна из фундаментальных нерешенных задач теории сложности. Максимум, что нам известно, — это то, что, какой бы ни была первоначальная конфигурация черных клеток, муравей не останется навечно в пределах ограниченной области поля.
Гипотеза Адамара
Матрица Адамара, названная в честь Жака Адамара, представляет собой квадратную матрицу из нулей и единиц, такую, что в любых двух ее рядах или столбцах половина элементов совпадает, а другая половина — отличается. На рис. 50 можно увидеть матрицы размеров 2, 4, 8, 12, 16, 20, 24 и 28, где 0 и 1 обозначены черным и белым цветом. Такие матрицы появляются во многих математических задачах и в компьютерных науках, в первую очередь в теории кодирования. (В некоторых приложениях, в том числе в задаче, которой первоначально занимался Адамар, белые квадраты соответствуют −1, а не 0.) Адамар доказал, что подобные матрицы могут существовать только при n = 2 или n, кратном 4. Теорема Пейли 1933 г. доказывает, что матрица Адамара существует всегда для n, кратного 4 и равного 2<sup>a</sup>(p<sup>b</sup> + 1), где p — нечетное простое число. Из чисел, кратных 4, под эту теорему не подпадают 92, 116, 156, 172, 184, 188, 232, 236, 260, 268 и другие, более крупные значения n. Гипотеза утверждает, что матрица Адамара существует любых размеров, кратных 4. В 1985 г. К. Савад нашел матрицу размера 268. Есть и другие числа, не удовлетворяющие условию теоремы Пейли, с которыми уже разобрались. В 2004 г. Хади Харагани и Бехруз Тайфех-Резайе нашли матрицу Адамара размера 428, и теперь минимальное значение n, для которого она неизвестна, составляет 668.
Уравнение Ферма — Каталана
Это диофантово уравнение x<sup>a</sup> +y<sup>b</sup> = z<sup>c</sup>, где a, b и c — положительные целые числа, показатели степени. Я назову это уравнение уравнением Ферма — Каталана, потому что его решения имеют отношение как к Великой теореме Ферма (см. главу 7), так и к гипотезе Каталана (см. главу 6). Если a, b и c малы, ненулевые целые решения не особенно удивительны. К примеру, если все они равны 2, мы имеем уравнение Пифагора, которое, как известно со времен Евклида, имеет бесконечно много решений. Так что основной интерес представляют те случаи, когда показатели степени велики. Формально они являются «большими», когда s = 1/a + 1/b + 1/c меньше 1. Известно лишь десять больших решений уравнения Ферма — Каталана: 1 + 2³ = 3², 2<sup>5</sup> + 7<sup>2</sup> = 3<sup>4</sup>, 7<sup>3</sup> + 13<sup>2</sup> = 2<sup>9</sup>, 2<sup>7</sup> + 17<sup>3</sup> = 71<sup>2</sup>, 3<sup>5</sup> + 11<sup>4</sup> = 122<sup>2</sup>, 17<sup>7</sup> + 76 271<sup>3</sup> = 21063928<sup>2</sup>, 1414<sup>3</sup> + 2213459<sup>2</sup> = 65<sup>7</sup>, 9262<sup>3</sup> + 15312283<sup>2</sup> = 113<sup>7</sup>, 43<sup>8</sup> + 9622<sup>3</sup> = 30042907<sup>2</sup>, 33<sup>8</sup> + 159034<sup>2</sup> = 15613<sup>3</sup>. Первое из этих решений считается большим, потому что 1 = 1<sup>a</sup> для любого a и для a = 7 в том числе. Гипотеза Ферма — Каталана утверждает, что для больших s уравнение Ферма — Каталана имеет лишь конечное число целых взаимно простых решений. |
