Симетрія й інваріанти

Ідея: Шукайте те, що не змінюється

Коли порядків ходів забагато для перебору, шукайте величину, яку не змінює жоден хід.

• Кожен хід: $a+b$ зникає, $a+b-1$ з’являється
• Тож сума на дошці падає на $1$ за хід
• Порядок ходів не має значення

Приклад: Стерти й замінити

Запишіть числа від $1$ до $10$. Раз у раз стирайте $a$ і $b$ та пишіть $a+b-1$. Яке число лишиться?

1. Кожен хід зменшує суму на $1$
2. Ходів: $10-1=9$; початкова сума $55$
3. Останнє число: $55-9=46$

Ідея: Кого перевіряти першим

Перевіряйте кожного кандидата на одному ході, записаному літерами, а не числами.

• Суму або суму з відомим зсувом за хід
• Парність суми чи кількості
• Добуток після зсуву на кшталт $x+1$ або остачу

Швидка перевірка: Правило з добутком

На дошці $1$, $2$, $3$; хід замінює $a$ і $b$ на $a+b+ab$. Яке число лишиться?

Формула: Пари, ідея Гаусса

$1+2+\cdots +n=\frac{n(n+1)}{2}$

Запишіть ряд уперед і назад: кожен стовпчик має ту саму суму. Кількість членів на середнє крайніх.

Типова помилка: Останній мінус перший

Рахувати членів від $13$ до $27$ як $14$. Така похибка зсуває всю суму на середнє.

Натомість Рахуйте останній мінус перший плюс один: $27-13+1=15$ членів, сума $15\times 20=300$.

Приклад: Фішки 3 кольорів

$10$ червоних, $13$ зелених, $18$ синіх. Хід перетворює $2$ фішки різних кольорів на третій колір. Яким кольором можуть стати всі?

1. Хід змінює кількості на $-1$, $-1$, $+2$: різниці змінюються на $0$ або $3$
2. Червоні мінус зелені: $10-13=-3$, кратне $3$
3. Червоні мінус сині $10-18=-8$, зелені мінус сині $13-18=-5$: лише всі сині

Ідея: Симетрія виграє ігри

Гравці по черзі кладуть однакові монети на круглий стіл; хто не може покласти, програє.

• Перший гравець займає точний центр
• Далі віддзеркалює кожен хід через центр
• Дзеркальне місце завжди вільне, тож суперник вичерпується першим

Ідея: Спершу назвіть інваріант

Скажіть «сума падає на $1$ за хід» або «добуток $x+1$ незмінний» до будь-яких обчислень.

• Потім назвіть початкове значення
• Потім кількість ходів
• Так ви розв’язуєте кожну версію задачі, а не лише цю