Inscription / Connexion Nouveau Sujet
Niveau 2 *
Partager :

Joute n°44 : Technique de surface

Posté par
godefroy_lehardi Posteur d'énigmes
14-09-11 à 14:38

Bonjour à tous,

Le sol d'un entrepôt est constitué de 25 dalles carrées identiques, la dalle centrale C3 étant dédiée au stationnement d'une laveuse de sol entièrement automatique qui fonctionne de la manière suivante :
La machine nettoie entièrement une dalle puis passe à la suivante par un côté adjacent (et non en diagonale). Elle possède un réservoir de produit lui permettant de nettoyer 4 dalles consécutives. Ensuite, elle doit revenir sur la dalle centrale C3 pour remplir à nouveau le réservoir (selon le même mode de déplacement).
Le lavage proprement dit ne commence que lorsque la machine a quitté la dalle centrale.
Cela dit, rien n'interdit de revenir en C3 pour compléter le réservoir avant qu'il soit vide.

Joute n°44 : Technique de surface

Attention : lorsque le réservoir est vide et que la machine roule sur une dalle déjà nettoyée, elle la resalit. Il faudra donc la nettoyer à nouveau entièrement.

Le départ et l'arrivée se font sur la case centrale C3 qui doit aussi être propre à la fin.

Question : Quel est le chemin permettant d'avoir toutes les dalles propres avec le moins de déplacements ?
On appelle déplacement le fait de passer d'une dalle à une autre. La quantité de produit consommée n'entre pas en ligne de compte.
Donnez la suite des dalles visitées dans l'ordre en commençant et en finissant par C3 (le parcours doit comprendre les déplacements de retour vers C3).
S'il existe plusieurs solutions, une seule suffira.

Pour faciliter la correction (et aussi la relecture avant de poster), merci de présenter le parcours en allant à la ligne à chaque fois que vous repassez en C3.

Voici le premier prototype de la machine

Joute n°44 : Technique de surface


P.S : au fait, c'est un anniversaire aujourd'hui.
Joute n°44 : Technique de surface

Posté par
totti1000
re : Joute n°44 : Technique de surface 14-09-11 à 15:58

gagnéSalut godefroy ,

Voici ma proposition en 58 déplacements :

C3-B3-B2-A2-A1-B1-C1-C2
C3-C2-C1-B1-B2-B3
C3-C4-B4-B5-A5-A4-A3-B3
C3-B3-A3-A4-B4-C4
C3-D3-D4-E4-E5-D5-C5-C4
C3-C4-C5-D5-D4-D3
C3-C2-D2-D1-E1-E2-E3-D3
C3-D3-E3-E2-D2-C2
C3-C2
C3

Merci.

Posté par
Nofutur2
re : Joute n°44 : Technique de surface 14-09-11 à 17:01

perduSans aucune méthode donc aucune certitude ...

aller : C3-C2-C1-B1-A1 retour : A2-A3-B3-C3   nettoyage C2-C1-B1-A1
aller : C3-B3-B2-A2-A3 retour : A4-B4-C4-C3 nettoyage B3-B2-A2-A3
aller : C3-C4-B4-A4-A5 retour : B5-C5-C4-C3 nettoyage B4-A4-A5
aller : C3-C4-C5-B5-C5 retour : D5-D4-D3-C3 nettoyage C4-C5-B5
aller : C3-D3-D4-D5-E5 retour : E4-E3-D3-C3   nettoyage D3-D4-D5-E5
aller : C3-D3-D4-E4-E3 retour : D3-C3 nettoyage E3-E4
aller : C3-D3-E3-E2-E1 retour : D1-D2-D3-C3 nettoyage E2-E1
aller : C3-D3-D2-D1-D2 retour : D3-C3 nettoyage D2-D1
aller : C3-D3 retour : C3 nettoyage D3-C3

Posté par
Tof
re : Joute n°44 : Technique de surface 14-09-11 à 17:16

perduBonjour à tous,

Sans être certain d'avoir optimisé, voici (entre parenthèse, le nombre de déplacement de chaque excursion ; un '/' = un déplacement ; deux "/" = un déplacement et le réservoir se vide) :
C3/B3/A3/A2/A1 // B1/C1/C2/C3 (8)
C3/B3/B2/B1/C1 // C2/C3 (6)
C3/C2/D2/D1/E1 // E2/E3/D3/C3 (8)
C3/D3/D2/E2/E3 // D3/C3 (6)
C3/C4/D4/E4/E5 // D5/C5/C4/C3 (8)
C3/C4/C5/D5/C5 // C4/C3 (6)
C3/C4/B4/A4/A5 // B5/C5/C4/C3 (8)
C3/C4/B4/B5/C5 // C4/C3 (6)
C3/C4/C3 (2)

Pour unt total de 58 déplacements.

Merci pour l'énigme,

Tof

Posté par
ksad
re : Joute n°44 : Technique de surface 14-09-11 à 18:12

perduBonjour
Aucune certitude quant à l'optimalité du chemin proposé, mais voici néanmoins une solution qui marche (entendez: qui nettoie tout!)

C3 C2 C1 D1 E1 E2 E3 D3
C3 D3 D2 E2 E3 E4 D4 C4
C3 C4 D4 E4 E5 D5 C5 C4
C3 C4 C5 D5 C5 B5 B4 B3
C3 B3 B4 B5 A5 A4 A3 B3
C3 B3 A3 A4 A3 A2 B2 C2
C3 B3 B2 A2 A1 B1 B2 B3
C3 B3 B2 B1 C1 C2 C3
C3 C2 C3

merci pour la joute !

Posté par
LeDino
re : Joute n°44 : Technique de surface 14-09-11 à 18:51

gagnéBonjour,

Voici ma proposition en 58 déplacements :
C2 - C1 - B1 - A1 - A2 - B2 - B3 - C3
C2 - B2 - A2 - A3 - B3 - C3
B3 - B4 - A4 - A5 - B5 - C5 - C4 - C3
B3 - B4 - B5 - C5 - C4 - C3
C4 - D4 - D5 - E5 - E4 - E3 - D3 - C3
C4 - D4 - E4 - E3 - D3 - C3
C2 - C1 - D1 - E1 - E2 - D2 - D3 - C3
C2 - D2 - E2 - E3 - D3 - C3
D3 - C3

Merci pour cette jolie énigme ...

Et en image, pour faciliter la correction :

Joute n°44 : Technique de surface

Posté par
ksad
re : Joute n°44 : Technique de surface 15-09-11 à 11:02

perduoops -- le retour à C3 ne devrait pas apparaître à la fin de l'avant-dernière ligne, puisque chaque ligne *commence* par C3 dans la solution que j'ai proposée. redondance d'une case, sans déplacement, donc.

proverbe de pêcheur: qui trop vite répond, récolte des poissons...

Posté par
F-R
re : Joute n°44 : Technique de surface 16-09-11 à 19:21

perduBonjour;

Je compte 60 déplacements:

C3 C2 C1 B1 A1 A2 A3 B3
C3 C2 C1 D1 E1 E2 E3 D3
C3 C4 C5 B5 A5 A4 A3 B3
C3 C4 C5 D5 E5 E4 E3 D3
C3 C2 B2 A2 A3 B3
C3 C2 D2 E2 E3 D3
C3 C4 B4 A4 A3 B3
C3 C4 D4 E4 E3 D3
C3 B3 C3 D3 C3

Posté par
castoriginal
Joute n°44 : Technique de surface 16-09-11 à 23:37

gagnéBonsoir,

je voudrais tout d'abord faire une remarque préliminaire. Examinons la figure 1

Joute n°44 : Technique de surface

on constate que chaque case du damier peut être atteinte d'une façon individuelle par un chemin aller-retour d'un certain nombre de cases.
Il y 4 cases dans les coins qui imposent un trajet minimum de 8 cases.
Si l'on considère que la machine lave immédiatement lorsqu'elle a quitté la case C3 (voir trajet bleu) elle ne peut atteindre dans le coin supérieur droit du carré qu'une case 8 et une case 6. L'autre case 6 en E2 doit faire l'objet d'un autre trajet. Cette situation se reproduit quatre fois: on a donc un trajet minimum de 4 x 8 cases + 4 x 6 cases = 56 cases . Il faut également laver la dernière case de sortie du trajet de 6 cases et la case C3, soit 2 cases. On a donc une solution de minimum 58 cases ou déplacements.
On arrive à la solution 1.
solution 1
On considère, comme le dit l'énoncé que "la machine ne commence son lavage proprement dit que lorsqu'elle a quitté la dalle C3". Elle lave immédiatement la dalle voisine de C3 ( voir figure 2)
Joute n°44 : Technique de surface

En bleu on voit les dalles lavées,dans les cercles blancs les dalles de retour.
On a 9 trajets débutant en C3:
trajet 1  C2-C1-D1-E1-E2-D2-D3-C3
trajet 2  D3-E3-E2-D2-C2-C3
trajet 3  D3-E3-E4-E5-D5-D4-C4-C3
trajet 4  D3-D4-D5-C5-C4-C3
trajet 5  C4-C5-B5-A5-A4-B4-B3-C3
trajet 6  C4-B4-A4-A3-B3-C3
trajet 7  B3-A3-A2-A1-B1-B2-C2-C3
trajet 8  B3-B2-B1-C1-C2-C3
trajet 9  C2-C3
Il y a donc  58 déplacements

la solution 2considère un point qui n'est pas évoqué dans l'énoncé: on a dit "la machine ne commence son lavage proprement dit que lorsqu'elle a quitté la dalle C3". On n'a pas dit qu'elle devait commencer à laver immédiatement la case voisine de C3.
Elle pourrait donc de déplacer d'abord d'un certain nombre de dalles avant de démarrer le lavage.
On voit une solution donnée par la figure 2 ci-dessous qui  comporte 46 déplacements
Joute n°44 : Technique de surface

On a 7 trajets débutant en C3:

trajet 1  C2-C1-D1-E1-E2-E3-D3-C3
trajet 2  D3-E3-E4-E5-D5-C5-C4-C3
trajet 3  C4-C5-B5-A5-A4-B4-B3-C3
trajet 4  B3-A3-A2-A1-B1-B2-C2-C3
trajet 5  C2-D2-D3-D4-C4-C3
trajet 6  C4-B4-B3-B2-C2-C3
trajet 7  C2-C3

Bien à vous

Posté par
Pantagruel
re : Joute n°44 : Technique de surface 17-09-11 à 00:04

perduBonjour tout le monde
Je propose ceci:
C3 C2 B2 A2 B2 C2 C3
C3 C4 B4 A4 B4 C4 C3
C3 C2 C1 B1 A1 A2 B2 C2 C3
C3 C4 C5 B5 A5 A4 B4 C4 C3
C3 C2 D2 E2 D2 C2 C3
C3 C4 D4 E4 D4 C4 C3
C3 C2 C1 D1 E1 E2 D2 C2 C3
C3 C4 C5 D5 E5 E4 D4 C4 C3
C3 D3 E3 D3 C3
C3 B3 A3 B3 C3
- C'est à dire 10 rotations et 64 cases traversées.

Posté par
dpi
re : Joute n°44 : Technique de surface 17-09-11 à 14:40

perduBonjour,

Après avoir tourné en rond..

Je n'arrive pas à faire mieux que 58 mouvements

Les 4 angles 4X8
boucher les "trous" 4x6
finir au milieu 2

Posté par
Rumbafan
re : Joute n°44 : Technique de surface 21-09-11 à 13:24

perduBonjour Godefroy,

Après beaucoup d'hésitation...je prends le risque du poisson !!!

Je propose (en 58 mouvements):

B3 A3 A2 A1 B1 C1 C2 C3
C2 B2 B1 C1 C2 C3
C2 C1 D1 E1 E2 E3 D3 C3
D3 D2 E2 E3 D3 C3
D3 E3 E4 E5 D5 C5 C4 C3
C4 D4 D5 C5 C4 C3
C4 C5 B5 A5 A4 B4 C4 C3
B3 B4 A4 A3 B3 C3
B3 C3

Merci pour ce casse-tête...pour lequel le faible nombre de participants plaide en faveur d'un 3 étoiles..

A+

Posté par
caylus
re : Joute n°44 : Technique de surface 26-09-11 à 16:55

gagnéBonjour Godefroy,

Le lundi n'est pas le jour du poisson, mais...

1: C3 B3 A3 A4 A5 B5 C5 C4 C3 : 8 déplacements.
2: C3 B3 B4 B5 C5 C4 C3       : 6
3: C3 C4 D4 D5 E5 E4 E3 D3 C3 : 8
4: C3 C4 D4 E4 E3 D3 C3       : 6
5: C3 D3 E3 E2 E1 D1 C1 C2 C3 : 8
6: C3 B3 A3 A2 A1 B1 C1 C2 C3 : 8
7: C3 D3 D2 D1 C1 C2 C3       : 6
8: C3 C2 C1 B1 B2 B3 C3       :6
9: C3 B3 C3                   :2 donc C3 est nettoyé.

4*8+4*6+2=32+24+2=58.

Il y a peut-être mieux mais je ne vois pas.(j'avais cette réponse le 14/09/2011 à 18h17 mais par peur du ridicule...)
Merci pour la joute.





Joute n°44 : Technique de surface

Posté par
pepegeo
réponse joute 44 27-09-11 à 14:12

perduLes coins étant éloignés de 4 déplacement, ils doivent être tentés en premier
et minimiser les retours effaçants.
Mix entre solitaire, combat naval et jeu de taquin/tetris

1 - C3, B3, A3, A2, A1, B1, C1, C2
2 - C3, C2, B2, B1, C1, D1, D2, D3
3 - C3, C4, B4, A4, A5, B5, C5, C4
4 - C3, D3, D2, D1, E1, E2, E3, D3
5 - C3, D3, E3, E2, E3, D3
6 - C3, C4, D4, E4, E5, D5, C5, C4
7 - C3, C4, C5, B5, C5, C4
8 - C3, C4, C5, D5, C5, C4, C3
9 - C3, C4, C3

Total 60 mouvements pour 25 cases
Aucune certitude que c'est un optimum

Posté par
yoruichi_26
re : Joute n°44 : Technique de surface 02-10-11 à 15:12

gagnéSalut Godefroy,

Je propose 58 déplacements, qui sont les suivants :

C3 C2 C1 B1 A1 A2 B2 B3
C3 C2 C1 D1 E1 E2 D2 D3
C3 B3 B2 A2 A3 B3
C3 D3 D2 E2 E3 D3
C3 B3 A3 A4 A5 B5 C5 C4
C3 D3 E3 E4 E5 D5 C5 C4
C3 B3 B4 B5 C5 C4
C3 D3 D4 D5 C5 C4
C3 C4
C3

Merci.

Posté par
Gaellexd
Challenge 03-10-11 à 17:11

gagnéBonjour,

Je propose :

C3 > C2 > B2 > B1 > A1 > A2 > A3 > B3 > C3

C3 > B3 > A3 > A2 > A3 > B3 > C3

C3 > B3 > B4 > A4 > A5 > B5 > C5 > C4 > C3

C3 > C4 > C5 > B5 > C5 > C4 > C3

C3 > C4 > D4 > D5 > E5 > E4 > E3 > D3 > C3

C3 > D3 > E3 > E4 > E3 > D3 > C3

C3 > D3 > D2 > E2 > E1 > D1 > C1 > C2 > C3

C3 > C2 > C1 > D1 > C1 > C2 > C3

C3 > C2 > C3

Soit 58 Déplacements

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°44 : Technique de surface 05-10-11 à 09:13

Clôture de l'énigme :

La recherche de l'optimum semble avoir fait reculer certains. Pourtant, elle n'était pas si difficile que ça.

Posté par
caylus
re : Joute n°44 : Technique de surface 05-10-11 à 11:57

gagnéBonjour à tous,

Je suis vivement intéressé par un algorithme résolvant ce problème.
Peu importe le langage de programmation.
Merci d'avance.

Posté par
Rumbafan
re : Joute n°44 : Technique de surface 05-10-11 à 13:44

perduBonjour Godefroy,

J'ai contrôlé et contrôlé, mais mon parcours fait également 58 déplacements et laisse C3 nettoyé !!!

Pour chaque ligne je démarre de C3

Aurais-je omis quelque chose ?

Merci de contrôler

A+

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°44 : Technique de surface 05-10-11 à 13:53

Bonjour Rumbafan,

J'ai contrôlé une fois de plus (j'avais déjà vérifié 2 fois avant de mettre le poisson).
Il te manque la case C4 qui se resalit au cours du retour du 7ème passage.

Sur le dessin ci-dessous, les chiffres correspondent au numéro du passage.

Joute n°44 : Technique de surface

Vraiment désolé

Posté par
Rumbafan
re : Joute n°44 : Technique de surface 05-10-11 à 14:01

perduRe-salut

C4 reste sale...

Je n'avais pas 100%

B3 B4 A4 A3 B3 C3
était
B3 B4 A4 A3 C4 C3

Erreur de recopiage

Mea culpa



A+

Posté par
LeDino
re : Joute n°44 : Technique de surface 06-10-11 à 19:10

gagnéBonjour Caylus,

Je pense que personne n'a tenté de résoudre le problème par programmation.

D'abord parce qu'une telle résolution ne semble pas simple à réaliser.
Et ensuite, parce qu'elle conduirait probablement à une combinatoire explosive...
... sauf à introduire des règles de parcours qui limitent "intelligemment" le robot.

Mais pour déterminer ces règles "intelligentes" (comme par exemple, renoncer à tout cycle supérieur à 8 déplacements...) il faut d'abord faire une analyse mathématique du problème (à l'image de ce qu'a présenté très justement Castoriginal). Et en faisant cette analyse, on voit assez vite que 58 est le minimum théorique. Et comme en cherchant un peu, on trouve pas mal de solutions en 58... il n'est plus nécessaire de programmer.

Conclusion : la programmation ne semble pas adaptée pour trouver une solution plus rapidement qu'à la main...
Et le simple fait de réfléchir à une solution programmée "viable", nous met pratiquement sur la voie d'une solution manuelle...

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 136:38:22.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !