Leprekon ovlama

İrlandiya mifologiyasında leprekon — göy qurşağının sonunda qızıldan dolu bir qazanda bütün xəzinələrini saxlayan kiçik bir ruhdur. Əgər kiminsə leprekonu tutmağa müvəffəq olarsa, leprekon öz qızıl qazanın vermək məcburiyyətindədir. Bu məsələdə leprekonu tutmağın nə qədər çətin olduğunu araşdırırıq.

Tutma prosesini $v$ kənd sakininin sadə istiqamətsiz qrafda bir leprekonu tutmağa çalışdığı bir oyun kimi modelləşdiririk. Oyun başında sakinlər təsadüfi $v$ müxtəlif köşələr tuturlar. Bundan sonra leprekon qalan köşələrdən birini başlanğıc mövqeyi kimi seçir. Hər bir növbəti raundda sakinlərdən biri indiki köşəsindən qonşu köşəyə gedə bilər, əgər ora başqa bir sakin tərəfindən tutulmayıbsa. Əgər bu köşədə leprekon mövcuddursa, sakinlər onun qızıl qazanın qazanırlar. Əks təqdirdə, leprekon ya yerində qala bilər, ya da boş bir qonşu köşəyə keçə bilər. Verilən qraf və sakinlərin sabit sayı üçün bizi leprekonu tutmaq üçün tələb olunan minimal gedişlərin sayı maraqlandırır.

Aşağıdakı şəkillərdəki nümunələri nəzərdən keçirək. Şəkil $1$-də bir sakin heç vaxt leprekonu tuta bilməz — leprekon ondan sonsuz qaçar. Lakin iki sakin maksimum $2$ gedişdə leprekonu tuta bilər. Məsələn, əgər sakinlər $A$ və $D$ köşələrində başlasalar, ağıllı leprekon başlanğıc mövqeyi kimi $F$-ni seçəcəkdir. Lakin $A$-dan gələn sakin $G$-yə keçdikdən sonra, növbəti gedişdə leprekon $F$-də qalarsa və ya $E$-yə keçərsə, mütləq tutulacaq.

Şəkil $2$-də bir sakin də leprekonu tuta bilməz. Niyə belə olduğunu anlamaq üçün leprekonun strategiyasını nəzərə alsaq: o həmişə $BCDE$ kvadratında qalıb, sakin kvadratda olsa, sakinlə əks köşəni tutar. Əgər sakin $A$-ya getmişdirsə, leprekon sadəcə yerində qalacaq. Lakin iki sakin məsələn $B$ və $E$ köşələrində başlanğıc mövqedə başlasalar, ilk gedişdə leprekonu tuta bilərlər.