¿Combinaciones perfectas en un tablero de ajedrez?

Considera el problema de encontrar el número máximo de caballeros que se pueden colocar en un tablero de ajedrez sin que dos de ellos se ataquen entre sí. La respuesta es 32: no es demasiado difícil encontrar una coincidencia perfecta (el gráfico inducido por los movimientos de los caballeros es bipartito, y hay una coincidencia perfecta para un tablero de 4 × 4), que obviamente es una cubierta de borde mínima. Tampoco es difícil demostrar que la respuesta es para un tablero de ajedrez cada vez que : es suficiente mostrar coincidencias para y hacer un poco de juego de pies de inducción.$\left\lceil \frac{mn}{2} \right\rceil$m , n ≥ 3 3 ≤ m , n ≤ $m \times n$$m,n \geq 3$$3 \leq m,n \leq 6$

Por otro lado, si el tablero de ajedrez fuera toroidal fueran pares, la prueba ni siquiera requeriría mostrar una coincidencia para tableros pequeños: el mapa tiene solo ciclos de longitud uniforme, por lo que debe haber una combinación perfecta.( x , y ) → ( x + 1 , y + 2 $m, n$$(x, y) \rightarrow (x+1, y+2)$

¿Existe algún equivalente para los tableros de ajedrez rectangulares , es decir, hay alguna forma más simple de demostrar que para suficientemente grande siempre hay una combinación perfecta del tablero de ajedrez? Para tableros grandes, el tablero rectangular y el tablero toroidal son casi equivalentes en el sentido de que la fracción de bordes faltantes llega a cero, pero no conozco ningún resultado teórico que garantice una coincidencia perfecta en ese caso.$m, n$

¿Qué pasa si, en lugar de saltar en cualquier dirección, un caballero salta cuadrados en cualquier dirección? O, para el caso, cuadrados, con impar y coprimo? Si no es una forma sencilla de probar que la respuesta es para suficientemente grande (por ejemplo, ), ¿Cómo se ve ?( 2 , 3 ) ( p , q ) p + q p , q ⌈ m $(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)$

La respuesta NO es para todos los grandesm,nsi, por ejemplo,p=6yq=3. ¿Por qué? Observe que debido a los restosahora el gráfico es la unión disjunta (vértice) de tres gráficos bipartitos y de cada uno podemos seleccionar la mitad más grande. Por ejemplo, si, de esta manera podemos colocar (al menos) 5002 caballeros. (Esto se debe a quetiene seis clases que están en tres pares, las diferencias entre las cardinalidades de los pares es).$\lceil \frac{mn}2\rceil$$m, n$$p=6$$q=3$$\mod 3$$m=n=100$$x+y \mod 6$$1,1,2$

No sé qué pasa si añadimos la condición de que y son primos relativos. (Tenga en cuenta que, aparte del divisor 2, esto es equivalente a que y sean números primos relativos, de hecho, esta es la condición que necesitamos y que también muestra que es impar).$p$$q$$p+q$$p-q$$p+q$