Idealne dopasowania na szachownicy?

14

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,n3: wystarczy pokazać dopasowania dla3m,n6i wykonać trochę pracy indukcyjnej.mn2m×nm,n33m,n6

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)(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+qp,qdla wystarczająco dużegom,n(powiedzmy,m,nC(p,q)), jak wyglądaC(p,q)?mn2m,nm,nC(p,q)C(p,q)

ctgPi
źródło
to miłe pytanie.
Suresh Venkat
Myślę, że wycieczka rycerza jest wystarczająca. Pozornie zamknięte trasy zawsze istnieją, gdy i m n jest parzysta. m,n>8mn
Timothy Sun

Odpowiedzi:

9

Odpowiedź NIE dla wszystkich dużychm,n, np.P=6iq=3. Dlaczego? Zauważ, że z powodu resztymn2m,np=6q=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 + ymod3m=n=100 ma sześć klas, które są w trzech parach, różnice między licznościami par wynoszą 1 , 1 , 2 ).x+ymod61,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.)pqp+qpqp+q

domotorp
źródło
Och, dobra uwaga; Zmodyfikowałem pytanie, aby odzwierciedlić twoją obserwację.
ctgPi