Funny Gnomish Hockey#12827

Funny Gnomish Hockey (Розбір)

Ігор Баренблат

Позначимо через кількість шайб на полі, а через та розміри поля.

Помітимо, що при min(n,m)>1 та p\ge 3 відповідь "yes". Доведення цього предсталено нижче (див. Лемму 4). Для випадків min(n,m)=1 та/або p\le 2 можна скористатись пошуком по всім можливим станам поля з складністю O(C_{n\cdot m}^p\cdot p\cdot (n+m)). Також розв'язати ці випадки можна аналітично зі складністю O(n\cdot m).

Лемма 1. При фіксованих n,m,p та фіксованому розміщенні елементу «g» таких, що min(n,m)=2 та p=2, існує універсальна стратегія досягнення позитивного результату яка не залежить від початкового розміщення шайб на полі.

Не обмежуючи загальності вважатимемо що n=2.

Побудуємо стратегію досягнення позитивного результату незалежно від розміщення елементу «g»:

  • Штовхаємо шайбу1 вверх, шайбу2 вниз, шайбу1 вліво, шайбу2 вліво. Тепер обидві шайби знаходяться у першому стовпчику. Вважатимемо що шайба1 знаходиться у лівому верхньому кутку поля, шайба2 у лівому нижньому кутку поля.

  • Виконаємо (m-1) разів наступну комбінацію кроків: штовхаємо шайбу2 вправо, шайбу2 вверх, шайбу2 вліво, шайбу2 вниз, шайбу2 вверх, шайбу1 вниз, змінюємо номери шайб (шайба1 стає шайбою2, а шайба2 стає шайбою1).

Лемма 2. При фіксованих n,m,p та фіксованому розміщенні елементу «g» таких, що min(n,m)\ge 3 та p=3, існує універсальна стратегія досягнення позитивного результату яка не залежить від початкового розміщення шайб на полі.

А) Елемент «g» розміщено на границі поля. Не обмежуючи загальності вважатимемо що елемент «g» розміщено у першому рядку поля. Побудуємо стратегію досягнення позитивного результату:

  • Тричі виконаємо наступну комбінацію кроків: штовхаємо шайбу1 вниз, шайбу2 вниз, шайбу3 вниз. Тричі виконаємо наступну комбінацію кроків: обираємо найвищу, а серед таких найлівішу, шайбу серед тих, що ще не були обрані за цим принципом, і штовхаємо її спочатку вліво а потім вверх. Тепер всі три шайби знаходяться у перших трьох клітинках першого стовпчика поля. Вважатимемо що шайба1 знаходиться у лівому верхньому кутку поля, шайба2 у другій клітинці першого стовпчика поля, шайба3 у третій клітинці першого стовпчика поля.

  • Виконаємо (m-1) разів наступну комбінацію кроків: штовхаємо шайбу2 вправо, шайбу2 вверх, шайбу2 вліво, шайбу1 вниз, змінюємо номери шайб з номерами 1 та 2 (шайба1 стає шайбою2, а шайба2 стає шайбою1).

Б) Елемент «g» розміщено не на границі поля. Побудуємо стратегію досягнення позитивного результату:

  • Тричі виконаємо наступну комбінацію кроків: штовхаємо шайбу1 вниз, шайбу2 вниз, шайбу3 вниз. Тричі виконаємо наступну комбінацію кроків: обираємо найвищу, а серед таких найлівішу, шайбу серед тих, що ще не були обрані за цим принципом, і штовхаємо її спочатку вліво а потім вверх. Тепер всі три шайби знаходяться у перших трьох клітинках першого стовпчика поля. Вважатимемо що шайба1 знаходиться у лівому верхньому кутку поля, шайба2 у другій клітинці першого стовпчика поля, шайба3 у третій клітинці першого стовпчика поля.

  • Штовхаємо шайбу3 вниз, шайбу3 вправо, шайбу3 вверх, шайбу3 вліво, шайбу3 вниз.

  • Допоки шайба3 знаходиться з елементом «g» у різних рядках виконуємо наступну комбінацію кроків: штовхаємо шайбу2 вправо, шайбу2 вверх, шайбу2 вліво, шайбу2 вниз, змінюємо номери шайб з номерами 2 та 3 (шайба2 стає шайбою3, а шайба3 стає шайбою2).

  • Штовхаємо шайбу1 вправо, шайбу2 вправо, шайбу2 вверх.

  • Виконаємо (m-3) разів наступну комбінацію кроків: допоки шайба2 знаходиться у різних рядках з шайбою3 штовхаємо шайбу1 вліво, шайбу1 вниз, шайбу1 вправо, шайбу1 вверх, змінюємо номери шайб з номерами 1 та 2 (шайба1 стає шайбою2, а шайба2 стає шайбою1); коли шайба2 опинилась у одному рядку з шайбою3 штовхаємо шайбу1 вверх, шайбу2 вліво, шайбу3 вниз, шайбу3 вправо, шайбу3 вверх, змінюємо номери шайб з номерами 2 та 3 (шайба2 стає шайбою3, а шайба3 стає шайбою2).

Лемма 3. При існуванні універсальної стратегії досягнення позитивного результату на полі фіксованого розміру з фіксованим розміщенням елементу «g» яке містить шайб, завжди існує універсальна стратегія S' на полі такого ж розміру з таким самим розміщенням елементу «g» що містить p' шайб, де p\le p'.

Доведемо для деякого фіксованого p' такого, що p\le p'. Для почачтку оберемо будь-який набір що містить шайб — позначимо ці шайби «видимими», відповідно всі інші (p'-p) шайб позначимо «невидимими». Будемо виконувати кроки стратегії один за одним, вважаючи що поточний набір видимих шайб є набором шайб для виконання плану стратегії — таким чином ми побудуємо стратегію S'. На кожному кроці стратегії ми обиратимемо деяку видиму шайбу та штовхатимемо її у певному напрямку. Якщо ця шайба вдаряється у стіну або у іншу видиму шайбу то очевидно інваріант стратегії S' валідний. Якщо шайба вдаряється у деяку невидиму шайбу то «змінимо їх видимості» — та видима шайба що зупиняється при зіткненні стає невидимою, а шайба що починає рухатись після зіткнення стає видимою. Очевидно що в цьому випадку інваріант стратегії S' теж валідний.

Лемма 4. При фіксованих n,m,p та фіксованому розміщенні елементу «g» таких, що min(n,m)>1 та p\ge 3 існує універсальна стратегія досягнення позитивного результату яка не залежить від початкового розміщення шайб на полі.

З Лемм 1, 2, 3 очевидно.