Путеводитель для влюбленных в математику - [52]

следующим образом:

Тройка 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]:

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

Правило диктатора подразумевает, что решение принимается на основе голоса одного-единственного человека, скажем избирателя № 1. Если № 1 выбирает A, побеждает A; если № 1 выбирает B, побеждает B. Другие мнения не учитываются.

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

Для вящей справедливости метод принятия решения должен обладать определенными свойствами. Обидная особенность правила диктатора заключается в том, что голоса не учитываются равным образом. Более формально: справедливый метод принятия решения должен следовать нейтральности учета голосов[216] – не важно, кто голосует, важно, сколько голосов отдано за того или другого кандидата. Правило большинства отвечает требованию нейтральности учета голосов, а правило диктатора – нет.

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

Есть и другой метод. Назовем его правилом алфавита. Побеждает тот кандидат, чье имя идет первым по алфавиту. Тогда в любом случае побеждает кандидат A.

Очевидно, и этот метод несправедлив, но почему?

Он обладает свойством нейтральности учета голосов: все избиратели равны в том плане, что не учитывается ничье мнение! Проблема состоит в том, что кандидаты поставлены в неравное положение. Мы будем говорить, что метод обладает свойством нейтральности учета кандидатов[217], если к кандидатам относятся одинаково; если кандидат сменит имя, это не повлияет на итог выборов.

Чувство справедливости требует нейтральности учета голосов и нейтральности учета кандидатов. Достаточно ли этого?

Есть еще один метод, который мы будем называть правилом нечетности: победу одерживает тот кандидат, который набрал нечетное число голосов. Если A предпочли 20 избирателей, а B – 13 избирателей, побеждает B. Этот метод отвечает требованиям нейтральности учета голосов и нейтральности учета кандидатов.

Или рассмотрим правило меньшинства: побеждает тот, кто набрал меньше всего голосов. Если A предпочли 12 избирателей, а B – 30 избирателей, побеждает A. Этот метод также отвечает требованиям