Алабама і зайве місце
Таблиця Бюро перепису після 1880 року показала: якби Палата представників мала 300 місць замість 299, Алабама отримала б на одне місце менше, 7 замість 8. Звідси й назва парадоксу.
Рада ділить місця між трьома районами пропорційно населенню, а дробові частки округлює найпростішим чесним правилом. Місць було 10, стане 11. Здається, що зайве місце може лише комусь додати. Скільки місць тоді отримає найменший район? Зафіксуйте відповідь, а потім перевірте її: покрутіть розмір ради самі, проженіть тисячі випадкових рад і прочитайте пояснення.
Рада ділить місця між районами з 6, 6 і 2 тисячами жителів за методом найбільших залишків. При 10 місцях малий район має 2, а при 11 лише 1, хоч місць більше, а люди ті самі. Нове місце збільшує частку кожного району пропорційно його розміру, і залишки великих районів обганяють залишок малого. 1880 року так у таблиці Бюро перепису Алабама мала 8 місць при Палаті зі 299 і 7 при Палаті з 300.
Ділити місця пропорційно легко, доки частки цілі. Але людей не ділять на шматки, тож дроби треба якось округлити. Правило нижче придумав Александер Гамільтон, і воно здається бездоганно чесним.
У районі А 6 000 жителів, у районі Б теж 6 000, у районі В 2 000. Разом 14 000.
Чесна частка району — це скільки місць йому належало б, якби місця можна було різати: населення району × кількість місць / усе населення. При 10 місцях це 6 000 × 10 / 14 000 ≈ 4,29 для А і Б і 1,43 для В.
Кожен район спершу отримує цілу частину своєї частки: 4, 4 і 1. Це 9 місць. Місця, що лишилися, роздають по одному районам з найбільшою дробовою частиною. Десяте місце дістається В: у нього 0,43, а в А і Б лише по 0,29. Виходить 4, 4 і 2.
Раду збільшують до 11 місць. Населення не змінилося, правило те саме. Скільки місць тепер отримає район В?
«Місць стало більше, тож нікому не може стати менше. У гіршому разі все лишиться як було»
Насправді В отримує 1 місце замість 2. Частки ростуть: 4,71, 4,71 і 1,57. Цілі частини ті самі, 4, 4 і 1, але тепер лишаються два місця, і обидва забирають великі райони: їхні 0,71 обігнали 0,57 району В.
| 10 місць | частка | ціле | місць |
|---|---|---|---|
| А 6 000 | 4,29 | 4 | 4 |
| Б 6 000 | 4,29 | 4 | 4 |
| В 2 000 | 1,43 | 1 | 2 |
Оберіть відповідь кнопкою під повзунком або введіть число. При 10 місцях у району В їх 2.
Тут з'явиться порівняння вашої відповіді з правильною.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Порахуйте чесні частки для 11 місць так само, як для 10: населення району × 11 / 14 000.
Скільки місць дають цілі частини при 11 місцях? Скільки лишається зайвих і в кого найбільші дробові залишки?
На скільки зростає частка кожного району від одного нового місця? Однаково для всіх чи пропорційно населенню?
Наступні раунди ділять місця: ви покрутите розмір ради й населення самі, комп'ютер переділить тисячі випадкових рад, а потім пояснення. Спершу відповісти в раунді 1 чи йти далі?
Ви обрали завжди показувати всі раунди.
Рухайте розмір ради, міняйте населення районів, додайте четвертий чи п'ятий район. Таблиця ділить місця за правилом найбільших залишків і порівнює з радою на одне місце меншою. Справа всі розміри від 1 до 40: рожеві клітинки — ті, де додане місце в когось забирає місце.
Клітинка h рожева, якщо при переході від h − 1 до h місць хоч один район утрачає місце. Пунктир — рівні залишки на межі, тоді місце вирішує жереб. Натисніть клітинку, щоб відкрити цей розмір.
Знайдіть парадокс для інших чисел: змініть населення так, щоб пропорція була не 3 : 3 : 1, і шукайте рожеву клітинку. Чи вдасться з двома районами?
Комп'ютер складає випадкові ради: від 2 до 12 районів з населенням від 1 до 100 тисяч, від 10 до 40 місць. Для кожної він ділить місця, додає одне місце й ділить знову. Трьома способами: найбільшими залишками і двома методами дільників, д'Ондта і Сент-Лаге, якими рахують мандати в багатьох парламентах.
Перевірка: Python на 500 000 рад для кожної кількості районів дає 0% для двох районів, 2,4% для трьох, 3,9% для чотирьох, 5,1% для шести і 6,2% для дванадцяти (похибка ±0,1 пункту). Із двома районами парадоксу немає жодного разу, а методи дільників не дають його ніколи.
Після вашої відповіді тут з'явиться код симуляції, який можна запустити в себе.
Та сама симуляція коротко і без бібліотек. JavaScript запускається в консолі браузера (F12) або в Node, Python потребує лише стандартної бібліотеки.
// Випадкові ради: від 2 до 12 районів з населенням від 1 до 100 тисяч, від 10 до 40 місць. Додаємо одне місце: чи втрачає хтось місце?
function largestRemainder(p, h) {
const P = p.reduce((a, b) => a + b, 0), q = p.map(x => x * h / P), s = q.map(Math.floor);
const order = p.map((_, i) => i).sort((a, b) => (q[b] - s[b]) - (q[a] - s[a]));
const left = h - s.reduce((a, b) => a + b, 0);
for (let k = 0; k < left; k++) s[order[k]]++; // зайві місця — найбільшим залишкам
return s;
}
function dHondt(p, h) { // наступне місце — найбільшому p / (s + 1)
const s = p.map(() => 0);
for (let k = 0; k < h; k++) { let b = 0; p.forEach((x, i) => { if (x / (s[i] + 1) > p[b] / (s[b] + 1)) b = i; }); s[b]++; }
return s;
}
console.log('6·6·2 тис.: 10 місць', largestRemainder([6, 6, 2], 10), '11 місць', largestRemainder([6, 6, 2], 11));
const loses = (f, p, h) => { const a = f(p, h), b = f(p, h + 1); return a.some((x, i) => b[i] < x); };
const T = 20000;
for (const n of [2, 3, 4, 6, 8, 12]) {
let ham = 0, dh = 0;
for (let t = 0; t < T; t++) {
const p = Array.from({ length: n }, () => 1 + 99 * Math.random()), h = 10 + Math.floor(31 * Math.random());
if (loses(largestRemainder, p, h)) ham++;
if (loses(dHondt, p, h)) dh++;
}
console.log('районів', n, '· найбільші залишки', (100 * ham / T).toFixed(1) + '%', '· д\'Ондт', dh);
}
# Випадкові ради: від 2 до 12 районів з населенням від 1 до 100 тисяч, від 10 до 40 місць. Додаємо одне місце: чи втрачає хтось місце?
import math, random
def largest_remainder(p, h):
P = sum(p)
q = [x * h / P for x in p]
s = [math.floor(x) for x in q]
order = sorted(range(len(p)), key=lambda i: q[i] - s[i], reverse=True)
for i in order[:h - sum(s)]: # зайві місця — найбільшим залишкам
s[i] += 1
return s
def d_hondt(p, h): # наступне місце — найбільшому p / (s + 1)
s = [0] * len(p)
for _ in range(h):
s[max(range(len(p)), key=lambda i: p[i] / (s[i] + 1))] += 1
return s
print("6·6·2 тис.: 10 місць", largest_remainder([6, 6, 2], 10), "11 місць", largest_remainder([6, 6, 2], 11))
def loses(f, p, h):
a, b = f(p, h), f(p, h + 1)
return any(y < x for x, y in zip(a, b))
T = 20000
for n in [2, 3, 4, 6, 8, 12]:
ham = dh = 0
for _ in range(T):
p = [1 + 99 * random.random() for _ in range(n)]
h = random.randint(10, 40)
ham += loses(largest_remainder, p, h)
dh += loses(d_hondt, p, h)
print("районів", n, "· найбільші залишки", f"{100 * ham / T:.1f}%", "· д'Ондт", dh)
Інтуїція думає про місця, а правило дивиться на дробові залишки. Нове місце додає кожному району шматок, пропорційний його населенню, тож великі отримують більші шматки й обганяють малого в черзі за зайвими місцями.
Шар «На пальцях» приховано на всіх задачах.
Це ще не все пояснення, але суть така. Зайві місця дістаються тим, у кого найбільший «хвостик» після цілих. Одне нове місце ділиться між районами як усе інше, пропорційно населенню: А і Б отримують по 6/14 ≈ 0,43 місця, а малий В лише 2/14 ≈ 0,14. Хвостик В майже стоїть, а хвостики великих районів стрибають уперед.
При 10 місцях одне зайве місце, і його бере В з найбільшим хвостиком 0,43. При 11 місцях зайвих два, але хвостики А і Б виросли до 0,71 і обігнали 0,57 району В. Обидва зайві місця йдуть великим, а В лишається з цілою частиною, 1.
| 3 місця | місць | 4 місця | місць | |
|---|---|---|---|---|
| А | 1,29 | 1 | 1,71 | 2 |
| Б | 1,29 | 1 | 1,71 | 2 |
| В | 0,43 | 1 | 0,57 | 0 |
Ті самі 6, 6 і 2 тисячі. У раді з трьох місць кожен район має по одному: третє місце бере В з хвостиком 0,43. Додайте четверте, і В утрачає своє єдине місце: 0,57 менше за 0,71 у великих.
Частки двох районів разом дають ціле число, тож їхні хвостики разом дають або 0, або 1. Зайве місце буває щонайбільше одне, і бере його той, чий хвостик більший за половину. Тобто кожен район просто округлює свою частку до найближчого цілого.
А частка з новим місцем лише росте, тож і округлена частка не може зменшитися. Саме тому в раунді 2 з двома районами рожевих клітинок немає, а в симуляції парадокс з'являється лише від трьох районів.
Шар «Строго» приховано на всіх задачах.
Кожна точка — дробова частина частки при h місцях. Коли частка перескакує через ціле, хвостик падає до нуля, тож графік схожий на пилку. Зуби А і Б круті, бо їхня частка росте на 3/7 місця за крок; зуби В пологі, лише 1/7. Пропорція 3 : 3 : 1 повторюється кожні 7 місць, тому В утрачає місце при переходах 3 → 4, 10 → 11, 17 → 18 і далі через кожні сім.
Хай у районі p жителів, усього P, місць h. Частка q = p · h / P. Додаємо місце: q зростає на p/P, тобто на частку району в населенні. Усі частки ростуть на той самий відсоток, а в абсолютних числах великі ростуть більше.
Сума всіх часток завжди h, тож кількість зайвих місць дорівнює сумі хвостиків. Район утрачає місце, коли його ціла частина не зросла, а кількість районів з більшим хвостиком стала не меншою за кількість зайвих місць. Для цього треба, щоб хтось інший обігнав його в черзі, а обігнати може лише той, чия частка росте швидше, тобто більший район.
Найбільші залишки ніколи не дають району менше за округлену вниз частку і більше за округлену вгору. Це «правило квоти»: 1,57 може стати лише 1 або 2, а не 0 чи 3. Порушити монотонність метод може, а вийти за межі частки — ні.
Тож при 11 місцях В з 1 місцем формально в межах: його частка 1,57. Порушено інше: при 10 місцях, коли частка була меншою, 1,43, він мав 2.
Частка району i з населенням pi при h місцях і загальному населенні P, та її ріст від одного нового місця.
Кожен район отримує цілу частину, а зайвих місць k стільки, скільки дають разом дробові частини.
Приклад 6, 6, 2 тисячі (P = 14): частки при 10 і 11 місцях.
Метод дільників: шукають одне число d і округлюють кожну частку pi/d своїм правилом (д'Ондт — униз, Сент-Лаге — до найближчого). Більше місць означає менше d, тож жодне pi/d не зменшується.
Найбільші залишки — це не один дільник для всіх, а окрема черга з хвостиків при кожному h. Черга при h + 1 може виявитися зовсім іншою, ніж при h, і саме тут з'являється парадокс.
Шар «Глибше» приховано на всіх задачах.
Д'Ондт (у США його називали методом Джефферсона), Сент-Лаге (метод Вебстера) і Гантінгтон — Гілл ділять населення кожного району на спільний дільник і округлюють. Їх можна рахувати й послідовно: кожне наступне місце йде району з найбільшим p/(s + 1) у д'Ондта чи p/(2s + 1) у Сент-Лаге, де s — уже отримані місця. Рада з h + 1 місць — це рада з h місць плюс ще одне, тож забрати місце в когось такий метод не може. Ця властивість зветься монотонністю за розміром ради.
Ціна — правило квоти. Чотири райони з 20, 5, 5 і 5 тисячами, 10 місць: частка великого 5,71, а д'Ондт дає йому 7, більше за округлену вгору частку. Найбільші залишки дали б йому 6, у межах частки.
Мішель Балінскі і Пейтон Янг довели, що жоден метод розподілу не може завжди дотримуватися правила квоти й водночас ніколи не давати парадоксу населення (коли район, що росте швидше, утрачає місце на користь того, що росте повільніше). Для чотирьох і більше районів це неможливо в принципі. Вони виклали цю теорію в книжці «Fair Representation» 1982 року.
Тож вибір методу — це вибір, яку несправедливість терпіти. Методи дільників монотонні, але інколи виходять за межі частки. Найбільші залишки тримаються меж, але страждають від парадоксів Алабами, населення і нових штатів (раунд 5).
Після перепису 1880 року головний клерк Бюро перепису США Чарльз Сітон розрахував розподіл місць у Палаті представників за методом Гамільтона для всіх розмірів від 275 до 350. При 299 місцях Алабама мала 8, а при 300 лише 7. Ми перерахували це з населення 38 штатів за переписом (разом 49 371 340 осіб; Невада отримує обов'язкове за Конституцією 1 місце, хоч її частка 0,38):
| Штат | населення | частка, 299 | місць | частка, 300 | місць |
|---|---|---|---|---|---|
| Алабама | 1 262 505 | 7,646 | 8 | 7,671 | 7 |
| Техас | 1 591 749 | 9,640 | 9 | 9,672 | 10 |
| Іллінойс | 3 077 871 | 18,640 | 18 | 18,702 | 19 |
При 299 місцях після цілих частин лишалося 20 місць, і Алабама з хвостиком 0,646 взяла останнє, двадцяте, випередивши Іллінойс і Техас з їхніми 0,640. При 300 хвостик Алабами виріс лише на 0,026, Техасу на 0,032, а Іллінойсу на 0,062. Обидва обігнали Алабаму. Водночас частки трьох штатів перескочили через ціле число, тож зайвих місць стало не 20, а 18, і Алабама опинилася дев'ятнадцятою в черзі. Відкриття викликало бурю в Конгресі; 1911 року Палата перейшла на метод Вебстера, а з 1941-го рахує методом Гантінгтона — Гілла.
Найбільші залишки можуть покарати район не лише за нове місце, а й за власне зростання чи за появу сусіда. А в реальних виборах цим правилом рахують мандати й досі.
Парадокс населення. Район А росте, Б стоїть на місці, а місце переходить від А до Б. Причина та сама: усі частки рахуються від загального населення, а воно росло через третій район, тож хвостики пересортувалися. За Вікіпедією та книжкою Джеймса Стайна, 1900 року Вірджинія так утратила місце на користь Мена, хоч росла швидше.
Парадокс нових штатів. До ради приєднують новий район разом з його чесною часткою місць. Старі райони нічого не віддавали, а місце між ними переходить. 1907 року Оклахома увійшла до США з 5 новими місцями, і перерахунок забрав місце в Нью-Йорка й віддав Мену.
Кожна з вимог звучить очевидно: кожен отримує свою частку, округлену вниз чи вгору; більше місць нікого не ображає; хто росте швидше, не втрачає на користь того, хто росте повільніше. Теорема Балінскі — Янга каже, що разом вони несумісні. Це не вада конкретного правила, а властивість самої задачі: дроби не можна округлити так, щоб округлення поводилося як дроби.
Схоже з голосуванням: парадокс Кондорсе показує, що навіть думку більшості не завжди можна скласти в чесний порядок. А частини і ціле, які поводяться по-різному, є ще в парадоксі Сімпсона і феномені Вілла Роджерса, де середні всіх груп ростуть, а люди ті самі.
За законом «Про вибори народних депутатів України» 2011 року (ст. 98), за яким обирали Раду 2012, 2014 і 2019 років, 225 мандатів за списками ділять між партіями, що подолали 5%. Виборча квота — це голоси за ці партії, поділені на 225; кожна партія отримує цілу частину від своїх голосів, поділених на квоту, а решту мандатів по одному отримують партії з найбільшими дробовими залишками. Голоси нижче — офіційні результати ЦВК, перевірте самі.
Бундестаг ділив місця між партіями методом Гера — Німаєра, тобто найбільшими залишками, з виборів 1987 року. 2008 року закон замінив його методом Сент-Лаге — Шеперса, щоб уникнути парадоксів, і вперше його застосували на виборах 27 вересня 2009 року. Якщо ділите ціле на цілі частини в таблиці (бюджет між відділами, ноутбуки між командами), а загальна сума може змінитися, беріть метод дільників: зайва одиниця тоді нікому не зменшить частку.
Таблиця Бюро перепису після 1880 року показала: якби Палата представників мала 300 місць замість 299, Алабама отримала б на одне місце менше, 7 замість 8. Звідси й назва парадоксу.
Після перепису 1900 року Бюро розрахувало Палату на 350–400 місць. Колорадо отримувало 3 місця за будь-якого розміру, крім одного: при 357 лише 2.
Оклахома стала штатом, і Палату збільшили на її 5 місць. Перерахунок забрав одне місце в Нью-Йорка й віддав Мену, хоч ці штати нічого не міняли.
На виборах до Верховної Ради 2019 року останні зайві мандати розподілили за залишками. «Батьківщина» з залишком 0,511 отримала мандат, а «Опозиційна платформа — За життя» з 0,500 — ні.
З 1941 року Палата представників США ділить свої 435 місць між штатами методом Гантінгтона — Гілла. Це метод дільників, і парадоксу Алабами в ньому немає.
Бундестаг з 1987 року ділив місця найбільшими залишками (метод Гера — Німаєра). Через парадокси 2008 року його замінили методом Сент-Лаге — Шеперса, уперше на виборах 2009 року.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Шкільна математика» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.