Розбиття чисел • Костянтин Кноп • Науково-популярні завдання на "Елементи" • Математика

Розбиття чисел

завдання

У лівому стовпчику таблиці виписані всі способи, якими можна записати число 7 у вигляді суми різних натуральних доданків ( "суворі розбиття"). У правому – всі способи, якими можна записати це ж число у вигляді суми непарних доданків ( "непарні розбиття").

суворі розбиттянепарні розбиття
7 = 77 = 7
7 = 6 + 17 = 5 + 1 + 1
7 = 5 + 27 = 3 + 3 + 1
7 = 4 + 37 = 3 + 1 + 1 + 1 + 1
7 = 4 + 2 + 17 = 1 + 1 + 1 + 1 + 1 + 1 + 1

нехай s(n) – кількість суворих розбиття числа n, а o(n) – кількість непарних розбиття. Доведіть, що s(n) = o(n).


Підказка 1

Щоб довести, що кількості елементів в двох множинах однакові, буває зручно встановити між ними взаємно-однозначна відповідність.


Підказка 2

Нехай є якесь розбиття на різні складові. З нього можна отримати розбиття на непарні складові, якщо кожне парне число розбивати на дві половинки до тих пір, поки не залишаться тільки непарні.

Приклад: 20 + 6 + 3 → 10 + 10 + 3 + 3 + 3 → 5 + 5 + 5 + 5 + 3 + 3 + 3.

А як по "непарному" розбиття отримати вихідне "суворе"? Ось це і є суть завдання …


Рішення

Затвердження завдання вперше було доведено Леонардом Ейлером близько 1740 року за допомогою виробляють функцій.

Леонард Ейлер (1707-1783). Портрет роботи Я. Е. Хандманна, 1753 р Зображення з сайту ru.wikipedia.org

Теорема Ейлера. Кількість розбиття числа N на попарно різні складові ( "суворі розбиття") дорівнює кількості розбиттів N на непарні складові ( "непарні розбиття").

У підказці був зазначений спосіб, що дозволяє отримати з будь-якого суворого розбиття непарне. Для цього кожне парне число, що входить в розбиття на різні складові, потрібно було розділити навпіл, тобто представити у вигляді суми двох рівних половинок. А потім повторювати цей процес до тих пір, поки парних чисел не залишиться.

Наприклад, з розбиття

75 = 18 + 15 + 13 + 9 + 8 + 7 + 4 + 1

вийде 15 + 13 + 93 + 7 + 113, Де верхні індекси означають зведення в ступінь, а кількість повторень доданка (тобто фактично є множником, але в математичній літературі про розбитті усталене саме таке позначення).

Щоб довести взаємну однозначність такого відповідності, тепер потрібно пояснити, як по непарному розбиття (наприклад, 15 + 13 + 93 + 7 + 113) Відновити вихідне суворе. З тими непарними числами, які зустрічаються лише один раз, все зрозуміло – вони були і в вихідному розбитті. А ось з чого вийшло 93? Так як число повторень непарній, то саме число 9 у разі необхідності розділення було. Крім нього, залишається ще 92, Яке могло бути отримано тільки з числа 18.Отже, ми відновили, що 93 ← (9, 18). Подібним же чином можна послідовно розібратися і з 113:

113 ← (1, 26) ← (1, 43) ← (1, 4, 42) ← (1, 4, 8).

Ви вже зрозуміли закономірність? Вона настільки ж проста, як і красива: кожен "показник ступеня" записується у вигляді суми різних ступенів двійки (тобто виписується його двійковий запис), після чого кожної з наявних ступенів відповідає своє доданок в вихідному "точний" розбитті. Це стає зовсім зрозумілим, якщо збагнути, що з одного парного доданка в строгому розбитті могли вийти тільки 2, 4, 8, 16 і т. Д. Непарних – тобто "внесок" кожного доданка в загальна кількість завжди є ступенем двійки, а так як рівних доданків немає, то все ступеня виявляються різними.

Джеймс Уітбред Лі Глейшер (1848-1928). Зображення з сайту ru.wikipedia.org

Це чудове відповідність було придумано в кінці XIX століття англійським математиком Джеймсом Уітбред Лі Глейшер (на жаль, його наукові результати в основному стосувалися областей математики, які не вивчаються ні в середній школі, ні навіть в нематематичних вузах, тому широкому загалу він абсолютно невідомий). Проте він був удостоєний двох дуже важливих математичних нагород свого часу – медалі де Моргана в 1908 році (це найвища нагорода Лондонського математичного товариства,присуджується раз на три роки) і медалі Сильвестра в 1913 році (вища нагорода Лондонського королівського товариства).

У задачі про непарних розбитті заслуга Глейшер в тому, що він придумав не тільки новий підхід до вирішення, але і дав чудове узагальнення завдання:

Теорема Глейшер. Кількість розбиття цілого числа N на частині, що не діляться на число d, дорівнює кількості розбиттів N на складові, в яких жодна частина не повторюється d або більше разів.


Післямова

Але розповідь про відповідності між непарними і строгими розбивками був би свідомо неповним без згадки іншого чудового відповідності між ними, придуманого Джеймсом Джозефом Сильвестром (тим самим, в честь якого названа згадана вище медаль).

Джеймс Джозеф Сильвестр (1814-1897). Зображення з сайту ru.wikipedia.org

Сильвестр був, мабуть, першим математиком, який досліджував розбиття чисел на складові за допомогою картатих картинок. Згодом ці картинки отримали назву "діаграми Юнга" або "діаграми Феррерс" в честь двох інших британських математиків, молодших сучасників Дж. Сильвестра.

Нехай є розбиття на непарні складові.Сильвестр пропонував намалювати діаграму, в якій цим доданком відповідають горизонтальні ряди (рядки), причому розташовувати ці ряди симетрично щодо центру (це можна зробити саме завдяки непарності всіх доданків, рис. 1). А для встановлення відповідності він розглядав "гаки", які на малюнку 1 зображені чергуються кольоровими рядами. Перший гак йде знизу по центральному ряду до верхнього рядка, а потім продовжується по цьому рядку вправо. Наступний гак – по сусідньому зліва ряду знову до верхнього рядка, а потім по першому рядку у крайнє ліве положення. Потім – знову гак справа, але вже до другого рядка, і так далі. У підсумку виходить вже знайоме нам по відповідності Глейшер розбиття (18, 15, 13, 9, 8, 7, 4, 1). Чи не правда, красиво? На жаль, настільки ж красивого зворотного відповідності Сильвестр не дав. Замість цього він просто привів алгебраїчне доказ того, що таке відповідність є взаємно-однозначним.

Мал. 1.

До слова, Сильвестр не обмежився одним новим відповідністю, а попутно в тій же роботі довів і кілька інших нових фактів про непарні і строгі розбиття. Зокрема, він виявив відповідність між непарними розбивками, що містять рівно k різних чисел, і розбиття на різні числа, що містять рівно k "Ланцюжків" – підпослідовностей з йдуть підряд натуральних чисел. Це привело його до наступній теоремі.

Теорема Сильвестра (1882). Кількість розбиття числа N на непарні частини, серед яких рівно k різних чисел, дорівнює кількості розбиттів N на різні частини, в яких зустрічаються рівно k ланцюжків.

Ясно, що вихідний результат Ейлера виходить в якості слідства з теореми Сильвестра – простим додаванням по всім k.

Однак математика не стоїть на місці, і гарне відповідність все-таки було знайдено, причому зовсім недавно, в самому кінці ХХ століття. Зробили це дві корейські математика Кім Донс і І Ечжа (в той момент другий з них був ще студентом, а нині він – професор в Університеті штату Пенсільванія). Я приведу картинку, взяту з їх статті A note on partitions into distinct parts and odd parts, і коротко прокоментую її, надаючи можливість читачеві самому додумати деталі.

Намалюємо картинку розбиття на різні частини, почавши з самих маленьких частин, тобто з одиниці: 1 + 4 + 7 + 8 + 9 + 13 + 15 + 18 (рис. 2). Якщо кількість частин непарній, то в якості найменшої частини додамо 0.Першу частину помістимо в перший рядок, другу – в рядок під нею, причому вирівнявши її по лівому краю першого рядка. Третю частину помістимо в третій рядок, але вирівняємо її з другим рядком по правому краю, і так далі, чергуючи вирівнювання по лівому і на правому краях. Так як всі частини різні, то в результаті все вертикальні краю (і ліві, і праві), крім останнього, будуть мати висоту 2.

Мал. 2.

Крім того, намалюємо жирну вертикальну риску – роздільник – на відстані від правого краю, рівному Знакозмінні сумі частин

d = 18 – 15 + 13 – 9 + 8 – 7 + 4 – 1 = 11.

Тоді всі стовпці правіше роздільник містять непарне число клітин (адже кожна вертикаль складається з однієї нижньої рядки і парного числа інших рядків) і можуть розглядатися як сума непарних доданків:

7 + 7 + 7 + 5 + 3 + 3 + 3 + 3 + 1 + 1 + 1

(Ці числа підписані в першому ряду під діаграмою, праворуч від роздільника). При цьому всі послідовні непарні числа від 1 до 7 зустрічаються хоча б один раз. Отже, до 1 можна додати число клітин в парі нижніх рядків зліва від роздільника (тобто 14), до 3 – число клітин в парі наступних рядків (10), до 5 – клітини з наступної пари (8), а до 7 – клітини останньої пари рядків (2). Ці складові підписані у другому рядку під діаграмою.Нарешті, в третьому рядку виписані суми першої та другої рядки – теж непарні, оскільки вся друга рядок складається з парних чисел. Ясно, що кожна клітина діаграми врахована рівно один раз – клітини правіше роздільник увійшли в доданки першого рядка. А клітини лівіше роздільник увійшли в доданки другого рядка. Тим самим ми отримали відповідність між різними складовими і непарними складовими, причому – те ж саме відповідність, яке було запропоновано Сильвестром.

А як побудувати зворотне відповідність? Метод Кіма – І тут багато в чому повторює спосіб Сильвестра, але виглядає, мабуть, навіть природніше.

Випишемо спадаючу послідовність з чисел непарного розбиття (a1 = 15, a2 = a3 = 13, a4 = 9, a5 = a6 = 7, a7 = a8 = a9 = 3, a10 = a11 = 1) і будемо від першого члена віднімати 1, від другого – 3, від третього – 5, і так далі до тих пір, поки різниці будуть позитивні. Тобто запишемо рівності 15 = 1 + 14, 13 = 3 + 10, 13 = 5 + 8, 9 = 7 + 2. Це відразу дасть нам потрібне розбиття третього рядка під діаграмою на першу і другу. Потім все числа першого рядка перенесемо в діаграму праворуч від роздільника, а кожне парне число другого рядка "укладемо" в два рядки зліва від роздільника. В результаті отримаємо діаграму, в якій нижня рядок буде найдовшою, а кожна наступна рядок буде коротше попередньої.Підсумовуючи клітини цієї діаграми по рядках, отримаємо розбиття на різні складові.

Результат Кіма – І – навіть при тому, що вони фактично просто переформулювали Сильвестра – використовує поняття роздільник, якого не було в оригіналі. А значить, теж дозволяє довести сильніший факт. Але дивно навіть не це, а те, що цей факт був відкритий на кілька років раніше, ніж з'явилася гарна картинка від корейців!

Теорема про розбиття на d непарних частин (М. Буську-Мело, К. Еріксон, 1997). Кількість розбиття числа N на попарно різні частини, які мають Знакозмінні суму d, дорівнює кількості розбиттів N на d непарних частин.


Like this post? Please share to your friends:
Залишити відповідь

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: