Зеник розіб’є k задач на 2, а n−k задач він не змінюватиме, отже в нього буде (2⋅k)+(n−k)=n+k задач. Тому в задачі достатньо перевірити чи це число не більше ніж 26.
Одним із розв’язків x2i+y2i=2⋅(a2i+b2i) є xi=ai−bi та yi=ai+bi.
Переконаємось у правильності цього розв’язку: x2i+y2i=(ai−bi)2+(ai+bi)2=a2i−2⋅ai⋅bi+b2i+a2i+2⋅ai⋅bi+b2i=2⋅(a2i+b2i).
Оскільки нам необхідно знайти пару xi,yi≥0, тому візьмемо xi=|ai−bi|, що не змінює правильність розв’язку.
Розглянемо декілька станів гри:
a=b — в такому стані виграє другий, бо він завжди може зробити симетричний хід і повернутись до цього ж стану, але з меншою кількістю камінців і стан a=b=0 програшний.
a>b — перший гравець може зробити дві купки рівні і тоді другий гравець буде у програшному стані
a<b та b−a≤⌊b2⌋ — у цьому стані першому необхідно забрати b−a камінців з купки другого. Перший гравець може забрати не більше ніж ⌊b2⌋, отже він зможе зробити дві купки рівними.
a<b та b−a>⌊b2⌋ — у цьому стані по аналогії до попереднього випадку перший гравець не зможе своїм першим ходом зробити дві купки рівні, після його ходу буде і надалі виконуватись умова a<b. Тобто перший перейде у такий стан в якому другий має виграшну стратегію, аналогічно до другого випадку.
Узагальнюючи усі умови можна сказати, що перший гравець виграє якщо 2a≥b та a≠b.
У рівнянні f(k)=m ми знаємо, що існує p таке, що k+p=m та k ділиться на p, отже і m теж ділиться на p. Отже, кандидатами на розв’язок є числа k=m−p, де p є простим дільником m. Для того аби мати хоча б n кандидатів на розв’язок, необхідно аби число m містило хоча б n різних простих.
Тому розглянемо число m=2⋅3⋅5⋅... — добуток перших n>1 простих чисел. Це число є найменшим числом, для якого рівняння f(k)=m має хоча б n кандидатів на розв’язок.
Розглянемо один із його простих дільників p, тоді доведемо, що f(m−p)=m. Для цього нам потрібно довести, що немає такого простого дільника q<p, що m−p ділиться на q. Припустимо, що такий дільник існує, оскільки ми вибрали число m як добуток перших n простих чисел, то й серед цих простих чисел є q. Отже, q∣m, оскільки p просте то q∤p, отже q∤(m−p). Отримали суперечність, отже ми довели що f(m−p)=m, оскільки різних p є n отже рівняння f(k)=m має хоча б n розв’язків.
Будемо шукати відповідь у вигляді рівнобедреного трикутника.
Для пошуку рівнобедреного трикутника використаємо двійковий пошук кута між двома рівними сторонами трикутника 2⋅α, у випадку α=0 (вироджений трикутник) відношення rP дорівнює нулю, а у випадку α=30∘ (рівносторонній трикутник) відношення максимальне. Отже, нам усього лише необхідно вивести формулу відношення — f(α).
P=2⋅r⋅ctg(α)+4⋅r⋅ctg(45∘−α2)⟹rP=(2ctg(α)+4ctg(45∘−α2))−1.
Графік цієї функції зображено на рисунку. Бачимо, що функція монотонна, отже можна скористатися двійковим пошуком.
Якщо в несправедливій шерензі залишити тільки числа більші за деяке число x, то шеренга залишиться несправедливою для будь-якого x.
Розглянемо вигляд шеренги якщо залишити усі числа строго більші за x, нехай таких чисел k. Після цього подивимось, скільки є способів вставити числа, що рівні x у цю шеренгу. Для чисел x є k+1 позиція, куди їх можна вставити.
Назвемо числа y з шеренги, що задовольняють y<2x малими.
У несправедливій шерензі не могли стояти поруч два малих числа, бо тоді вони б порушували умову несправедливості.
Число x не можна ставити в шеренгу поруч (ні ліворуч, ні праворуч) з малим числом, бо знов тоді порушимо умову несправедливості.
Позначимо кількість малих чисел s. Залишається k+1−2s позицій, куди можна вставити числа x, бо кожне мале число забороняє дві позиції: ліворуч і праворуч від себе.
Нехай p — кількість чисел x, які потрібно вставити.
Ми вибираємо p з k+1−2⋅s позицій Cpk+1−2s способами.
Зауважимо, що ця формула не залежить від розташування чисел у шерензі, отже відповідь буде рівна добутку значень Cpk+1−2s для всіх можливих x.
Почнімо з простішої версії. Розглянемо випадок, коли n і m парні. Тоді ми можемо розділити нашу кімнату на ділянки з розміром 2×2, і замостити кожну таку ділянку. Для того щоб замостити ділянку з розміром 2×2 можна поставити по одному L-троміно кожного з чотирьох типів. Тоді кожна клітинка буде покрита тричі.
Тепер розглянемо випадок, коли n або m непарне. Без втрати загальності вважатимемо, що n — непарне. Тоді ми можемо розділити кімнату на дві частини з розмірами 3×m та (n−3)×m. Оскільки n непарне, то (n−3) парне, отже ми можемо покрити частину з розміром (n−3)×m описаним раніше способом. Щоб покрити ділянку з розміром 3×m, розділимо її на частини з розміром 3×2. Покрити таку частину можна двома L-троміно. Оскільки клітинки з іншої частини ми покрили тричі, то частинки з розміром 3×2 потрібно також покрити тричі.
Тепер перейдімо до складнішої версії. Єдиний випадок, який ми ще не розглянули, коли n і m непарні. Зауважимо, що кімнату з розміром 7×7 можна покрити так:
Тут поле 2×2 покриваємо описаним раніше способом, а кожну іншу L-троміно ставимо тричі.
Тоді можна розділити нашу кімнату на частини з такими розмірами: 7×7, (n−7)×7, 7×(m−7) та (n−7)×(m−7). Зауважимо, що n−7 та m−7 парні, тому ми зможемо покрити кожну з частин.