Путеводитель для влюблённых в математику - Эдвард Шейнерман

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

3x + 1, или проблема Коллатца^[212]

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

Логистическое отображение – функция, заданная простой алгебраической формулой. Однако функции можно задавать иначе. Функция F, о которой сейчас пойдет речь, определена исключительно для положительных целых чисел и задана следующим образом:

Эта функция задается двумя простыми алгебраическими формулами, но мы выбираем формулу в зависимости от того, четное число x или нечетное.

Пример:

• F (9) = 28. Число 9 – нечетное, поэтому мы руководствуемся формулой 3х + 1 и получаем 3 × 9 + 1 = 28;

• F (10) = 5. Число 10 – четное, поэтому мы руководствуемся формулой x/2 и получаем 10/2 = 5.

Вне зависимости от того, четное число мы подставляем в функцию или нечетное, ее значение будет целым положительным числом.

Короче говоря, если x – целое положительное число, F (x) – тоже целое положительное число.

Мы можем итерировать нашу функцию, потому что выходное значение удовлетворяет условию, наложенному на входное значение. Что мы получим, итерируя функцию при начальном значении x = 12?

• F (12) = 6, потому что число 10 четное;

• F² (12) = F (6) = 3, потому что число 6 четное;

• F³ (12) = F (3) = 10, потому что число 3 нечетное;

• F⁴ (12) = F (10) = 5.

Вот удобный способ проиллюстрировать итерации. Мы записываем 12 → 6, подразумевая, что значение функции от 12 равно 6. Мы можем записать итерации F следующим образом:

Тройка 4 → 2 → 1 повторяется! А что дальше? Так как F(1) = 4, F(4) = 2, F(2) = 1, следующие три значения те же самые.

Другими словами, когда мы дошли до числа 1, тройка 4 → 2 → 1 будет повторяться до бесконечности.

Начнем с другой величины, скажем с 9. Вот что мы имеем: 9 → 28 → 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

Вот еще один впечатляющий ряд итераций:

27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

Мы снова дошли до 1, но после ста с лишним итераций.

Гипотеза Коллатца^[213] заключалась в том, что вне зависимости от того, с какого целого положительного числа x мы начинаем, последовательность итераций рано или поздно достигает единицы и тройка 4 → 2 → 1 повторяется до бесконечности.

Проблема была решена самым умопомрачительным образом – штурм потребовал чудовищной дотошности математиков-профессионалов и математиков-любителей.

Глава 22
Демократический выбор и теорема Эрроу

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

Выбор в случае двух кандидатов

Знакомая всем демократическая процедура – выборы, на которых два кандидата претендуют на одну и ту же должность. Избиратели отдают голоса за первого или второго кандидата, и побеждает тот, кто наберет больше голосов.

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

Вообразим, что два кандидата, претендующих на одну и ту же должность, зовутся A и B. Избиратели отдают голос за того или другого^[214]. Если отдано n голосов, данные голосования выглядят следующим образом^[215]:

Как используется такой профиль предпочтений для принятия решения? Обычно просто подсчитывают, сколько голосов было отдано за каждого кандидата. Победителем оказывается тот, кто набрал больше голосов. Мы назовем такой подход правилом большинства – это метод демократических сообществ. Но это не единственный метод учета профиля предпочтений для принятия решения. Посмотрим на альтернативы.