Научно-методически статии
ЗА ЕДНА ВРЪЗКА МЕЖДУ OEIS, ФЕСТИВАЛА НА МЛАДИТЕ МАТЕМАТИЦИ 2025 И АНИМАЦИОННАТА ПОРЕДИЦА „ФУТУРАМА“
https://doi.org/math2026-3-1-ocb
Резюме. Отправна позиция на статията е комбинаторна задача от Фестивала на младите математици 2025, изследваща максималния брой различни транспозиции, които могат да бъдат извършени върху дадена пермутация така, че началното разположение да бъде възстановено. Показана е връзка с редицата A011848 от Онлайн енциклопедията на целочислените редици (OEIS) и е доказано обобщение за максималната дължина на поредица от различни транспозиции, свързваща два елемента на симетричната група \(S_{n}\).
Ключови думи: математически състезания; инверсии в пермутация; четност на цикли в пермутация
1. Въведение
Едно от най-сериозните предизвикателства в четвъртия ден на старшата \({ }^{2}\) възрастова група на Фестивала на младите математици – София 2025 – беше описаната по-долу задача, мотивирана от анимационната поредица „Футурама”. Два частни случая на същата задача бяха дадени няколко дни по-рано във финала на младшата \({ }^{1}\) група на същия фестивал; те улавяха част от характернитеѝ моменти, без да дават насоки за индукционния подход в общия случай. Пълният вариант на задачата поражда редица от четни числа, която липсва в Онлайн енциклопедията на целочислените редици (OEIS). Тъй като при \(n \geq 4\) тя се явява удвоена на A011848 от OEIS (Sloane, 1996), съгласно политиката на OEIS вместо включванетоѝ като отделен обект в Енциклопедията беше предпочетено да бъдат обогатени свойствата на A011848.
2. Задачите
Задача 8, Финал, 6. – 7. клас, ФММ 2025. Всяко от \(n\) джуджета има по една шапка. То не се разделя с нея никога, освен ако не се запознае с друго джудже – в този случай двете джуджета си разменят шапките. След общо \(k\) размени се оказало, че всяко от джуджетата е с началната си шапка. Намерете най-голямата възможна стойност на \(k\), ако:
а) \(n=5 ; \quad\) б) \(n=6\).
Отговор: а) 10; б) 14.
Решение: Означаваме джуджетата с A, B, C, D,. . . и първоначалните им шапки – със съответните малки букви. Размяната се описва с имената на участниците в нея.
а) Пет джуджета образуват 10 ненаредени двойки, така че \(k \leqq 10\). За да видим, че \(k=10\), процедираме както следва, започвайки с началното състояние \(\mathrm{Aa}, \mathrm{Bb}, \mathrm{Cc}, \mathrm{Dd}\), Ee:
• Запознанствата AE, после AB, после BE водят до състоянието Ab, Ba, Cc, Dd, Ee.
• Запознанствата CE, после CD, после DE водят до състоянието Ab, Ba, Cd, Dc, Ee.
• Запознанствата AC, после BD водят до състоянието Ad, Bc, Cb, Da, Ee.
• Запознанствата AD, после BC водят до състоянието \(\mathrm{Aa}, \mathrm{Bb}, \mathrm{Cc}, \mathrm{Dd}\), Ee и сме готови.
б) Шест джуджета образуват 15 ненаредени двойки, така че \(k \leqq 15\). Ще докажем, че общият брой размени трябва да е четен. Наричаме двойка шапки „обърната“, ако шапката с по-предна буква е у това от двете джуджета, чиято буква е по-задна. Нека \(T\) е броят обърнати двойки; отначало \(T=0\). Всяка размяна променя четността на \(T\). В края \(T=0\), така че общият брой размени трябва да е четен и значи \(k \leqq 14\).
Ето пример с \(k=14\) :
• Запознайте AE, после AB, после BE; състоянието сега е \(\mathrm{Ab}, \mathrm{Ba}, \mathrm{Cc}\), Dd, Ee, Ff.
• Запознайте CE, после CD, после DE; състоянието сега е Ab, Ba, Cd, Dc, Ee, Ff.
• Запознайте BF, после BC, после CF; състоянието сега е \(\mathrm{Ab}, \mathrm{Bd}, \mathrm{Ca}\), Dc, Ee, Ff.
• Запознайте DF, после AD, после AF; състоянието сега е Ac, Bd, Ca, Db, Ee, Ff.
• Запознайте AC, после BD; състоянието сега е Aa, Bb, Cc, Dd, Ee, Ff и сме готови.
При това само джуджета E и F не са се запознали.
Задача 1, ден 4, 10-12, ФММ 2025. В един от епизодите на анимационната поредица „Футурама” има машина, в която влизат двама души и разменят съзнанията си. Машината не може да се ползва от кои да е две тела повече от веднъж. Да се намери максималният общ брой размени, които \(n \geq 4\) души могат да са извършили, ако в края всеки е с началното си съзнание.
Отговор: \(\tfrac{n(n-1)}{2}\) за \(n \equiv 0,1(\bmod 4), \tfrac{n(n-1)}{2}-1\) за \(n \equiv 2,3(\bmod 4)\)
Решение: Нека търсеният брой е \(F(n)\). Явно \(F(n) \leq \tfrac{n(n-1)}{2}\) заради броя двойки хора. Ще докажем, че \(F(n)\) е четно.
(Първи метод) В началото и в края броят независими цикли в пермутацията е \(n\). При размяна между хора от различни цикли двата цикъла се обединяват в един, а при размяна между хора от един цикъл той се разпада на два независими. Така при всяка размяна броят независими цикли променя четността си, следователно може да се върне в началното положение само след четен брой размени.
(Втори метод) Номерираме от 1 до \(n\) и хората, и съзнанията, така че в началното положение номерациите да съвпадат. Ще наречем двойка хора инверсни, ако този с по-преден номер притежава съзнание с по-заден номер, отколкото другия. Нека \(T\) е общият брой инверсни двойки; отначало \(T=0\). Размяна между хора със съседни номера променя \(T\) с 1. Всяка размяна може да се замени с нечетен брой размени между хора със съседни номера, така че променя четността на \(T\). В края \(T=0\), така че \(F(n)\) е четно.
С това оценката е доказана за всяко \(n\).
Първо ще построим пример за четните \(n \geq 4\) по индукция. Означаваме телата с главни букви, а първоначалните им съзнания – със съответните малки букви. Размяната се описва с означенията на участващите в нея тела.
База. Следният пример доказва \(F(4)=6\). Началното състояние е \(A a, B b, C c, D d\).
1. Разменете \(A B\), после \(C D\); състоянието сега е \(A b, B a, C d, D c\).
2. Разменете \(A C\), после \(B D\); състоянието сега е \(A d, B c, C b, D a\).
3. Разменете \(A D\), после \(B C\); състоянието сега е \(A a, B b, C c, D d\) и сме готови.
Стъпка. Нека \(n \geq 4\) се дели на 4 и хората \(P_{1}, P_{2}, \ldots, P_{n}\) могат да постигнат целта с \(\tfrac{n(n-1)}{2}\) размени. Добавяме нови двама, \(A\) и \(B\). Процедурата за множеството от \(n+2\) души е като тази за изходните \(n\) души със следните модификации:
• За нечетно \(k\) размяна от тип \(P_{k} P_{k+1}\) се заменя с поредицата от три размени \(A P_{k}\), после \(P_{k} P_{k+1}\), после \(P_{k+1} A\), която има същия ефект (в частност \(A\) е отново със своето съзнание).
• За четно \(k\) размяна от тип \(P_{k} P_{k+1}\) се заменя с поредицата от три размени \(B P_{k}\), после \(P_{k} P_{k+1}\), после \(P_{k+1} B\), която има същия ефект.
• Размените между несъседни хора в горната номерация се запазват.
В края началното състояние е възстановено и всяка двойка хора освен \(A B\) е извършила размяна. Това завършва конструкцията при \(n\) кратно на 4.
Нека сега \(n=4 m+2\) при \(m \geq 1\). Да допуснем, че \(P_{1}, P_{2}, \ldots, P_{4 m}, A, B\) могат да постигнат целта с \(\tfrac{n(n-1)}{2}-1\) размени, като липсва само размяната \(A B\). Добавяме нови двама – \(C\) и \(D\). Процедурата за множеството от \(n+2\) души е като тази за изходните \(n\) души със следните модификации:
• За нечетно \(k\) размяна от тип \(P_{k} P_{k+1}\) се заменя с поредицата от три размени \(C P_{k}\), после \(P_{k} P_{k+1}\), после \(P_{k+1} C\), която има същия ефект (в частност \(C\) е отново със своето съзнание).
• За четно \(k\) размяна от тип \(P_{k} P_{k+1}\) се заменя с поредицата от три размени \(D P_{k}\), после \(P_{k} P_{k+1}\), после \(P_{k+1} D\), която има същия ефект (номерацията на индексите е по модул \(n\) ).
• Накрая \(A, B, C, D\) правят 6 размени както при \(F(4)=6\).
• Всички останали размени – между несъседни хора при дадената номерация или между някой от \(A, B\) и някой от тип \(P_{k}-\) се запазват.
В края началното състояние е възстановено и всяка двойка хора е извършила размяна. Това завършва конструкцията при четно \(n\).
Сега преминаваме към конструкцията при нечетен брой хора. Нека \(n\) е четно и хората \(P_{1}, P_{2}, \ldots, P_{n}\) могат да постигнат целта с максимален брой размени, както е описано по-горе. Добавяме нов човек \(A\). Процедурата за множеството от \(n+1\) души е като тази за изходните \(n\) души със следните модификации:
• При нечетно \(k\) размяна от тип \(P_{k} P_{k+1}\) се заменя с трите размени \(A P_{k} ; P_{k} P_{k+1} ; P_{k+1} A\), която има същия ефект (в частност \(A\) е отново със своето съзнание).
• Всички размени между несъседни хора при дадената номерация се запазват.
В края началното състояние е възстановено и всяка двойка хора е извършила размяна, освен една двойка хора при \(n=4 m+2\).
3. Връзката с OEIS
Горната задача сочи, че при \(n \geq 4\) максималният брой допустими размени в описаната ситуация е
(∗) \[ 2\left\lfloor\tfrac{1}{2}\binom{n}{2}\right\rfloor=2\left\lfloor\tfrac{n(n-1)}{4}\right\rfloor . \]
Ако премахнем коефициента 2, получаваме A011848 от OEIS (Sloane, 1996), но трябва да установим как стои въпросът с малките естествени числа, които горните задачи не обхващат. Формулата (∗) дава стойност 0 при \(n=0,1,2\), докато при \(n=3\) стойносттаѝ е 2. Това съвпада с наблюденията с описаната комбинаторна постановка при \(n=0,1,2\) : или ходове са априори невъзможни, или (при \(n=2\) ) единственият възможен ход води до необратима ситуация. В контраст с това, при \(n=3\) нека началното състояние (в термините на решението на горната задача) е \(A a, B b, C c\). Можем да считаме без ограничение на общността, че първите две размени са \(A B\) и после \(A C\). След тях състоянието е \(A c, B a, C b\), Ba, Cb, при което \(A\) няма право на повече размени и ситуацията е необратима. Това показва, че при \(n=3\) максималният брой допустими ходове отново е 0, т.е. не съответства на (∗) . И така, с изключение на \(n=3,2\). А 011848 е най-големият възможен брой размени, които могат да бъдат извършени от \(n\) души съгласно правилата на машината за размяна на съзнания от поредицата „Футурама” (две тела могат да извършат най-много една размяна) по начин, че накрая всеки да има своето първоначално съзнание.
Прави впечатление дуалността на описания в задачата подход в сравнение с този в (Kortezov, 2021), който също описваше задача от национално състезание, породена от комбинаторен въпрос, свързан с човешката култура и генерираща редица от OEIS (Kortezov, 2011, 2021). Там формулата е подобна на (∗) , но с обръщане на „посоката” на скобката и е свързана с A054925 (Sloane, 2000). С други думи, двете редици си приличат по това, че се състоят от четни числа, различаващи се с не повече от 1 от съответните триъгълни числа (Sloane, 1973); разликата е в това дали (Sloane, 1973) мажорира, или минорира съответната редица. Това, че в единия случай в избрано създаване на нова редица (Kortezov, 2011), а в другия – обогатяване с ново свойство на известна редица (Sloane, 1996), се дължи единствено на случилата се междувременно промяна на политиката на OEIS по отношение утвърждаването на нови редици.
4. Едно обобщение
Нека са дадени естествено число \(n\) и две пермутации \(\pi, \sigma \in S_{n}\), като \(\pi\) („изходна пермутация”) съответства на някакво начално разположение на съзнанията на \(n\) души, а \(\sigma\) („целева пермутация”) – на разположение, към което се стремим. Започвайки от \(\pi\), достигаме до \(\sigma\) с поредица от транспозиции, съответстващи на размени на съзнанията между различни двойки хора (всяка транспозиция може да се ползва най-много веднъж в поредицата). Ще покажем, че ако \(n \neq 3\), то максималната дължина на такава поредица от транспозиции е \(\binom{n}{2}\), ако \(\pi\) и \(\sigma\) имат еднаква четност, а в противен случай е \(\binom{n}{2}-1\). Досегашното изложение съответства на ситуацията \(\pi=\sigma=\mathrm{id}\). Твърдението остава в сила и при \(n=3\), освен в случая \(\pi=\sigma\) (когато, в съответствие с казаното по-рано, дължината на тази поредица е 0).
Твърдение 1. Нека \(n=3\). Ако \(\pi \neq \sigma\), то с 2 или 3 размени от \(\pi\) може да се получи \(\sigma\).
Доказателство. Нека \(\pi=\left(a_{1}, a_{2}, a_{3}\right)\). Има два случая:
• Ако в \(\sigma\) едно от съзнанията е у същия човек като в \(\pi\), то без ограничение на общността \(\sigma=\left(a_{1}, a_{3}, a_{2}\right)\). В такъв случай разменяме (1, 3) , после (2, 3) и накрая (1, 2) – наистина, така получаваме последователно разположенията \(\left(a_{3}, a_{2}, a_{1}\right),\left(a_{3}, a_{1}, a_{2}\right)\) и \(\left(a_{1}, a_{3}, a_{2}\right)\). • Ако в \(\sigma\) никое от съзнанията не е у същия човек като в \(\pi\), то без ограничение на общността \(\sigma=\left(a_{2}, a_{3}, a_{1}\right)\). В такъв случай разменяме \((1,2)\) и после \((2,3)\)– наистина, така получаваме последователно разположенията \(\left(a_{2}, a_{1}, a_{3}\right)\) и \(\left(a_{2}, a_{3}, a_{1}\right)\).
Твърдение 2. При \(n=4\) от \(\pi\) може да се получи \(\sigma\) с 5 или 6 размени. Доказателство. Нека \(\pi=\left(a_{1}, a_{2}, a_{3}, a_{4}\right)\). Има два случая:
• Ако \(\sigma=\pi\), то използваме конструкцията от Задача 2.
• Ако в \(\pi\) има съзнание \(a_{p}(1 \leq p \leq 4)\), което в \(\sigma\) трябва да се озове у човек \(q \neq p\), то извършваме размени на човека \(q\) с тримата други, като последната от тези размени е с човека \(p\)– така съзнанието \(a_{p}\) вече е у \(q\) и всички размени на \(q\) са вече извършени. Сега прилагаме Твърдение 1 за останалите трима (можем, тъй като поне един от тях не е с целевото си съзнание) – така с още 2 или 3 размени достигаме до целевата пермутация.
Алтернативно доказателство без използване на Твърдение 1. Нека \(\pi=\left(a_{1}, a_{2}, a_{3}, a_{4}\right)\). Ако \(\sigma=\pi\), то извършваме последователно размените \(\{(1,2),(3,4)\},\{(1,3),(2,4)\},\{(1,4),(2,3\})\). Ако точно две от съзнанията в \(\sigma\), без ограничение на общността \(-a_{3}, a_{4}\), не са на началните си места, то извършваме всички горни операции без \((3,4)\) (Фиг. 1).
Фигура 1. Размени, когато точно два върха не са на началните си места
Ако точно три от съзнанията не са на началните си места, то без ограничение на общността \(\sigma=\left(a_{1}, a_{3}, a_{4}, a_{2}\right)\). Правим последователно размените \((1,3)\), \((2,3),(2,4),(1,2),(1,4)\)– с пет размени получаваме пермутация, в която \(a_{2}\) и \(a_{3}\) са разменени. След това завършваме с шестата размяна \((3,4)\) (Фиг. 2).
Фигура 2. Размени, когато точно три върха не са на началните си места
Нека точно четири от съзнанията не са на началните си места. Ако \(\sigma\) се получава само от две независими размени, например (\(a_{2}, a_{1}, a_{4}, a_{3}\) ) , то прилагаме размени \((1,3),(3,2),(4,2),(1,2),(1,4),(3,4)\) (Фиг. 3).
Фигура 3. Размени, ако крайните позиции на съзнанията са две разменени двойки
В противен случай трябва съзнанието \(a_{i}\) да отиде на позиция \(j, a_{j}\) да отиде на позиция \(k, a_{k}\) на позиция \(l\) и \(a_{l}\) на позиция \(i\), където \(\{i, j, k, l\}=\) \(\{1,2,3,4\}\). Правим размените \((j, l),(j, k),(j, i)\), след които \(a_{i}\) е в човек \(j\) и никое от останалите не си е на мястото. С две от останалите размени можем да поставим трите съзнания на целевите им места. На фиг. 4 е показано това за \(\sigma=\left(a_{4}, a_{1}, a_{2}, a_{3}\right)\).
Фигура 4
Твърдение 3. Ако \(n \geq 4\) и \(\pi, \sigma \in S_{n}\), то \(\sigma\) може да се достигне от \(\pi\) с поредица от \(\binom{n}{2}\) или \(\binom{n}{2}-1\) различни транспозиции (всяка транспозиция може да се ползва най-много веднъж в поредицата).
Доказателство. Ако \(\sigma=\pi\), то действаме като в Задача 2. Нека \(\sigma \neq \pi\). При \(n=4\) използваме Твърдение 2. Нека \(n \gt 4\) и твърдението е вярно за \(n-1\) души. Ако в \(\pi\) има съзнание \(a_{p}(1 \leq p \leq n)\), което в \(\sigma\) трябва да се озове у човек \(q \neq p\), то извършваме размени на човека \(q\) с всички останали, като последната от тези размени е с човека \(p\)– така съзнанието \(a_{p}\) вече е у \(q\) и всички размени на \(q\) са вече извършени. Множеството от съзнания \(A=\{1,2, \ldots, n\} \backslash\left\{a_{p}\right\}\) у останалите хора е това, което трябва да бъде в \(\sigma\). Прилагайки индукционната хипотеза за \(A\), можем с \(\binom{n-1}{2}\) или \(\binom{n-1}{2}-1\) размени да достигнем до разположението, необходимо за \(\sigma\). Тъй като \(\binom{n-1}{2}+(n-1)=\binom{n}{2}\), то броят на размените е \(\binom{n}{2}\) или \(\binom{n}{2}-1\).
Теорема. Нека \(n\) е естествено число и \(\pi, \sigma \in S_{n}\). Максималната дължина на поредица от различни транспозиции, водеща от \(\pi\) до \(\sigma\), e най-голямото цяло число, което не надхвърля \(\binom{n}{2}\) и има същата четност като общия брой инверсии в \(\pi\) и в \(\sigma\), освен ако \(n=3\) и \(\pi=\sigma\), когато тази дължина е 0.
Доказателство. При \(n=1\) и \(n=2\) твърдението е тривиално вярно. При \(n=3\) то следва от Твърдение 1 поради основния факт, че всяка транспозиция променя броя на инверсиите в пермутацията с нечетно число. При \(n \geq 4\) то следва от Твърдение 3 с приложение на същия основен факт.
5. Изучаване на темата чрез софтуер
В процеса на писането на статията, в системата „СтруниМа“ (https:// strunima.valkovbg.com/play-in-browser/) се разработи и тема, която обхваща основната задача и нейното обобщение. Това включва възможност за самостоятелно разглеждане на задачата, нива за време и обучителна тема, която преминава през случаите \(n=3,4,5,6,7\). Изследването може да се направи и в темата „Графи и вериги” – да се направи конструкция (Фиг 5.), състояща се от няколко номерирани точки („върхове”) и същия брой номерирани поставки, които играят ролята на позиции в пермутация. Оттук при избoр на Свързване → Размяна от падащите менюта, при размяна двете точки анимирано си разменят местата и се чертаят отсечки между съответните поставки (броят на отсечките е равен на броя на направените размени между поставките).
Фигура 5. Симулация на размени в „СтруниМа“
Има падащо меню, от което да се избира и броят на точките, участващи в размяната – циклично се преместват точките по реда им на избиране (Фиг. 6).
Фигура 6. Менюта и бутони, нужни за достигане до конфигурация с размени
При нивата за време (Фиг. 7) се дава разместване на върховете върху поставки, при което с даден брой размени трябва да се достигне до положение на върховете, при което всеки връх е на поставката с неговия номер – върховете върху две поставки с номера \(i\) и \(j\) могат да се разменят ограничен брой пъти (в този случай не повече от веднъж). Тук можем да видим ситуация, при която имаме 20 направени размени със 7 върха, които са в началното си положение, използвайки решението на задача 2 (Фиг 8.).
Фигура 7. Състезателно ниво върху задачата със седем върха (съзнанията)
Фигура 8. Двадесет направени размени, така че всеки от върховете (съзнанията) е на началното си място
Обучителната тема може да се намери в Графи и вериги → Научи → Разместване – пермутации с размени – тук се разглеждат случаите за \(n=3,4,5,6,7\), както и инвариантът от Задача 2, обяснен с пример (размяна на две съзнания на хората сменя четността на броя на инверсиите).
6. Заключение
Разгледаните задачи показват как състезателна комбинаторна постановка, породена от елемент на популярната култура, естествено води до изследване на структурата на симетричните групи и до поява на числова редица от OEIS. Централна роля играе инвариантът, свързан с четността на инверсиите, който определя възможната максимална дължина на поредица от различни транспозиции. Получената теорема обобщава конкретната състезателна задача до достижимост между произволни две пермутации при ограничение за еднократно използване на всяка транспозиция.
NOTES
1. ФММ, 2025. Фестивал на младите математици – Математически боеве, https://klasirane.com/competitions/IFYM/1-6-7
2. ФММ, 2025. Фестивал на младите математици – Математически боеве, https://klasirane.com/competitions/IFYM/3-10-12
REFERENCES
Evans R., L. Huang, T. Nguyen (2012). Keeler’s theorem and products of distinct transpositions, arXiv:1204.6086
Evans R., L. Huang (2014). Mind switches in Futurama and Stargate, arXiv:1209.4991
Kortezov, I. (2011). Sequence A192447. In: N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. , OEIS Foundation Inc.
Kortezov, I. (2021). A Combinatorial Question Related to an Easter Tradition Led to a New Entry in OEIS. Математика и Информатика, 64, 2, Национално издателство "Аз-буки", ISSN: 1310–2230 (Print), pp. 222 – 225
Sloane, N. J. A. (1973). Sequence A000217. In: N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. , OEIS Foundation Inc.
https://oeis.org/A000217
Sloane, N. J. A. (1996). Sequence A011848. In: N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. , OEIS Foundation Inc.
https://oeis.org/A011848
Sloane, N. J. A. (2000). Sequence A054925. In: N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. , OEIS Foundation Inc.
https://oeis.org/A054925