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.
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.
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.
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 ⌈dla wystarczająco dużegom,n(powiedzmy,m,n≥C(p,q)), jak wyglądaC(p,q)?
źródło
Odpowiedzi:
Odpowiedź NIE dla wszystkich dużychm,n, np.P=6iq=3. Dlaczego? Zauważ, że z powodu reszty⌈mn2⌉ 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 + ymod3 m=n=100 ma sześć klas, które są w trzech parach, różnice między licznościami par wynoszą 1 , 1 , 2 ).x+ymod6 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
źródło