Échecs en 3D

[Juzo]

Bonjour,
Voici une question que j'ai trouvé sur internet :
Quel est le nombre minimal de tours nécessaires pour contrôler complètement un échiquier en trois dimensions (8×8×8) ?

J'ai trouvé un minimum de

 Cliquez pour afficher

32 tours

pour le moment

... Mais cherche à démontrer quel est le nombre minimal.

Bonne journée !
-----

[Juzo]

* mais JE cherche

Ps : Il n'y avait pas de réponse sur le site où j'ai trouvé cette question

[Noress]

Bonjour Juzo, ce serait donc 4 élevé au cube.
Pour un échiquier à trois dimensions (je n'ai pas la réponse) ça n'a pas l'air évident à se représenter.
Soit on l'imagine dans son volume à six plateaux, soit on appréhende l'espace à l'intérieur de ce même volume par la superposition de 8 plateaux pour chacune des trois dimensions.
Troisième possibilité : je n'ai rein compris... C'est plutôt complexe.
Cdt.

[Noress]

Bonjour Juzo, ce serait donc 4 élevé au cube.
Pour un échiquier à trois dimensions (je n'ai pas la réponse) ça n'a pas l'air évident à se représenter.
Soit on l'imagine dans son volume à six plateaux, soit on appréhende l'espace à l'intérieur de ce même volume par la superposition de 8 plateaux pour chacune des trois dimensions.
Troisième possibilité : je n'ai rein compris... C'est plutôt complexe.
Cdt.

Rectification : 4 élevé au cube, quelle horreur !!!!

[A voir en vidéo sur Futura]

[Juzo]

Bonjour, c'est un cube dont les arêtes font 8 cases de long

[Mct92mct]

Bonjour Juzo ,
je suis d'accord avec toi pour contrôler complétement un cube échiquier de 8X8X8 il faut 32 tours
soit 8 au 8 coins du cube 8
puis 8 aux 8 coins du cube 7
puis 8 aux 8 coins du cube 6
puis 8 aux 8 coins du cube central
soit 4X8 32 tours pour couvrir toutes les cases.
Pas possible de faire mieux!

[Mct92mct]

plutôt lire:
8 tours aux 8 coins du cube 8X8X8 puis
8 tours aux 8 coins du cube 6X6X6 puis
8 tours aux 8 coins du cube 4X4X4 puis
8 tours aux 8 coins du cube 2X2X2 du cube central
soit 32 tours au total
Pas possible de faire mieux

[Dynamix]

Bonjour Juzo ,
je suis d'accord avec toi pour contrôler complétement un cube échiquier de 8X8X8 il faut 32 tours
soit 8 au 8 coins du cube 8

Tu contrôle les 12 arêtes .
Mais , chaque tour dans un coin contrôlant 3 arrêtes , 4 tours suffisent .
Ce qui donne un contrôle sur 80 cases seulement .

(une case , c' est en fait un cube )

[Mct92mct]

Tu contrôle les 12 arêtes .
Mais , chaque tour dans un coin contrôlant 3 arrêtes , 4 tours suffisent .
Ce qui donne un contrôle sur 80 cases seulement .

(une case , c' est en fait un cube )

je ne sais pas ou tu trouves 12 arêtes dans un cubes moi j'en vois que 8...

[Mct92mct]

Yes compris...en fait, il faut 16 tours pour contrôler les 512 cases du cube 8X8X8

[Dynamix]

je ne sais pas ou tu trouves 12 arêtes dans un cubes moi j'en vois que 8...

Ne te décourage pas , cherche encore .
Tu va finir par trouver .

[Dynamix]

Yes compris...en fait, il faut 16 tours pour contrôler les 512 cases du cube 8X8X8

Non , c' est impossible .
Une tour , peu importe son emplacement , contrôle 22 cases (3x7+1)
Sans chevauchement (2 tours contrôlant la même case) il faudrait donc 24 tours (23,27...) .
On ne peut pas faire moins .
L' astuce est en fait de minimiser les chevauchements .

[Mct92mct]

Ne te décourage pas , cherche encore .
Tu va finir par trouver .

je sais pas si tu t'en est rendu compte mais je réagis à chaud, et il est impossible avec ce foutu logiciel de revenir en arrière même 20 seconde après avoir relu son texte... il dise 5 minutes mais c'est du bluf!

[Mct92mct]

Non , c' est impossible .
Une tour , peu importe son emplacement , contrôle 22 cases (3x7+1)
Sans chevauchement (2 tours contrôlant la même case) il faudrait donc 24 tours (23,27...) .
On ne peut pas faire moins .
L' astuce est en fait de minimiser les chevauchements .

Bon récapitulons
avec 32 tours, il n'y a aucun problème on occupe ou on vise tous les cubes...du cube(8X8X8)
de la même façon avec 24 tours on occupe ou on vise tous les cubes du cube(6X6X6) et le centre des 6 faces (8X8)
Bref, il ne reste plus qu'à s'occuper des 12 arêtes avec 4 tours supplémentaires et donc, on contrôle avec 28 tours seulement l'ensemble des 512 cases du cube(8X8X8)
là, ça devrait être pas trop mal...

[Mct92mct]

Bon récapitulons
avec 32 tours, il n'y a aucun problème on occupe ou on vise tous les cubes...du cube(8X8X8)
de la même façon avec 24 tours on occupe ou on vise tous les cubes du cube(6X6X6) et le centre des 6 faces (8X8)
Bref, il ne reste plus qu'à s'occuper des 12 arêtes avec 4 tours supplémentaires et donc, on contrôle avec 28 tours seulement l'ensemble des 512 cases du cube(8X8X8)
là, ça devrait être pas trop mal...

Bon, on peut encore se passer de 4 tours dans le petit cube (2X2X2) du centre
On arrive donc à 24 tours...
4 tours dans le cube(2X2X2) central
8 tours dans les arêtes du cube (4X4X4)
8 tours dans les arêtes du cube (6X6X6)
et 4 tours dans les arêtes du cube (8X8X8)

[Juzo]

Bonjour, pour un cube d'arête 6 j'utilise 18 tours

Je décris la méthode que j'utilise ci-dessous, en spoiler pour que tu puisses continuer Ã* chercher si tu le souhaites

 Cliquez pour afficher

J'appelle "super tour d'arête n" un cube d'arête n qui se comporte comme une tour, c'est-Ã*-dire qu'il contrôle complètement les directions orthogonales Ã* toutes ses faces. Pour fabriquer une super tour d'arête n on utilise n^2 tours.

Pour contrôler un échiquier d'arête n, avec n impair (n>1), je place au centre de l'échiquier une super tour d'arête n-2 (ça contrôle l'intérieur de l'échiquier et le centre de ses faces, soit tout l'échiquier sauf ses arêtes). J'utilise aussi 4 tours pour contrôler les arêtes.
Pour contrôler complètement un échiquier d'arête impaire j'utilise donc
(n-2)^2+4 = n^2 - 4n + 8 tours

Pour contrôler un échiquier d'arête n avec n pair, je sépare l'échiquier en 8 cubes d'arête n/2. Je place deux super tours d'arête n/2 dans les deux cubes d'une diagonale de l'échiquier (qui n'ont qu'un sommet en commun), ce qui permet de contrôler complètement l'échiquier
Nombre de tours utilisé : 2×(n/2)^2 = n^2/2 tours

Arête 1 : 1 tour
Arête 2 : 2 tours
Arête 3. : 5 tours
Arête 4 : 8 tours (2 super tours en diagonale)
Arête 5 : 13 tours (une super tour de 3 au centre et arêtes contrôlées avec 4 tours)
Etc.

Par contre je ne sais pas si c'est la méthode optimale, ni dans ce cas comment le démontrer.

[JPL]

La même chose avec des caractères lisibles ?

[Mct92mct]

Bonjour, pour un cube d'arête 6 j'utilise 18 tours

Je décris la méthode que j'utilise ci-dessous, en spoiler pour que tu puisses continuer Ã* chercher si tu le souhaites

 Cliquez pour afficher

J'appelle "super tour d'arête n" un cube d'arête n qui se comporte comme une tour, c'est-Ã*-dire qu'il contrôle complètement les directions orthogonales Ã* toutes ses faces. Pour fabriquer une super tour d'arête n on utilise n^2 tours.

Pour contrôler un échiquier d'arête n, avec n impair (n>1), je place au centre de l'échiquier une super tour d'arête n-2 (ça contrôle l'intérieur de l'échiquier et le centre de ses faces, soit tout l'échiquier sauf ses arêtes). J'utilise aussi 4 tours pour contrôler les arêtes.
Pour contrôler complètement un échiquier d'arête impaire j'utilise donc
(n-2)^2+4 = n^2 - 4n + 8 tours

Pour contrôler un échiquier d'arête n avec n pair, je sépare l'échiquier en 8 cubes d'arête n/2. Je place deux super tours d'arête n/2 dans les deux cubes d'une diagonale de l'échiquier (qui n'ont qu'un sommet en commun), ce qui permet de contrôler complètement l'échiquier
Nombre de tours utilisé : 2×(n/2)^2 = n^2/2 tours

Arête 1 : 1 tour
Arête 2 : 2 tours
Arête 3. : 5 tours
Arête 4 : 8 tours (2 super tours en diagonale)
Arête 5 : 13 tours (une super tour de 3 au centre et arêtes contrôlées avec 4 tours)
Etc.

Par contre je ne sais pas si c'est la méthode optimale, ni dans ce cas comment le démontrer.

bien si tu as bien compris comment je disposais mes tours, je pense qu'il est possible de n'avoir que 16 tours pour un cube (6X6X6)
Dans les jours qui viennent je vais dessiner ma solution pour un cube (6X6X6)
A bientôt

[Juzo]

Désolé, c'est le téléphone qui a mal fonctionné :

 Cliquez pour afficher

J'appelle "super tour d'arête n" un cube d'arête de longueur n qui se comporte comme une tour, c'est-à-dire qu'il contrôle complètement les directions orthogonales à toutes ses faces. Pour fabriquer une super tour d'arête n on utilise n^2 tours.

Pour contrôler un échiquier d'arête n, avec n impair (n>1), je place au centre de l'échiquier une super tour d'arête n-2 (ça contrôle l'intérieur de l'échiquier et le centre de ses faces, soit tout l'échiquier sauf ses arêtes). J'utilise aussi 4 tours pour contrôler les arêtes.
Pour contrôler complètement un échiquier d'arête impaire j'utilise donc
(n-2)^2+4 = n^2 - 4n + 8 tours

Pour contrôler un échiquier d'arête n avec n pair, je sépare l'échiquier en 8 cubes d'arête n/2. Je place deux super tours d'arête n/2 dans les deux cubes d'une diagonale de l'échiquier (qui n'ont qu'un sommet en commun), ce qui permet de contrôler complètement l'échiquier
Nombre de tours utilisé : 2*(n/2)^2 = n^2/2 tours

Arête 1 : 1 tour
Arête 2 : 2 tours
Arête 3. : 5 tours
Arête 4 : 8 tours (2 super tours en diagonale)
Arête 5 : 13 tours (une super tour de 3 au centre et arêtes contrôlées avec 4 tours)
Etc.
Arête 8*: 8^2/2 = 32 tours

Et comme je le disais, je ne sais pas si c'est la méthode optimale, et si c'est le cas comment le démontrer

[Dynamix]

et 4 tours dans les arêtes du cube (8X8X8)

Avec 4 tours , tu ne contrôle que les arête , pas les faces .

[Dynamix]

Je me lance

 Cliquez pour afficher

8 tr dans le 2³
8 tr dans le 4³ dans les coins = contrôle des 4 arrêtes . les face sont contrôlées par les 8 du 2³
8 tr dans le 6³ dans le coins = même motif .
4 tr dans le 8³ dans les coins opposés = vu qu' il n' y a que les arêtes à contrôler , 4 suffisent .

[Mct92mct]

Je me lance

 Cliquez pour afficher

8 tr dans le 2³
8 tr dans le 4³ dans les coins = contrôle des 4 arrêtes . les face sont contrôlées par les 8 du 2³
8 tr dans le 6³ dans le coins = même motif .
4 tr dans le 8³ dans les coins opposés = vu qu' il n' y a que les arêtes à contrôler , 4 suffisent .

Pourquoi 8 tours dans le 2³ alors que pour ce cube les arêtes et le cube entier, c'est la même chose?
4 tours suffisent...

[Dynamix]

Pour contrôler les faces du 4³
Mais c' est vrai qu' on peut le faire avec les coins opposés .

[Mct92mct]

Pour contrôler les faces du 4³
Mais c' est vrai qu' on peut le faire avec les coins opposés .

hé oui, c'est même à cause de cela que j'ai cru qu'il suffisait de 16 tours...
En fait il en faut 4+8+8+4 soit 24 tours au total pour contrôler les 512 cases du cube de (8X8X8)
c'est l'optimum qu'on puisse faire!

[Juzo]

@Mct92mct Je ne sais pas exactement quelle technique tu utilises (si on peut se tutoyer ), ce qui es sûr c'est qu'en plaçant des tours sur les sommets de cubes imbriqués les uns dans les autres, tu ne contrôles pas complètement l'échiquier.

Prenons un échiquier (8x8x8) :
Tu contrôles les arêtes du cube (8x8x8) avec 4 tours, puis tu contrôles les arêtes du cube (6x6x6) en utilisant 8 tours.

Que se passe-t-il maintenant sur une face de l'échiquier ?
Le carré extérieur (8x8) est complètement contrôlé (il est constitué d'arêtes du cube (8x8))
Le carré (6x6) de cette face est contrôlé en seulement 4 cases, celles qui sont "au-dessus" des tours du cube (6x6x6). Il te manques donc 4x4 = 16 cases à contrôler sur cette face, soit 16 x4 = 64 cases à contrôler en tout sur toutes les faces de l'échiquier. C'est le même raisonnement pour les "couches" en-dessous.

De toute façon il est impossible que tu n'utilises que 24 tours s'il y a des tours qui se recoupent, c'est-à-dire qu'il y a des "cases" contrôlées par deux tours différentes. 24 tours implique que chaque tour permet de contrôler 22 cases sans recoupement.

[Juzo]

* ce seront plutôt 6x16 = 96 "cases" qui ne seront pas contrôlées sur les carrés (6x6) des 6 faces de ton échiquier, mais le raisonnement est le même

[Mct92mct]

* ce seront plutôt 6x16 = 96 "cases" qui ne seront pas contrôlées sur les carrés (6x6) des 6 faces de ton échiquier, mais le raisonnement est le même

Bonjour, effectivement en dessinant, je me suis aperçu que mon raisonnement avait un problème...

[Juzo]

Bonjour, la méthode donnée pour l'échiquier d'arête impaire n'était pas la bonne, je corrige

 Cliquez pour afficher

Pour n impair :
Plutôt que de placer une super tour d'arête (n-2) au centre puis couvrir les arêtes de l'échiquier, ce qui est trop gourmand à partir de n =7,
placer en diagonale dans l'échiquier une super tour d'arête [(n+1)/2]² et une super tour d'arête [(n-1)/2]².

On utilise en tout [(n+1)/2]² + [(n-1)/2]² = ... = (n²+1)/2 tours

Bilan :
Pour n pair : deux super tours d'arête n/2, on utilise n²/2 tours
Pour n impair : une super tour d'arête [(n+1)/2]² et une super tour d'arête [(n-1)/2]², on utilise (n²+1)/2 tours

Quand on trace le nombre de tours utilisées en fonction de l'arête n de l'échiquier, on a cette fois une fonction qui est toujours croissante

Même est-ce la meilleure méthode ?

Fin du monologue ?

[Mct92mct]

bonjour,
Comme promis,
une petite vidéo des 24 tours qui sont nécessaires pour contrôler un cube 6X6X6
http://sd-1.archive-host.com/membres...8/IMG_1724.MOV
Cordialement

[Juzo]

Bonjour, merci pour la vidéo, quel logiciel as-tu utilisé ?
Comme je l'ai décrit plus haut, il est possible de contrôler un échiquier (6x6x6) avec 18 tours seulement.