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

Dans le ccarré

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,382E+3

Dans e 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,896E+3

Dasn le 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

dans le xarré

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

ans 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 : 3801

Dans le craré

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,382E+3

Dans le crré

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 le careé

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

Dans le 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 le caeré

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

dans le varré

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

dzns 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 : 3801

dans lz 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 : 3208
Lieu: Luxembourg

Dans le carr

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

Dans le arré

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,382E+3

dans le carté

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

aDns le carré

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

fans le 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,382E+3

Dans le craré

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 : 3801

dans le catré

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

dans le xarré

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 : Pif, Paf 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