Математические головоломки профессора Стюарта

– Что показывает лишь, насколько легко наш глаз обмануть, Ватсап. Предположим, что стороны треугольника имеют единичную длину. Тогда вариант Малфатти имеет площадь 0,31567, но площадь второго варианта составляет 0,31997, то есть немного больше.

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

– Может быть, разница и невелика, Сомс, но вывод ясен. Малфатти ошибся.

– В самом деле. Мало того, Ватсап, разница между вариантом Малфатти и правильным решением в некоторых случаях может оказаться намного больше. К примеру, если треугольник будет длинным, тонким и равнобедренным, то верным решением будет расположить круги один на другом, и площадь такого варианта будет почти вдвое превосходить вариант Малфатти.

Он сделал паузу, чтобы швырнуть раскрошившийся гипсовый отпечаток следов Ratufa macroura через всю комнату в камин.

– Ирония в том, – добавил он наконец, – что вариант Малфатти никогда не бывает лучшим. «Жадный» алгоритм – вписать в треугольник наибольший возможный круг, затем найти наибольший круг, который вписывается в оставшиеся промежутки, и напоследок проделать то же самое в третий раз – всегда лучше и всегда приводит к верному ответу.

Дополнительную информацию см. в главе «Загадки разгаданные».

Квадратные остатки

Полные квадраты заканчиваются на одну из цифр 0, 1, 4, 5, 6 или 9. Они не могут заканчиваться на 2, 3, 7 или 8. Более того, последняя цифра квадрата числа зависит только от последней цифры этого числа.

Если число заканчивается на 0, то его квадрат тоже заканчивается на 0.

Если число заканчивается на 1 или 9, то его квадрат заканчивается на 1.

Если число заканчивается на 2 или 8, то его квадрат заканчивается на 4.

Если число заканчивается на 5, то его квадрат тоже заканчивается на 5.

Если число заканчивается на 4 или 6, то его квадрат заканчивается на 6.

Если число заканчивается на 3 или 7, то его квадрат заканчивается на 9.

Специалисты по теории чисел предпочитают описывать подобные эффекты с помощью целых чисел по некоторому модулю. Если взять модуль 10, то достаточно рассмотреть только числа 0–9: возможные остатки от деления любого числа на 10. Их квадраты (по модулю 10) равны

0 1 4 9 6 5 6 9 4 1

и приведенный выше список правил для определения последней цифры квадрата по последней цифре числа – это всего лишь другой способ сказать то же самое.

За исключением начального 0, список квадратов (по модулю 10) симметричен: числа 1, 4, 9, 6 после 5 повторяются в обратном порядке: 6, 9, 4, 1. Симметрия возникает благодаря тому, что квадраты n и 10 – n по модулю 10 равны. В самом деле, 10 – n – то же, что – n (mod 10), а n² = (−n)². Поэтому данные четыре числа в списке фигурируют дважды; 0 и 5 встречаются там только по одному разу, а 2, 3, 7, 8 не встречаются вовсе. Это не слишком демократично, но это так.

Что происходит, если мы берем другой модуль? Величины квадратов по этому модулю называются квадратичными вычетами. (Здесь под «вычетом» подразумевается остаток от деления на модуль.) Остальные цифры при этом становятся квадратичными невычетами.

Предположим, к примеру, что модуль равен 11. Тогда возможные полные квадраты (чисел, меньших 11) равны

0 1 4 9 16 25 36 49 64 81 100.

По модулю 11 это дает

0 1 4 9 5 3 3 5 9 4 1.

Таким образом, квадратичные вычеты (по модулю 11) – это

0 1 3 4 5 9.

А невычеты – это

2 6 7 8.

Приведем небольшую таблицу.

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

Возводя число в квадрат, мы умножаем его на самого себя, а там, где речь заходит об умножении, в теории чисел главную роль всегда играют простые числа. Поэтому стоит начать с простых модулей – 2, 3, 5, 7, 11 – в приведенном списке. Модуль 2 уникален: единственные возможные вычеты по модулю 2 – это 0 и 1, и оба они являются полными квадратами. Для всех остальных простых чисел примерно половина вычетов являются квадратами, а остальные – не являются. Точнее, если p – простое число, то существует (p + 1)/2 различных квадратичных вычетов и (p − 1)/2 невычетов. Квадратичные вычеты обычно являются квадратами двух различных чисел, n² и (– n)² для подходящего n. Однако 0 встречается в списке лишь однажды, потому что –0 = 0.

Составные модули усложняют ситуацию. Теперь одни и те же вычеты иногда могут быть квадратами больше чем двух чисел. К примеру, 1 по модулю 8 встречается четыре раза, как квадрат 1, 3, 5 и 7. Лучший способ разобраться во всем этом – воспользоваться современной абстрактной алгеброй, но имеет смысл взглянуть и на модуль 15. У него два простых множителя: 3 × 5. А вот список квадратов:

Таким образом, квадратичные вычеты по модулю 15 равны

0 = 0²

1 = 1², 4², 11², 14²

4 = 2², 7², 8², 13²

6 = 6², 9²

9 = 3², 12²

10 = 5², 10²