Шахи та математика - 3
Човен є найпоширенішою фігурою в комбінаторних завданнях на шахівниці і часто згадується навіть у серйозній математичній літературі. Що спільного, скажімо, між шаховим терміном «човна» і суто математичним поняттям «багаточлен»? Проте американський математик Дж. Ріордан у своїй книзі "Введення в комбінаторний аналіз" часто використовує термін "ладейний багаточлен". Виявляється, великий клас комбінаторних завдань, важливих у прикладній математиці, зводиться до підрахунку числа тих чи інших розстановок тур на шахівниці. У цьому істотну роль грає многочлен
Нехай потрібно призначити n робітників на n різних робіт, причому кожна робота повинна виконуватись лише одним робітником. Скільки способами можна здійснити таке призначення?
Поставимо у відповідність робітникам горизонталі шахової дошки n n, а роботам її вертикалі. Якщо i-й робітник призначається на j-ю роботу, то поле, що відповідає перетину i-ї горизонталі та j-ї вертикалі, займемо турею. Оскільки кожна робота виконується одним робітником і кожен робітник призначається однією роботу, то результаті розстановки n ладей всі вертикалі і горизонталі дошки міститимуть по одному човні, тобто. човни не загрожують один одному. Отже, нашим завданням про призначення можна надати шахове формулювання.
Скільки способами можна розставити n не загрожують один одному ладей на дошці n ґ n?
Фактично в цьому завданні потрібно знайти число rn коефіцієнт при старшому члені ладейного многочлена. Перш ніж провести обчислення, зауважимо, що при будь-якому розташуванні більше n човнів знайдеться хоча б одна вертикаль і хоча б одна горизонталь із двома або більше човнами, тобто човнами. n ¦ це найбільша кількість мирних тур на дошці n ґ n. Одна з розстановок восьми мирних турів назвичайній дошці наведено на рис. 25 2 .
З'ясуємо тепер, скільки всього існує розташувань, що шукаються n ладей на дошці n ґ n. На першу вертикаль можна довільно поставити одну з n човнів потім на другу вертикаль - одну з (n - 1) човнів, що залишилися, причому горизонталь, зайнята першою човном виключається (човни не повинні загрожувати один одному) на третю вертикаль - одну з (n - 2 ) що залишилися (горизонталі, зайняті першими двома човнами, виключаються) і т.д., аж до (n - 1)-ї вертикалі, на якій для човна залишається вибір з двох горизонталей, і останньої, n-ї вертикалі, з єдиним полем для тури. Комбінуючи n різних розташувань тури на першій вертикалі з (n - 1) розташуванням на другій, (n - 2) на третьій і т.д., отримуємо n(n - 1) 2·1=n! різних розташувань човнів. Це і є шуканим. Зокрема, на звичайній дошці вісім човнів, що не загрожують один одному, можна розмістити 8! = 40320 методами.
Якщо човни занумеровані числами від 1 до n, то існує вже (n!) 2 розташування човнів, що не загрожують один одному. Це випливає з того, що n потрібних полів можна вибрати n! способами; стільки ж способів є розташування цих полях n занумерованих ладей.
Отже, n робітників можна призначити на n робіт n! у різний спосіб. Нехай обрано призначення, яке відповідає рис. 25, тобто. i-го робітника призначили на i-у роботу, і потрібно зробити нове призначення з урахуванням того, що кожен робітник хоче змінити свою попередню роботу. Скільки таких призначень? Це завдання має інше човникове формулювання.
Скільки способами можна розставити n не загрожують один одному ладей на дошці n ґ n так, щоб жодна з них не стояла на головній діагоналі (для звичайної дошки надіагоналі a1-h8)?
Додаткова умова значно ускладнює вирішення завдання. Навіть Ейлер не вдалося знайти загальну формулу для числа An зазначених розстановок. Щоправда, він вивів рекурентне співвідношення An=(n - 1)(An - 1+An - 2), за допомогою якого можна послідовно визначати значення An для будь-якого n і 3 (A1=0, A2=1). Пізніше була знайдена формула для An, яка має такий вигляд:
Для n=8 отримуємо A8=14833, тобто. за додаткової умови кількість розстановок восьми човнів, що не загрожують один одному, зменшується майже втричі.
У розглянутих задачах про човнах, як і в аналогічних задачах для інших фігур, зазвичай передбачається, що всі вони одного кольору. Якщо розставляти і білі, і чорні фігури, кількість розстановок збільшується.
Скільки способами можна розставити n мирних ладей на дошці n ґ n, якщо k з них білі і n - k чорні?
Будь-яка розстановка, що задовольняє умов завдання, визначається вибором n полів для всіх n мирних човнів і потім зазначенням k полів з цих n, на яких будуть розташовані білі човни, інші n - k полів займуть чорні човни. Таким чином, кількість розстановок, що шукається, дорівнює n! Cn k.
Розглянемо знову розміщення на рис. 25. Ми бачимо, що вісім човнів здатні взяти під обстріл усі поля шахівниці. Відповідно, для охорони всієї дошки n ґ n достатньо мати n човнів. Якщо човнів менше, ніж n, то принаймні одна її вертикаль і одна горизонталь виявляться порожніми і, отже, поле, яке стоїть на їхньому перетині, не буде атаковано.
Скільки способів можна розставити n ладей на дошці n ґ n так, щоб вони тримали під обстрілом усі поля дошки? 3
Якщо n човнів охороняють дошку, то або на кожній вертикалі, або на кожній горизонталі стоїть хоча б одна з них (якщо існуютьвертикаль і горизонталь, вільні від човнів, то поле, що знаходиться на їхньому перетині, не атаковане). Число розстановок i ладей по одній на кожній вертикалі дорівнює n n (першу туру можна поставити на одне з n полів першої вертикалі; другу, незалежно від першої, на одне з n полів другої вертикалі і т.д.). Стільки ж є розстановок і по одній на кожній горизонталі. На перший погляд здається, що загальна кількість розташування ладей дорівнює n n +n n =2n n . Однак за такого підрахунку двічі враховуються розстановки, в яких на кожній вертикалі та на кожній горизонталі стоїть по одній турі. Так як кожна з них характеризується тим, що жодна пара човнів не загрожує один одному, то розв'язанням задачі є число 2 n n - n!. Число розстановок восьми човнів, що обстрілюють звичайну дошку, дорівнює 2 · 8 8 - 8! = 33514312.
Комбінаторні завдання про розміщення атакуючих фігур не менш популярні, ніж завдання про розміщення мирних фігур. У наступних розділах ми розглянемо завдання й іншого типу кожної шахової фігури. Найбільш просто вони вирішуються для човна, мабуть, позначається її прямолінійність.
У завданнях про розміщення мирних човнів ми могли використовувати всю дошку. Припустимо тепер, що є ряд заборонених полів, на які човни ставити не можна. І тут встановлено такі цікаві факти. Якщо на кожній вертикалі та на кожній горизонталі дошки n ґ n є хоча б по два поля, доступні човнам, то існує не менше двох різних розстановок n мирних човнів. При цьому на дошці n×n можна розставити одночасно n білих човнів, що не атакують один одного, і n чорних, що володіють тією ж властивістю. Якщо кожна вертикаль і горизонталь дошки містить рівно два вільні поля (а всього на дошці 2n полів), то число розташування n мирних човнів дорівнює 2 b , де b Ј [n/2](квадратні дужки означають цілу частину числа).
Проілюструємо сказане з прикладу звичайної дошки (рис. 26,а). Кожна лінія дошки містить два дозволені поля, а інші є забороненими. Сукупність усіх 16 полів розбита на чотири квадрати 2 ґ 2, і в кожному з них можна поставити дві мирні човни одним з двох способів (a1, b2 або a2, b1 для лівого нижнього квадрата; c3, d4 або c4, d3 для наступного квадрата і і т.д.). Таким чином, всього є 2 b =2 4 =16 різних розташувань мирних човнів, а оскільки b n/2=4, це максимально можливе число. Найпростіше, діагональне розташування човнів дано на рис. 25. Мінімальний варіант представлений на рис. 26,б. Тут існують лише дві розстановки - одна діагональна, а в іншій тури займають всі поля, що лежать поза діагоналі.
У наступному завданні про тур (і короля) частина полів також є забороненою.
Нехай деякі поля дошки nґn заміновані таким чином, що король не може пройти з однієї крайньої вертикалі на іншу. Довести, що в цьому випадку тура може пройти з однієї крайньої горизонталі на іншу (з першою на останню) одним замінованим полям.
На рис. 27 заміновані поля дошки виділені чорною фарбою, і вони перегороджують королю шлях між крайніми вертикалями. Мостом, що складається з одних замінованих полів, тура може пройти з першої горизонталі дошки (поле b1) на останню (поле g8).
Досі ми мали справу з мирними човнами. У наступному завданні човни можуть загрожувати один одному, але більше одного нападу не дозволяється.
Яке найбільше число човнів можна розставити на дошці n ґ n так, щоб кожна з них знаходилася під ударом небільше однієї з решти?
Переконаємося, що вказаним чином можна розташувати трохи більше 4n/3 тур. Нехай на дошці розставлені до човнів, що задовольняють умову завдання. На всіх зайнятих човнами полях напишемо спочатку число 0, а потім з кожної з n вертикалей дошки зробимо наступну операцію. Якщо на ній стоять дві тури, то до числа на полях з турами додамо 1, а якщо стоїть одна тура, то додамо 2. Тепер таку ж операцію зробимо з кожною з n горизонталів дошки. У результаті кожному з k полів з турами буде написано число 3 чи 4, і тому сума s всіх чисел щонайменше 3k. З іншого боку, оскільки на кожній з n вертикалей та n горизонталів дошки ми додали не більше двох одиниць, s не більше 4n. Отже, 3k Ј s Ј 4n, звідки k Ј 4n/3. Таким чином, максимально можливе число човнів дорівнює [4n/3], причому ця оцінка є досяжною. Для n=8 маємо [4n/3]=10, і відповідне розташування десяти човнів показано на рис. 28,а (воно легко узагальнюється для будь-якого n). Розстановка десяти ферзей, що мають ту саму властивість - кожен з ферзів під ударом тільки одного іншого, показано на рис. 28,б. На відміну від човнів, для ферзей завдання у випадку не вирішена.
Повернемося до розстановок мирних човнів на шахівниці.
Нехай на кожному полі дошки записано твір номерів горизонталі та вертикалі, яким воно належить. Розставити вісім човнів, які не загрожують один одному, так, щоб сума чисел на полях, які вони займали, була найбільшою.
Човни слід розташувати вздовж головної діагоналі (див. рис. 25). Доведемо це від неприємного. Нехай у вирішенні є човни, що не стоять на головній діагоналі. Позначимо через i номер найпершої вертикалі з такою турою, а через p номер відповідноїгоризонталі; очевидно, p> i (рис. 29, а). Нехай j¦ номер вертикалі, на якій стоїть тура i-ї горизонталі. Ця тура також стоїть поза головною діагоналі і перебуває правіше першої, тобто. j > i. Переставимо дві ці човни, залишаючи на своїх вертикалях, поміняємо їх горизонталі. В результаті перша з цих човнів опиниться на i-й горизонталі (діагональне поле), а друга на p-й (рис. 29, б). Зрозуміло, що човни, як і раніше, не загрожують один одному.
Підрахуємо суми чисел для обох розташувань відповідні двом човнам, що перемістилися (на інші доданки перестановка не впливає). Для вихідної розстановки суми дорівнювала ip+ji, а для нової i 2 +jp. Так як j, p & gt; 1, то маємо
Таким чином, у другому випадку сума більша, а це суперечить припущенню про те, що вихідне рішення давало максимальну суму. По суті, ми тут використовували так званий перестановочний прийом, що зустрічається під час вирішення різних оптимізаційних завдань (наприклад, теоретично розкладів). Цей прийом полягає в наступному: передбачається, що деяке розташування об'єктів (порядок) є найкращим у тому чи іншому сенсі, а потім при перестановці об'єктів розташування покращується, тобто. виходить суперечність.
На 64 полях шахової дошки виписані поспіль числа від 1 до 64 (на першій горизонталі зліва направо від 1 до 8, на другій від 9 до 16 і т.д.). Поставимо на дошку вісім не загрожують один одному човнів. Які значення може набувати сума чисел на полях, зайнятих турами?
Число, що стоїть на i-й вертикалі і j-ї горизонталі можна записати так: i + 8 (j - 1) (i, j = 1, 2, , 8). Оскільки човни не загрожують один одному, на кожній вертикалі та горизонталі стоїть одна з них. Це означає, що сума, що шукається, дорівнює