Zadanie drugie jest wbrew pozorom ciekawe, oczywiście „na zdrowy rozum” łatwo jest odpowiedzieć na pytania, ale trudniejszą sprawą jest sformalizowanie odpowiedzi.
Niech
\(\displaystyle{ p_{x,y}}\) oznacza pole o numerze kolumny
\(\displaystyle{ x}\) i wiersza
\(\displaystyle{ y}\). Numery kolumny wzrastają w prawo, numery wierszy wzrastają w dół (ważne!).
Goniec bije pierwszą napotkaną figurę po skosie w czterech kierunkach, gdyż nie może skakać (jak skoczek), zatem jedne figury przesłaniają inne. Załóżmy, że goniec stoi na polu
\(\displaystyle{ p_{x,y}}\). Gdyby goniec mógł skakać, mógłby bić wszystkie figury stojące na polach
\(\displaystyle{ p_{x+sk,\ y+s'k},}\)
\(\displaystyle{ k \in \NN_+ ,\ s,s' \in \left\{ -1,1\right\}}\). Ponieważ nie może skakać, bije najbliższą sobie figurę w każdym kierunku, czyli taką, dla której
\(\displaystyle{ k}\) jest najmniejsze. Przy okazji: może się wydać dziwne, że tworzę dwie zmienne przechowujące znak liczby, a właściwy offset chcę mieć dodatni, zamiast po prostu napisać
\(\displaystyle{ k \in \ZZ \setminus \left\{ 0\right\}}\) — wyjaśni się to poniżej.
Z tych rozważań wynika, że nasze wieże muszą po pierwsze znajdować się na linii bicia a po drugie jedna nie może przesłaniać drugiej, czyli każda z nich musi się znajdować „w innym kierunku bicia”. Oznaczmy pole pierwszej wieży
\(\displaystyle{ p_{x+s_1k_1,\ y+s_1'k_1}}\), zaś pole drugiej
\(\displaystyle{ p_{x+s_2k_2,\ y+s_2'k_2}}\). Wtedy, żeby spełnić nasze założenia,
\(\displaystyle{ \sgn s_1k_1 \neq \sgn s_2k_2 \ \vee \ \sgn s_1'k_1 \neq \sgn s_2'k_2}\). To jest jednak bardzo nieporadny zapis. Chcemy albo zanegować obydwie współrzędne albo jedną z nich. Powołajmy do życia nową zmienną,
\(\displaystyle{ s \in \left\{ -1,0,1\right\}}\), która to zmienna zdecyduje o tym, czy zanegować tylko współrzędną iksową (
\(\displaystyle{ s=-1}\)), igrekową (
\(\displaystyle{ s=1}\)) czy obie (
\(\displaystyle{ s=0}\)).
Potrzebujemy więc pomnożyć
\(\displaystyle{ s_1}\) przez funkcję, która zwróci następujące wartości:
\(\displaystyle{ \begin{cases} f(-1)=-1 \\ f(0)=-1 \\ f(1)=1 \end{cases}}\). Taką funkcją jest na przykład
\(\displaystyle{ f(s)=s^2+s-1}\).
Z kolei
\(\displaystyle{ s_1'}\) pomnożymy przez następującą funkcję:
\(\displaystyle{ \begin{cases} f(-1)=1 \\ f(0)=-1 \\ f(1)=-1 \end{cases}}\), czyli np.
\(\displaystyle{ f(s)=s^2-s-1}\).
Ostatecznie, aby wieże mogły być obie naraz bite przez gońca, muszą stać na polach:
\(\displaystyle{ p_{x+s_1k_1,\ y+s_1'k_1}}\)
\(\displaystyle{ p_{x+\left( s^2+s-1\right) s_1k_2,\ y+\left( s^2-s-1\right)s_1'k_2 }}\)
gdzie:
\(\displaystyle{ p_{x,y}}\) — pozycja gońca
\(\displaystyle{ x,y \in \left[ 1,n\right]}\)
\(\displaystyle{ k_1,k_2 \in \NN_+}\) — moduł z offsetu wieży pierwszej i drugiej
\(\displaystyle{ s_1,s_1' \in \left\{ -1,1\right\}}\) — znak offsetu poziomego i pionowego wieży pierwszej
\(\displaystyle{ s \in \left\{ -1,0,1\right\}}\) — zmienna umiejscawiająca wieżę drugą w jednym z trzech pozostałych kierunków bicia zgodnie z tabelą: (u góry wartości
\(\displaystyle{ s}\), po lewej kierunek, w którym musi się poruszyć goniec, by zbić pierwszą wieżę)
\(\displaystyle{ \begin{array}{c|c|c|c}
& -1 & 0 & 1 \\
\hline \nwarrow & \nearrow & \searrow & \swarrow \\
\hline \nearrow & \nwarrow & \swarrow & \searrow \\
\hline \searrow & \swarrow & \nwarrow & \nearrow \\
\hline \swarrow & \searrow & \nearrow & \nwarrow \\
\end{array}}\)
To jest odpowiedź na pytanie:
Czy zawsze można znaleźć pozycję dla białego gońca, by mógł atakować obydwie wieże jednocześnie? Jeżeli nie, co należy dodatkowo założyć o ułożeniu wież?
W następnym poście zapiszę obliczenia związane z tym:
Czy znając pozycję obu wież, możemy określić liczbę możliwych, szukanych pozycji gońca?
— bo to też ciekawe zważywszy na to, że w jednym przypadku, kiedy wieże będą stały „w rogu”, np. na polach G1 i H7, goniec po prostu nie zmieści się między nimi — co nie zostało uwzględnione powyżej.
