Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 27-02-2015 09:03:47

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

sans le carré

Peut on toujours placer N pions dans un carré de côté N*N sans qu'il y ait 2 pions qui partagent colonne, ligne ou diagonale? Justifiez smile

Une précision: si on prend le carré comme un damier, les diagonales dont parle le sujet sont toutes celles qui sont parallèles aux 2 principales. Il n'y donc pas que les 2 grandes diagonales mais tous les alignements à-/+45°. Désolé pour la confusion.

  • |
  • Répondre

#0 Pub

 #2 - 27-02-2015 09:06:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Dns le carré

Bonjour

Déjà ça ne marche pas avec n=2 smile

Vasimolo

 #3 - 27-02-2015 09:25:56

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,993E+3

Dans lee carré

NON, ça ne marche pas pour 2x2

 #4 - 27-02-2015 10:00:10

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

danq le carré

Deux cas évidents sont identifiés, N=2 et N=3 où ça ne marche pas.
Dans le cas général, pour un N quelconque, comment savoir si ça marche ou pas?

 #5 - 27-02-2015 10:26:10

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

Daans le carré

Pour info, ça marche pour N=4, 5, 6, 7, ... big_smile

 #6 - 27-02-2015 10:55:49

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

dabs le carré

A part le cas N=2 pas faisable, il suffit de disposer les pions sur les cases voisines d'une diagonale. Si N impair, 1 pion sur la diagonale.
ça marche aussi pour 3 il me semble, kossi.

 #7 - 27-02-2015 11:03:04

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Dans el carré

C'est une généralisation du fameux problème des huit dames sur l'échiquier .

Il y a plusieurs solutions dès que N est supérieur à 3 . Il y a un algorithme très simple qui donne une des solutions , je devrais pouvoir retrouver ça si personne ne le fait avant moi smile

Sinon il y a sûrement moyen de simplement justifier l'existence d'une solution mais il ne me saute pas aux yeux cool

Vasimolo

 #8 - 27-02-2015 11:37:18

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

Dans e carré

Pour n=1 et n=2, c'est possible.

Supposons que ça marche pour n, on place 2 pions comme sur le dessin ci-dessous :
http://www.prise2tete.fr/upload/dylasse-echecnxn.jpg
ça marche pour n+2.

Donc ça marche tout le temps !!!

 #9 - 27-02-2015 12:57:35

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Dan sle carré

Pour N=3, on peut faire :

OXO
OOX
XOO

Ça marche non ?

 #10 - 27-02-2015 13:47:10

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

dans lr carré

Nodim et titouf : n=3 ne marche pas.
Dylasse : ça ne marche pas pour n=2 ni tout le temps.
vasimolo: ce serait très intéressant la solution du cas que tu évoque.

 #11 - 27-02-2015 13:50:54

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Danns le carré

kossi, qu'est-ce qui ne va pas dans l'exemple que j'ai donné ? Il n'y a pas deux pions qui partagent la même ligne, colonne ou diagonale !

 #12 - 27-02-2015 13:56:46

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

Dnas le carré

Petite précision...
Est-ce que par diagonale tu entends seulement les 2 diagonales du carré ou tous les alignements à +/-45° ?

Dans le premier cas, ma récurrence est bonne (il faut juste initialiser proprement avec 3 et 4), dans le second cas, il faut que je cherche !

 #13 - 27-02-2015 16:21:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Das le carré

Je crois que ça ne marche pas pour les carrés de coté 6k+3 cases.

 #14 - 27-02-2015 16:44:51

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3221
Lieu: Luxembourg

Dans le caarré

Sans la contrainte d'au moins une diagonale (mais juste lignes et colonnes), ce serait possible (par exemple en les disposant justement sur une diagonale).
Avec la contrainte d'au moins une diagonale, ça devient impossible; c'est un peu comme si on avait une inconnue de plus que le nombre d'équations.
Je m'explique: en ayant comme contrainte juste lignes et colonnes, pour le premier pion on aura N² possibilités; pour le second plus (n-1)²; etc ...; et pour le dernier plus qu'une seule. Toute contrainte supplémentaire "bloque" le système.

 #15 - 27-02-2015 17:57:01

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

Danns le carré

Une précision: si on prend le carré comme un damier, les diagonales dont parle le sujet sont toutes celles qui sont parallèles aux 2 principales. Il n'y donc pas que les 2 grandes diagonales mais tous les alignements à-/+45°. Désolé pour la confusion.

 #16 - 27-02-2015 18:05:45

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

dans le czrré

Une solution pour N supérieur à 3 :

1) On note R le reste de N modulo 12 .
2) On écrit les nombres pairs de 2 à N .
3) Si R=3 ou R=9 on met le 2 à la fin de la liste .
4) On écrit les nombres impairs de 1 à N ( sauf si R=8 , on les permute alors deux à deux : 3,1,7,5,...).
5) Si R=2 on échange 1 et 3 et on met le 5 en fin de liste .
6) Si R=3 ou R=9 on met 3 puis 1 en fin de liste .

Par exemple pour N=15 , l'algorithme donne : [4,6,8,10,12,14,2,5,7,9,11,13,15,1,3] .

La ième composante indiquant la hauteur du pion de la ième colonne  .

Vasimolo

 #17 - 27-02-2015 18:12:33

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

Dans le craré

vasimolo a écrit :

C'est une généralisation du fameux problème des huit dames sur l'échiquier .

Oui, c'est tout à fait ca.

Nodim: c'est une très intéressante réponse mais pas que...(enfin, il me semble). Est ce le nombre de cases dans le carré ou le côté du carré que tu donnes?

Les autres: l'énoncé n'était pas vraiment clair sur tous les alignements à -/+45°, vous êtes tous partis sur les 2 diagonales du carré. Partie remise smile

 #18 - 27-02-2015 18:19:53

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 307
Lieu: Montargis

Dans lee carré

vasimolo a fait du vasimolo en donnant carrément un algorithme...
Pour le moment, j'admire sans avis. Vous jugerez par vous même smile

 #19 - 27-02-2015 19:21:31

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Dans le carér

Je n'ai pas grand mérite sur ce coup : je n'ai fait que recopier un algorithme sûrement connu depuis très longtemps smile

Vasimolo

 #20 - 27-02-2015 19:32:25

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Dan sle carré

Je complète ma première réponse en donnant les impossibilités de construction:
coté 3+6k pour les carrés impairs.
coté 2+12k pour les carrés pairs.

Bon, il faudra justifier tout de même.

 #21 - 03-03-2015 15:52:14

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Dan sle carré

Bonjour,

nodgim #13 a écrit:

Je crois que ça ne marche pas pour les carrés de coté 6k+3 cases.

Voici un contre-exemple, pour k=1

Code:

 ♛ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
 ⋅ ⋅ ♛ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
 ⋅ ⋅ ⋅ ⋅ ⋅ ♛ ⋅ ⋅ ⋅
 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ♛ ⋅
 ⋅ ♛ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
 ⋅ ⋅ ⋅ ♛ ⋅ ⋅ ⋅ ⋅ ⋅
 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ♛
 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ♛ ⋅ ⋅
 ⋅ ⋅ ⋅ ⋅ ♛ ⋅ ⋅ ⋅ ⋅
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete