Combinações perfeitas em um tabuleiro de xadrez?

Considere o problema de encontrar o número máximo de cavaleiros que podem ser colocados em um tabuleiro de xadrez sem que dois deles se atacem. A resposta é 32: não é muito difícil encontrar uma combinação perfeita (o gráfico induzido pelos movimentos dos cavaleiros é bipartido e há uma combinação perfeita para uma prancha 4 × 4), o que obviamente é uma cobertura mínima da borda. Também não é difícil provar que a resposta é para um tabuleiro de xadrez sempre que : basta mostrar combinações para e faça um pouco de footwork de indução.m×nm,n≥33≤m,n≤$\left\lceil \frac{mn}{2} \right\rceil$$m \times n$$m,n \geq 3$$3 \leq m,n \leq 6$

Por outro lado, se o tabuleiro de xadrez fosse toroidal e fosse par, a prova nem exigiria a exibição de uma correspondência para tabuleiros pequenos: o mapa tem apenas ciclos de comprimento uniforme; portanto, deve haver uma correspondência perfeita.( x , y ) → ( x + 1 , y + 2 $m, n$$(x, y) \rightarrow (x+1, y+2)$

Existe algum equivalente para tabuleiros de xadrez retangulares , ou seja, existe uma maneira mais simples de mostrar que, para suficientemente grande sempre existe uma correspondência perfeita do tabuleiro de xadrez? Para placas grandes, a placa retangular e a placa toroidal são quase equivalentes no sentido de que a fração de arestas ausentes chega a zero, mas não conheço nenhum resultado teórico que garanta uma correspondência perfeita nesse caso.$m, n$

E se, em vez de pular em qualquer direção, um cavaleiro pular quadrados em qualquer direção? Ou, nesse caso, quadrados, com ímpar coprime? Se não é uma simples forma de provar que a resposta é para suficientemente grande (por exemplo, m, n \ GEQ C (p, q) ), como é C (p, q) ?( 2 , 3 ) ( p , q ) p + q p , $(1, 2)$$(2, 3)$$(p, q)$$p+q$$p, q$$\left\lceil \frac{mn}{2} \right\rceil$$m, n$$m, n \geq C(p, q)$$C(p, q)$

A resposta é NÃO para todos os grandes se, por exemplo, e . Por quê? Observe que, devido aos restantes agora o gráfico é a união disjunta (vértice) de três gráficos bipartidos e de cada um podemos selecionar a metade maior. Por exemplo, se , então podemos colocar (pelo menos) 5002 cavaleiros. (Isso ocorre porque tem seis classes que estão em três pares, as diferenças entre as cardinalidades dos pares são .)$\lceil \frac{mn}2\rceil$$m, n$$p=6$$q=3$$\mod 3$$m=n=100$$x+y \mod 6$$1,1,2$

Eu não sei o que acontece se adicionarmos a condição de que e são primos relativos. (Observe que, além do divisor 2, isso é equivalente a e são primos relativos, na verdade, essa é a condição de que precisamos e que também mostra que sendo ímpar é necessário.)$p$$q$$p+q$$p-q$$p+q$