L’horloge de Berlin

– T’as vu la nouvelle horloge que je me suis achetée ?
– Nan, fais voir !
– Tiens, regarde:
deja_10h31.
– Trop cool !
– Mince, il est déjà 10h31, je suis en retard !

Fin de l’histoire. Ok, là vous allez dire que cette histoire n’a aucun sens. Et je ne pourrai que vous donner raison SAUF pour l’horloge. Il existe bel et bien une horloge comme sur le dessin et qui donne vraiment l’heure ! On peut la trouver à Berlin. La voici:

Pour l’anecdote, cette horloge a été inventée par un certain Dieter Binninger et elle fût installée pour la première fois en 1975 à Berlin.

Comme vous avez pu le constater, elle indique l’heure de manière plutôt étrange… Je vous propose d’essayer de comprendre son fonctionnement.

Explication du fonctionnement de l’horloge

Contrairement aux premières impressions, le principe  de cette horloge n’a rien de bien sorcier. L’idée est la suivante: chaque lampe allumée indique qu’une certaine durée de temps s’est écoulée. Plus précisément:

  • Chaque lumière de la première ligne représente 5 heures.
  • Chaque lumière de la deuxième ligne représente 1 heure.
  • Chaque lumière de la troisième ligne représente 5 minutes. (les lumières rouges indiquent les quarts d’heure)
  • Chaque lumière de la dernière ligne représente 1 minute.

Par exemple, quelle heure  indique l’horloge suivante ?quelle_heure_est_ilEh oui, il s’agit bien de 13h37 ! En effet:

  • deux lumières sont allumées dans la première ligne, donc cela donne 2x5h = 10h;
  • trois lumières sont allumées dans la deuxième ligne, ce qui donne 3x1h = 3h;
  • sept lumières sont allumées dans la troisième ligne, ce qui donne 7x5mn = 35mn;
  • deux lampes sont allumées dans la dernière ligne, ce qui donne 2x1mn = 2mn.

Il suffit ensuite d’additionner le tout: 10h + 3h + 35mn + 2mn = 13h et 37mn !

Mais pourquoi cette horloge est une vraie horloge ?

A priori, rien ne dit que chaque temps de la journée peut être représenté à l’aide de cette horloge (existence), ni même que chaque configuration de l’horloge ne peut représenter deux heures distinctes (unicité).

Nous allons donc prouver mathématiquement que c’est bien le cas et, pour cela, nous allons commencer par tout convertir en minutes. Comme vous le savez, dans une journée il y a 24 heures, ce qui fait 1440 minutes. Ainsi,

  • Chaque lumière de la première ligne indique que 5×60 = 300 mn se sont écoulées.
  • Chaque lumière de la deuxième ligne indique que 1×60 = 60 mn se sont écoulées.
  • Chaque lumière de la troisième ligne indique que 5 mn se sont écoulées.
  • Chaque lumière de la dernière ligne indique qu’1 mn s’est écoulée.

D’autre part, chaque temps de la journée, si on l’exprime en minutes écoulées depuis minuit, est représenté par un nombre entier compris entre 0 et 1440. Par exemple, 2h34 = 94 mn après minuit et 20h10 = 1210 minutes après minuit.

L’horloge de Berlin marche grâce à la proposition suivante:

Tout nombre entier N compris entre 0 et 1440 s’écrit de manière unique sous la forme:

N = c_1 \times 300 + c_2 \times 60 + c_3 \times 5 + c_4 \times 1

c_1, c_2 et c_4 sont des entiers compris entre 0 et 4 (inclus), et où c_3 est un entier compris entre 0 et 11 (inclus).

Le nombre c_1 donnera le nombre de lumières allumées dans la première ligne, le nombre c_2 le nombre de lumières allumées dans la deuxième ligne, etc.

Cette horloge représente 12h34. En effet, 12h34 = 754 mn = 2x300mn + 2x60mn + 6x5mn + 4x1mn

Cette horloge représente 12h34. En effet, 12h34 = 754 mn = 2x300mn + 2x60mn + 6x5mn + 4x1mn

Nous allons donc démontrer cette proposition pour voir que l’horloge de Berlin permet bien d’indiquer chaque moment de la journée. Vous allez le voir, la démonstration est similaire à celle qui donne l’existence et l’unicité de l’écriture d’un entier en base b.

Existence

Soit N est un entier avec 0 \leqslant N \leqslant 1440.

1ère étape: On effectue la division euclidienne de N par 300. On sait qu’il existe donc deux entiers c_1 et r_1 tels que:

N = c_1 \times 300 + r_1 \text{ avec } 0 \leqslant r_1 <300

Il reste à voir que c_1 est bien un nombre compris entre 0 et 4 inclus. Or, d’après la relation précédente, c_1 = \dfrac{N-r_1}{300}. Mais:

0 \leqslant N \leqslant 1440 \Rightarrow -300 < N-r_1 \leqslant 1440

donc

-1 < \dfrac{N-r_1}{300} \leqslant \dfrac{1440}{330} \simeq 4,8

Comme c_1 est entier, nous voyons ainsi que 0 \leqslant c_1 \leqslant 4.

2ème étape: On procède de manière similaire, et on effectue la division euclidienne du nombre r_1 précédent par 60. Il existe donc deux entiers c_1 et r_1 tels que

r_1 = c_2 \times 60 + r_2 \text{ avec } 0 \leqslant r_2 < 60

De la même manière qu’à la première étape, on va utiliser le fait que c_2 = \dfrac{r_1-r_2}{60} pour montrer que c_2 est un entier compris entre 0 et 4. Or, 0 \leqslant r_1 < 300 et 0 \leqslant r_2 <60 donc:

-1 < \dfrac{r_1 - r_2}{60} < \dfrac{300}{60}=5

Nous voyons ainsi que 0 \leqslant c_2 \leqslant 4. D’autre part,

N = c_1 \times 300 + r_1 = c_1 \times 300 + c_2 \times 60 + r_2.

 Vous voyez qu’en continuant ainsi les divisions euclidiennes successives, on arrivera à la propriété voulue…

3ème étape: On effectue la division euclidienne de r_2 par 5. Il existe donc deux entiers c_3 et r_3 tels que:

r_2 = c_3 \times 5 + r_3 \text{ avec } 0 \leqslant r_3 < 5

Cette fois-ci, nous allons voir que c_3 est compris entre 0 et 11 (inclus). En effet, on a c_3 = \dfrac{r_2 - r_3}{5} et comme 0 \leqslant r_2 < 60:

\dfrac{-5}{5} < \dfrac{r_2 - r_3}{5} < \dfrac{60}{5} =12

donc 0 \leqslant c_3 \leqslant 11. De plus,

N = c_1 \times 300 + c_2 \times 60 + r_2 = c_1 \times 300 + c_2 \times 60 + c_3 \times 5 + r_3

4ème étape: Pour finir, va-t-on faire la division euclidienne de r_3 par 1 ? Non ! (car faut pas déconner non plus, se lancer dans une division par 1 n’a rien de bien passionnant…). On va tout simplement poser c_4 = r_3 et comme on a vu que r_3 <5, on  a donc immédiatement 0 \leqslant c_3 \leqslant 4, ainsi que la relation

N = c_1 \times 300 + c_2 \times 60 + c_3 \times 5 + c_3 \times 1

Exemple en pratique: La preuve précédente nous donne évidemment un algorithme de décomposition pratique, et voici par exemple comment on a décomposé 12h34 = 754 mn:

754 = 2×300 + 154 = 2×300 + 2×60 + 34 = 2×300 + 2×60 + 6×5 + 4

Unicité

Pour l’unicité, nous allons supposer que N se décompose de deux façons différentes:

N= c_1 \times 300 + c_2 \times 60 + c_3 \times 5 + c_4 = c'_1 \times 300 + c'_2 \times 60 + c'_3 \times 5 + c'_4

ce qui, en faisant passer certains termes de l’autre côté, nous donne l’égalité :

(c_1 - c'_1)\times 300 + (c_2 - c'_2) \times 60 + (c_3 - c'3) \times 5 = c'_4 - c_4

d’où:

[(c_1 - c'_1)\times 60 + (c_2 - c'_2) \times 12 + (c_3 - c'3) ] \times 5 = c'_4 - c_4 (*)

Cela montre que l’entier c'_4 - c_4 est un multiple de 5. Mais, comme les nombres c_4 et c'_4 sont compris entre 0 et 4 inclus, on a aussi les inégalités suivantes: -4 \leqslant c'_4 - c_4 \leqslant 4. Vous en connaissez beaucoup des multiples de 5 compris entre -4 et 4 ? Il n’y en a pas énormément… Pour ne rien vous cacher, le seul est 0 ! Cela veut donc dire que c'_4 - c_4 = 0 et donc c'_4 = c_4.

L’égalité (*) devient alors:

[(c_1 - c'_1)\times 60 + (c_2 - c'_2) \times 12 + (c_3 - c'3) ] \times 5 = 0

et donc:

(c_1 - c'_1) \times 60 + (c_2 - c'_2) \times 12= c'_3 - c_3

Et là, rebelote, on suit le même raisonnement que précédemment, en commençant par factoriser:

[(c_1 - c'_1) \times 5 + (c_2 - c'_2) ] \times 12 = c'_3 - c_3 (**)

Et donc, c'_3 - c_3 est un multiple de 12, mais comme 0 \leqslant c_3 , c'_3 \leqslant 11, on en déduit que -11 \leqslant c'_3 - c_3 \leqslant 11. Puisque le seul multiple de 12 compris entre -11 et 11 est 0, on a donc bien c'_3 = c_3 !

On reprend ensuite l’équation (**), qui devient:

[(c_1 - c'_1) \times 5 + (c_2 - c'_2) ] \times 12 = 0

d’où:

(c_1 - c'_1) \times 5 = c'_2 - c_2 (***)

Bon, je pense qu’au bout de la troisième fois vous commencez à comprendre l’idée: c'_2 - c_2 est un multiple de 5 qui vérifie -4 \leqslant c'_2 - c_2 \leqslant 4, ce qui donne donc c'_2 = c_2. Et l’égalité (***) devient alors c_1 - c'_1 = 0 d’où c_1 = c'_1.

Voilà pour l’unicité. Joli, non ?

Votre propre horloge de Berlin !

J’ai écrit un programme qui affiche l’heure (en temps réel) comme l’horloge de Berlin. Voici une capture d’écran:

programme_horloge_de_BerlinCe programme a été écrit en Python, et s’il vous intéresse, le code est disponible dans le lien suivant: http://pastebin.com/6DCR9WQM

Note:

Une des raisons pour lesquelles nous avons pu faire cette décomposition est le fait que 1mn divise 5 mn, qui elles-mêmes divisent 60mn, qui elles-mêmes divisent 300mn.  Pour ceux qui aiment les horloges exotiques, voici un article sur Arxiv (lien direct vers le pdf) qui reprend cette idée, avec 1mn, 6mn, 30mn, 2h=120mn et 6h=360mn, pour créer une horloge triangulaire, dont voici quelques beaux exemples:

Horloge_triangulaire

Advertisements
Cet article, publié dans Arithmétique, est tagué , , , , . Ajoutez ce permalien à vos favoris.

5 commentaires pour L’horloge de Berlin

  1. C’est très amusant et étonnant! Je ne suis pas étonné par le résultat mathématique mais bien par sa mise en oeuvre publique!

    Quant au résultat mathématique, on peut le comprendre dans le cadre de la théorie des systèmes de numération. L’utilisation de la division euclidienne pour trouver les chiffres successifs est une manifestation de l’algorithme glouton qu’on applique dans une vaste famille de systèmes de numération généralisant les systèmes de position. Dans ces systèmes, on remplace la suite des puissances de la base par une suite strictement croissante d’entiers U_i commençant par U_0=1. Pour avoir un alphabet de chiffres fini, il faut et il suffit que le quotient U_{i+1}/U_i soit borné. Pour décomposer un nombre n, on détermine i pour que U_i\leqslant n < U_{i+1} et on prend comme premier chiffre le quotient de n par U_i. Ensuite, on remplace n par le reste de sa division par U_i et on recommence. On intercale des 0 entre les premiers chiffres ainsi obtenus de manière que le rang de chaque chiffre soit celui de l'élément de U à l'aide duquel on a obtenu. L'algorithme glouton donne une décomposition canonique de chaque entier mais, en général, un même entier possède plusieurs décompositions comme combinaison linéaire des U_i. Le système construit de la sorte avec la suite des nombres de Lucas s'appelle le système de Zéckendorf. Dans le cas de l'horloge berlinoise, les nombres 1, 5, 60, 300 peuvent être vus comme l'analogue de la base U et les divisions successives réalisées pour coder une heure sont la manifestation de l'algorithme glouton.

    Une remarque pour finir : l'application qui associe à n sa représentation dans la base U est strictement croissante quand on ordonne l'ensemble des représentations, vues comme des mots sur l'alphabet des chiffres, selon l'ordre généalogique. Cette observation est à la base de la création d'une vaste généralisation des systèmes de numération connus au moment de son introduction : les systèmes de numération abstraits. Ceux-ci sont étudiés depuis plus d'une dizaine d'années et ont donné lieu à de nombreux résultats importants dont des généralisations difficiles de deux théorèmes fondamentaux de Cobham. Pour une première approche de ces systèmes, je suggèrerais le chapitre 3 du livre : Combinatorics, Automata and Number Theory paru au Cambridge University Press en 2010.

    En tout cas, merci pour ce bel article!

  2. Ping : Animations diverses – scratchlouisemichel

  3. Anonyme dit :

    merci vous m avez bien aidé

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s