Idealne dopasowania na szachownicy?

Zastanów się nad problemem znalezienia maksymalnej liczby rycerzy, którzy mogą zostać postawieni na szachownicy bez atakowania się dwóch z nich. Odpowiedź brzmi 32: nie jest zbyt trudno znaleźć idealne dopasowanie (wykres wywołany ruchami rycerza jest dwustronny, i istnieje idealne dopasowanie dla planszy 4 × 4), co jest oczywiście minimalną osłoną krawędzi. Nie jest również trudne udowodnienie, że odpowiedź brzmi dlaszachownicym×nza każdym razem,gdym,n≥3: wystarczy pokazać dopasowania dla3≤m,n≤6i wykonać trochę pracy indukcyjnej.$\left\lceil \frac{mn}{2} \right\rceil$$m \times n$$m,n \geq 3$$3 \leq m,n \leq 6$

Z drugiej strony, gdyby szachownica była toroidalna, a były parzyste, dowód nie wymagałby nawet pokazywania dopasowania dla małych plansz: mapa ( x , y ) → ( x + 1 , y + 2 ) ma tylko cykle o równej długości, więc musi być idealnie dopasowane.$m, n$$(x, y) \rightarrow (x+1, y+2)$

Czy istnieje jakiś odpowiednik prostokątnych szachownic, tj. Czy istnieje prostszy sposób, aby pokazać to dla wystarczająco dużych zawsze istnieje idealne dopasowanie szachownicy? W przypadku dużych desek deska prostokątna i toroidalna są prawie równoważne w tym sensie, że ułamek brakujących krawędzi dochodzi do zera, ale nie znam żadnych wyników teoretycznych, które gwarantowałyby idealne dopasowanie w takim przypadku.$m, n$

Co jeśli zamiast skakać w dowolnym kierunku, rycerz skoczył ( 2 , 3 ) kwadraty w dowolnym kierunku? A może, ( p , q ) kwadraty, z p + q nieparzystym i p , q coprime? Jeśli nie jest to prosty sposób na udowodnienie, że odpowiedź jest $(1, 2)$$(2, 3)$$(p, q)$$p+q$$p, q$dla wystarczająco dużegom,n(powiedzmy,m,n≥C(p,q)), jak wyglądaC(p,q)?$\left\lceil \frac{mn}{2} \right\rceil$$m, n$$m, n \geq C(p, q)$$C(p, q)$

Odpowiedź NIE dla wszystkich dużychm,n, np.P=6iq=3. Dlaczego? Zauważ, że z powodu reszty$\lceil \frac{mn}2\rceil$$m, n$$p=6$$q=3$ teraz wykres jest (rozłącznym) połączeniem trzech dwudzielnych grafów i z każdego możemy wybrać większą połowę. Na przykład, jeśli m = n = 100 , to w ten sposób możemy umieścić (co najmniej) 5002 rycerzy. (Jest tak, ponieważ x + $\mod 3$$m=n=100$ ma sześć klas, które są w trzech parach, różnice między licznościami par wynoszą 1 , 1 , 2 ).$x+y \mod 6$$1,1,2$

Nie wiem, co się stanie, jeśli dodamy warunek, że i q są liczbami względnymi. (Zauważ, że oprócz dzielnika 2 jest to równoważne z p + q i p - q będącymi liczbami względnymi, w rzeczywistości jest to warunek, którego potrzebujemy i który pokazuje również, że p + q jest nieparzyste.)$p$$q$$p+q$$p-q$$p+q$