L'horloge grecque

 Niveau énigmesPartager :
			        
L'horloge grecque
Posté par 
Alishisap  10-01-18 à 12:07
Bonjour à tous,

j'ai lu dans un livre l'existence d'étranges horloges en Grèce. Elles ressembleraient à nos horloges modernes, avec les même nombres, mais elles sont dépourvues d'aiguilles, et il y a une lettre grecque en-dessous de chaque nombre.

En fait, une telle horloge possède chacune des lettres suivante, deux fois chacune : , , , ,  et .

Dans ce livre, il est indiqué que ces horloges seraient considérées comme réglées si et seulement si les deux lettres identiques de chaque paire se font face (i.e sont diamétralement opposées). Exactement comme dans la représentation précédente. Le livre précise également qu'il n'est pas obligatoire que les lettres soient exactement dans l'ordre ,  etc., il suffit que quelle que soit la lettre grecque qu'on regarde sur l'horloge, alors on trouve la même lettre en "avançant de 6 heures".

Le problème, c'est qu'une telle horloge peut se dérégler.

Par un mécanisme ingénieux, on peut en effet appuyer sur un des douze nombres de l'horloge. Appelons N ce nombre. Si donc on appuie sur N, alors la lettre grecque se situant en N cède sa place à la lettre grecque suivante (dans le sens des aiguilles d'une montre), qui laisse alors un emplacement vide où va se placer la lettre grecque suivante et ainsi de suite. On répète cette opération N fois. Finalement, la lettre grecque qui auparavant se situait à l'emplacement N prend le dernier emplacement vide.

Ci-dessous, on peut voir ce qu'il se passe lorsqu'on appuie, à partir de l'horloge de l'image précédente, successivement sur 5 (horloge de gauche) puis sur 7 (horloge de droite).

Bref, tout à fait par hasard, je vais chez un antiquaire et voilà que je tombe sur une horloge grecque ! Je l'achète, et à la maison je remarque (évidemment) qu'elle a été déréglée par des dizaines de curieux qui ont appuyé au hasard sur certains nombres.

Voici à quoi cette horloge ressemble maintenant :

Nous supposerons que cette horloge est réglable.

Pouvez-vous m'aider à régler cette horloge, en m'indiquant sur quels nombres, successivement, je dois appuyer ?

Questions subsidiaires pour ceux qui en redemande :

- Comment minimiser le nombre d'opérations ?

- Y a-t-il plusieurs manières d'atteindre ce minimum ?

- Existe-t-il une configuration de départ, réglable, tel que le nombre minimum d'opérations à effectuer pour la régler est au moins de 10 ?

- Existe-t-il des configurations de base non réglables ?

A vous de jouer ! 
 Posté par 
Alishisapre : L'horloge grecque  10-01-18 à 12:12
Erratum

Citation :
En fait, une telle horloge possède chacune des lettres suivante, deux fois chacune : , , , ,  et .

Il s'agit bien de  (zêta) et non de  (êta).
 Posté par 
dpire : L'horloge grecque  10-01-18 à 16:10
Bonjour

Je ne pense pas participer car cela me semble bien complexe .

Bonne chance aux candidats 
 Posté par 
Alishisapre : L'horloge grecque  10-01-18 à 16:36
Bonsoir dpi,

tu es tout pardonné.  Mais ton message indique que tu as au moins lu l'énoncé jusqu'au bout ce qui me fait déjà plaisir. 

Au passage, j'ai remarqué que j'ai indiqué que ces horloges possèdent les mêmes nombres...

Or par inadvertance j'ai mis un 0 à la place d'un 12  (mais cela ne perturbera personne : que cela soit 0 ou 12, d'après les règles rien ne se produit quand on appuie sur ce nombre)
 Posté par 
Alishisapre : L'horloge grecque  10-01-18 à 16:41
Hum... En fait c'est un peu plus délicat que ça dans le cas où c'est 12 et non 0.

Considérez donc que c'est bien 0 et qu'il ne se passe rien. 
 Posté par 
dpire : L'horloge grecque  10-01-18 à 17:16
Je pense que ton énoncé devrait être repensé pour être sexy 
 Posté par 
Alishisapre : L'horloge grecque  10-01-18 à 17:23
Sur le fond ou la forme ? 
 Posté par 
veledare : L'horloge grecque  10-01-18 à 17:44
bonjour,

Alishisap

j'ai lu l'énoncé,je vais aller faire une heure ou deux de repassage pour y réfléchir mais pas sûre du tout  que cela suffise

merci   pour tous ces problèmes originaux
 Posté par 
dpire : L'horloge grecque  11-01-18 à 08:36
>veleda

On te souhaite un bon repassage puis tu repasses 
 Posté par 
LittleFoxre : L'horloge grecque  11-01-18 à 12:17

Ce problème avait l'air vraiment compliqué mais au final non .

 Cliquez pour afficher

Il y a énormément d'horloge possible mais beaucoup sont équivalentes en effet renommer les symboles ne change rien. On peut renommer le premier symbole rencontré 'a', le second 'b', etc. On a donc 12!/26/6! = 10395 horloges différentes, et depuis chaque horloge 12 arêtes sortantes, c'est beaucoup mais largement abordable par un ordinateur. 

Parmi ces horloges, seule l'horloge 'abcdefabcdef' est réglée.

Pour répondre à toutes les questions il 'suffit' de créer le graphe des horloges puis de calculer la distance de chaque horloge vers l'horloge réglée.

Je vais commencer par les questions subsidiaires parce qu'elles sont en fait plus faciles 

- On minimise le nombre d'opération en suivant un chemin qui fait strictement décroître la distance à l'horloge réglée.

- Oui, il y a plusieurs chemin minimum entre certaines horloges. Par exemple pour l'horloge de la question, tous les chiffres sauf le 0 nous en rapproche.

- Non, la distance maximale à l'horloge réglée est 7 opérations. Il y a 87 horloges différentes à cette distance.

- Non, toutes les horloges sont à une distance finie (7) de l'horloge réglée.

Pour régler l'horloge donnée une solution (parmi beaucoup d'autres) est d'appuyer successivement sur 1,4,3,5,9,4 donc 6 opérations :

bgezezddagba 

1 begzezddagba

4 begzzddaegba

3 begzddzaegba

5 begzdzaegbda

9 egzdzabegdab

4 egzdabegzdab

from collections import defaultdict, deque

def getSignature(position):
    # Seule la signature 'abcdefabcdef' est réglée
    d,signature,count = {},'',0
    base = ord('a')
    for c in position:
        if c not in d:
            d[c] = chr(base+count)
            count += 1
        signature += d[c]
    return signature

def getNextPositions(position):
    ans = []
    for i in range(6):
        ans.append(position[:i] + position[i+1:2*i+1] + position[i] + position[2*i+1:])
    for i in range(6,12):
        ans.append(position[1:2*i-11] + position[i] + position[2*i-11:i] + position[i+1:] + position[0])
    return ans

def getGraph():
    G = defaultdict(set)
    D = {'abcdefabcdef':0}
    seenNodes, newNodes = set(), {'abcdefabcdef'}
    while newNodes:
        node = newNodes.pop()
        seenNodes.add(node)
        for n in map(getSignature,getNextPositions(node)):
            G[n].add(node)
            if n not in seenNodes:
                newNodes.add(n)
                
    newNodes = deque()
    newNodes.append('abcdefabcdef')
    D = {'abcdefabcdef':0}
    while newNodes:
        node = newNodes.popleft()
        for n in G[node]:
            if n not in D:
                D[n] = D[node] + 1
                newNodes.append(n)
    return G,D

def solve(position):
    G,D = getGraph()
    print(position)
    while getSignature(position) != 'abcdefabcdef':
        ds = list(D[n] for n in map(getSignature,getNextPositions(position)))
        i = ds.index(min(ds))
        position = getNextPositions(position)[i]
        print(i,position)

solve('bgezezddagba')

Merci pour ce joli problème 
 Posté par 
Alishisapre : L'horloge grecque  11-01-18 à 16:42
Bonjour LittleFox et merci pour ta participation ! 

 Cliquez pour afficher
Je n'ai rien à ajouter, c'est du très beau boulot et une analyse bien plus complète que ce que j'ai moi-même tenté de faire.  Je valide ta solution à 6 mouvements qui est bien le minimum pour cette configuration.

Tiens, je t'en rajoute une : parmi les solutions à 6 mouvements pour cette configuration, essaye de trouver celle(s) qui permet(tent) d'appuyer sur le moins de chiffres différents possible (on a la flemme de bouger le doigt  )

Citation :
Ce problème avait l'air vraiment compliqué mais au final non

N'est-ce pas ?  Il faut pas surestimer mes problèmes, il faut que moi-même je sois capable de les résoudre !  Cela incitera peut-être dpi à s'y essayer. 
 Posté par 
dpire : L'horloge grecque  11-01-18 à 17:21
Quand je vois la complexité de la réponse de l'excellent  Littlefox, je ne

me risque pas à faire mieux 

Ce qui est certain c'est que nous ne sommes pas le s derniers à animer.
 Posté par 
Alishisapre : L'horloge grecque  11-01-18 à 17:52
Je n'espère pas ! 
 Posté par 
LittleFoxre : L'horloge grecque  11-01-18 à 19:19
@Alishisap

 Cliquez pour afficher

Il y a 93 chemins possibles depuis l'horloge donnée vers une horloge réglée.

Parmis ces chemins 6 n'utilisent que 3 chiffres ce qui est le minimum mais ce n'est pas comme ça qu'on bouge le moins possible le doigt (on fait beaucoup d'aller retour):

1, 7, 1, 7, 5, 7

1, 7, 8, 1, 7, 7

4, 4, 4, 10, 8, 8

5, 4, 5, 8, 4, 8

7, 2, 8, 2, 7, 7

8, 7, 7, 2, 2, 7

Si on compte la distance totale que le doigt doit bouger (on considère que l'on fait le tour de l'horloge et qu'on ne la traverse pas pour rester simple) alors il n'y a qu'un seul minimum et il nous fait bouger le doigt de 5  crans (heures?) :

5,4,4,4,7,8

Si on compte qu'il faut une seconde pour aller d'une heure à l'autre mais qu'appuyer une seconde fois sur la même heure prend un temps négligeable alors le minimum est 2 secondes avec (unique minimum) :

4,4,4,10,8,8

Merci énormément à dpi et Alishisap et mijo d'animer autant cette rubrique .

Merci à tous ceux qui prennent le temps de réfléchir à un problème, le mettre en forme et le soumettre à nos petites méninges 
 Posté par 
Alishisapre : L'horloge grecque  12-01-18 à 10:17
@LittleFox

 Cliquez pour afficher
Bien vu, j'avais aussi retenu 4,4,4,10,8,8 que je trouve joli. 

Le minimum serait 2 secondes... Sans compter le temps que prendrait le système mécanique pour effectuer les modifications nécessaires ! 

 Posté par 
javatasmaniere : L'horloge grecque  13-01-18 à 19:58
Bonjour
 Cliquez pour afficher

pour n=0, pas de modification de la position des lettres
Si on différencie chaque lettre, il y a  situations possibles.
On réduit ce nombre grâce aux paires de lettres égales : 
Il y a donc  situations différentes.
Et si on choisit aussi de permuter les lettres de ces situations pour qu'elles apparaissent dans l'ordre naturel, on réduit encore ce nombre.
Il reste  positions initiales distinctes, à une permutation près des lettres.

Dans une position réglée, il est facile de voir que les lettres forment une symétrie centrale. Et en conséquence que les 6 premières positions contiennent les 6 lettres, les 6 dernières de même.

Avec le réarrangement des lettres, on peut considérer qu'il n'y a QU'UNE SEULE position réglée (à  permutations des lettres près)

Je pars de cette situation réglée et je génère en nombre de coups croissants toutes les situations possibles (en éliminant celles déjà rencontrées, toujours à une permutation des lettres près).

J'ai donc trouvé exactement  (situation initiale comprise) situations différentes (à une permutation des lettres près)

J'en déduis que TOUTE situation initiale est réglable.

Le réglage de l'horloge donnée nécessite au minimum 6 coups. 

Désolé, j'avais vraiment envie de vous montrer cette image, mais je n'ai pas trouvé comment l'insérer dans la zone masquée. Enfin, le topic a déjà reçu de nombreuses réponse, donc je pense qu'on ne m'en voudra pas trop

En image : 

malou edit > il suffit de mettre le [/blank] après l'image....et pour charger l'image au bon endroit, on écrit dans le texte,  l'endroit voulu,  img1 entre crochets
 Posté par 
javatasmaniere : L'horloge grecque  13-01-18 à 20:09
Au fait, si vous voulez prolonger l'expérience, voici deux options auxquelles je me suis frotté, qui peuvent être essayées séparément ou ensemble : 

Que se passe-t-il si au lieu du 0, on conserve le 12 ? (le mouvement généré est un peu spécial)

- a-t-on toujours une solution pour chaque situation ?

- quelle longueur minimale pour la situation de l'énoncé ?

- quelle longueur minimax ? (au fait, la mnimax de l'énigme initiale est 7)

Et si le nombre de lettres déplacées n'était pas fonction de la position (de 0 à 11, ou de 1 à 12), mais fonction de la lettre qui est à la position choisie

exemple : 

et si on choisit une position dans laquelle on a un , alors on décale 3 lettres dans le sens trigonométrique, et  est déplacée dans le trou formé.
  Posté par 
Alishisapre : L'horloge grecque  16-01-18 à 15:58
Bonjour javatasmanie,

 Cliquez pour afficher
Bravo pour ton travail, tu as trouvé les mêmes réponses que LittleFox et ta solution est correcte. 

Je réfléchirai aux extensions que tu proposes...