Prouver une solution pour le puzzle $ N $

Question

donné une $ N $ x $ n $ carte, suppose que $ n \ geq 5 $ et que $ n $ n'est pas divisible par $ 2 $ < / span> ou 3 $ $ . Prouvez que le positionnement suivant de $ N $ reine $ q_0, q_2, ..., q_ {n-1} $ fonctionne, c'est-à-dire pas deux reines se menacer mutuellement:

pour 0 \ LEQ i \ Leq n-1 $ Nous positionnons la reine $ q_i $ sur Le champ $ (i, 2i \ texte {} \ pmod n) $ .

ici, nous utilisons le ( $ x $ -Coordinate, $ y $ -Coordinate) Système de coordonnées, où $ x $ décrit la position horizontale et $ y $ la verticale. Par exemple, dans la formule ci-dessus, $ x $ serait $ i $ et $ y $ serait 2i \ pmod n $ .

Mon idée était de prouver la contradiction et de rompre chaque cas sur la manière dont les reines sont positionnées pour ne pas se menacer mutuellement (horizontalement, verticalement et en diagonale), mais je ne vois pas ce qui suit. Quelqu'un peut-il offrir leurs pensées ou me dire dans la bonne direction?

Answer 1

verticalement: si $ q_i $ et $ q_j $ ont le même $ x $ -Coordinate, $ i= j $ donc ils sont la même reine.

horizontalement: si $ q_i $ et $ q_j $ a la même catégorie $ Y $ -Coordinate, $ 2i= 2j \ pmod n $ , donc $ 2i= 2J + kN $ pour certains $ k \ in \ mathbb {z} $ ; depuis $ n $ n'est pas divisible par 2, $ k $ doit être, et nous avons $ i= j + (2k ') n $ , donc $ i= j \ pmod n $ . Depuis les deux $ i $ et $ j $ sont $ \ Le n $ , ils sont égaux.

diagonale: nous avons deux cas: les diagonales parallèles à $ (0, 0) \ to (1, 1) $ et les "antidiagonaux". Premier cas: si i - 2i= j - 2j \ pmod n $ , $ - i= -j \ pmod n $ , donc $ i= j \ pmod n $ . Deuxième cas: si $ i + 2i= j + 2j \ pmod n $ , donc $ 3i= 3j + kn $ < / span> pour certains $ k \ in \ mathbb {z} $ ; depuis $ N $ n'est pas divisible par 3, $ k $ doit être, et nous avons $ i= j + (3k ') n $ , donc $ i= j \ pmod n $ .

Answer 2

considérer $ i entre 0 et $ n-1 $ . Bien sûr, la première coordonnée ne peut être identique pour deux reines, par conséquent, ils ne sont donc pas dans la même rangée.

Maintenant, supposons que, par souci de contradiction, ils se trouvent sur la même colonne. Ensuite, 2 $ (I-J)= NK $ pour certains $ K $ . Maintenant, comme n ne contient pas 2 comme il est diviseur, $ k $ doit être même. Donc, soit $ k $ est 0, ce qui n'est pas possible car cela va contredire notre hypothèse que $ i $ et $ j $ ne sont pas égaux ou $ k \ geq 2 $ . Dans ce dernier cas, $ lhs= 2 (ij) <2 (n-1) <2n \ leq nk $ , et donc $ Lhs \ ne rhs rhs $ . Par conséquent, nous concluons que notre hypothèse doit avoir été incorrecte et que deux reines positionnées de cette manière ne peuvent pas se situer sur la même colonne.

Vous devez toujours trouver le boîtier diagonal.

Answer 3

pour le boîtier diagonal, divisé à deux épreuves - une pour chaque "rotation" de la ligne diagonale.

Lorsque la ligne diagonale est "de haut à gauche en bas à droite", alors assumez pour la contradiction que nous avons deux reines $ i, j $ . Ensuite, pour qu'ils soient sur la même ligne diagonale, il doit y avoir une partie $ k $ où $ i + k= j $ et 2i \ pmod n + k= 2j \ pmod n $ . Ainsi, $ k= ji $ et $ k= 2 (ji) \ pmod n $ .

Par conséquent, il doit y avoir un nombre entier $ d $ avec $ k= 2 (ji) + dn $ < / span>. Substitut $ k= ji $ et obtenir $ ij= dn $ et donc $ ij= 0 \ pmod n $ . mais les deux $ 0 \ le i, j \ le n-1 $ donc nous devons avoir $ i= j $ Et donc nous avons une contradiction.

L'autre "rotation" de la ligne diagonale utilise la même idée.