Полювання на лепреконів

В ірландській міфології лепрекон — це маленький дух, який зберігає всі свої скарби в прихованому горщику зі золотом на кінці веселки. Якщо комусь вдасться зловити лепрекона, той зобов'язаний віддати свій горщик із золотом. У цій задачі ми досліджуємо, наскільки складно зловити лепрекона.

Ми моделюємо процес затримання як гру, в якій $v$ сільських жителів намагаються зловити одного лепрекона на простому неорієнтованому графі з n \ge 1 + v вершинами. На початку гри жителі займають довільні $v$ різних вершин. Після цього лепрекон обирає одну з решти вершин як стартову позицію. У кожному наступному раунді один з жителів може перейти зі своєї поточної вершини в сусідню вершину, якщо вона не зайнята іншим жителем. Якщо в цій вершині знаходиться лепрекон, жителі виграють його горщик із золотом. Інакше лепрекон отримує можливість або залишитися на місці, або перейти в сусідню незайняту вершину. Для заданого графа і фіксованого числа жителів нас цікавить мінімальна кількість ходів, необхідних, щоб гарантовано зловити найхитрішого лепрекона.

Розглянемо приклади на рисунках нижче. На графі на Рисунку $1$ один житель ніколи не зможе зловити лепрекона — той буде безкінечно від нього втікати. Однак два жителі зможуть зловити лепрекона максимум за $2$ ходи. Наприклад, якщо жителі почнуть на вершинах $A$ і $D$, то хитрий лепрекон обере вершину $F$ як стартову. Але після того як житель з $A$ перейде в $G$, у наступному ході лепрекон буде зловлений незалежно від того, залишиться він на $F$ чи піде в $E$.

На графі на Рисунку $2$ один житель також не може зловити лепрекона. Щоб зрозуміти чому, розглянемо стратегію лепрекона: він завжди залишається всередині квадрата $BCDE$ і займає вершину, протилежну тій, в якій знаходиться житель, якщо той також у квадраті. Якщо ж житель піде в $A$, лепрекон просто залишиться на місці. Водночас два жителі можуть зловити лепрекона вже на першому ході, якщо почнуть, наприклад, на вершинах $B$ та $E$.