Probando una solución para el rompecabezas de $ n $

Question

Dado un $ n $ x $ n $ tablero, asuma que $ n \ geq 5 $ y que $ n $ no es divisible por $ 2 $ < / span> o $ 3 $ . Demuestre que el siguiente posicionamiento de $ n $ Queens $ q_0, q_2, ..., q_ {n-1} $ funciona, es decir, no dos reinas amenazadas entre sí:

para $ 0 \ leq i \ leq n-1 $ Posicionamos la reina $ q_i $ en El campo $ (i, 2i \ texto {} \ pmod n) $ .

Aquí estamos usando el ( $ x $ -coordinate, $ y $ -coordinate) Sistema de coordenadas, donde $ x $ describe la posición horizontal, y $ y $ la vertical. Por ejemplo, en la fórmula anterior, $ x $ sería $ i $ , y $ y $ sería $ 2i \ PMOD N $ .

Mi idea era probar por contradicción y romper cada caso sobre cómo se posicionan las reinas para no amenazarse mutuamente (horizontal, vertical y diagonal), pero no puedo ver lo que sigue. ¿Alguien puede ofrecer sus pensamientos o apuntarme en la dirección correcta?

Answer 1

verticalmente: si $ q_i $ y $ q_j $ tienen la misma $ x $ -coordinate, $ i= j $ para que son la misma reina.

horizontalmente: si $ q_i $ y $ q_j $ tienen la misma $ y $ -coordinate, $ 2i= 2j \ PMOD N $ , por lo $ 2i= 2J + KN $ para algunos $ k \ in \ mathbb {z} $ ; Desde $ n $ no es divisible por 2, $ k $ debe ser, y tenemos $ i= J + (2k ') n $ , por lo que $ i= j \ pmod n $ . Desde ambos $ i $ y $ j $ son $ \ le n $ , son iguales.

Diagonalmente: tenemos dos casos: los diagonales paralelos a $ (0, 0) \ a (1, 1) $ y los 'antidiagonales'. Primer caso: si $ i - 2i= j - 2j \ pmod n $ , $ - i= -j \ pmod n $ , por lo que $ i= j \ pmod n $ . Segundo caso: si $ i + 2i= j + 2j \ pmod n $ , por lo $ 3i= 3j + kn $ < / span> para algunos $ k \ in \ mathbb {z} $ ; Desde $ n $ no es divisible por 3, $ k $ debe ser, y tenemos $ i= j + (3k ') n $ , por lo que $ i= j \ pmod n $ .

Answer 2

Considere $ i entre 0 y $ n-1 $ . Por supuesto, la primera coordenada no puede ser la misma para dos reinas, por lo tanto, no están en la misma fila.

Ahora, supongamos, por el bien de la contradicción, se encuentran en la misma columna. Luego, $ 2 (I-J)= NK $ para algunos $ k $ . Ahora, como N no contiene 2, ya que es divisor, $ k $ debe ser incluso. Por lo tanto, ya sea $ k $ es 0, lo que no es posible porque eso contradigirá nuestro supuesto de que $ i $ y $ j $ no son iguales, o $ k \ geq 2 $ . En este último caso, $ lhs= 2 (ij) <2 (n-1) <2n \ leq nk $ , y por lo tanto $ Lhs \ ne shs $ . Por lo tanto, concluimos que nuestra suposición debe haber sido incorrecta y dos reinas posicionadas de esta manera no pueden mentir en la misma columna.

aún necesita averiguar el caso diagonal.

Answer 3

para la caja diagonal, dividida en dos pruebas, una para cada "rotación" de la línea diagonal.

Cuando la línea diagonal es "desde la parte superior izquierda a la parte inferior derecha", asuma por el bien de la contradicción, tenemos dos reinas $ i, j $ . Luego, para que estén en la misma línea de diagonal, debe haber algunos $ k $ donde $ i + k= j $ y $ 2i \ PMOD N + K= 2J \ PMOD N $ . Por lo tanto, ambos $ k= ji $ y $ k= 2 (ji) \ pmod n $ .

Por lo tanto, debe haber algún número entero $ d $ con $ k= 2 (ji) + dn $ < / span>. Sustituto $ k= ji $ y obtenga $ ij= dn $ y, por lo tanto, $ ij= 0 \ PMOD N $ . Pero ambos $ 0 \ le i, j \ le n-1 $ para que debemos tener $ i= j $ Y por eso tenemos una contradicción.

La otra "rotación" de la línea diagonal utiliza la misma idea.