horloge .pdf



Nom original: horloge.pdf

Ce document au format PDF 1.5 a été généré par LaTeX with hyperref package / xdvipdfmx (20140317), et a été envoyé sur fichier-pdf.fr le 02/11/2016 à 17:42, depuis l'adresse IP 89.93.x.x. La présente page de téléchargement du fichier a été vue 423 fois.
Taille du document: 574 Ko (5 pages).
Confidentialité: fichier public


Aperçu du document


L’horloge de Prague
L’horloge de Prague1 , création du maître horloger Mikulas de Kadan, a un système de sonnerie très
particulier, par exemple 5h se décompose en 3 bong une pause et deux bong, et 6h se décompose en 1
bong une pause 2 bong une pause 3 bong.

Cette manière de procéder suit un principe très simple, prenons la suite périodique de motif 123432
1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 2
si nous plaçons des + et des , judicieusement nous obtenons
1, 2, 3, 4, 3 + 2, 1 + 2 + 3, 4 + 3, 2 + 1 + 2 + 3, 4 + 3 + 2, ...
c’est à dire la suite des entiers naturels non nuls. Il est facile de le vérifier jusqu’à 24 ce qui est
suffisant pour l’horloge de Prague mais c’est une propriété qui est toujours vraie, la construction se
poursuit indéfininiment. Plusieurs questions se posent
• comment justifier que la construction se poursuit indéfiniment ?
• existe-t-il d’autres motifs qui possèdent la même propriété ?
Avant de répondre à ces deux questions, on peut observer que si dans le motif initial on remplace le
4 par 3 1, le motif obtenu vérifiera la même propriété, il suffit de remplacer le 4 qui apparait dans
1, 2, 3, 4, 3 + 2, 1 + 2 + 3, 4 + 3, 2 + 1 + 2 + 3, 4 + 3 + 2, ...
par 3 + 1 à chaque fois,
1, 2, 3, 3 + 1, 3 + 2, 1 + 2 + 3, 3 + 1 + 3, 2 + 1 + 2 + 3, 3 + 1 + 3 + 2, ...
1 On pourra consulter l’article Prague Clocks de Chan Bae , John Conway , Lukas Kohlase et Sunghyuk Park dans The
mathematical intelligencer, vol 1, 2016

1

On peut donc passer du motif 123432 au motif 1233132 en décomposant, a contrario, il est possible de
passer du motif 1233132 au motif 123432 en fusionnant le 3 et le 1 (où chaque fois le motif a la propriété
de l’horloge de Prague, et on dira que le motif convient). Un motif qui convient et que l’on ne peut
réduire en fusionnant, est un motif minimal. Nous allons décrire les motifs minimaux. Considérons un
motif minimal M = a0 . . . ap−1 qui convient et où les ai sont des entiers naturels non nuls, et prolongeons
la suite an en posant an = an mod m pour tout n ∈ N avec m = a0 + . . . + ap−1 , l’entier étant désigné
comme la somme du motif M . Lorsque l’on décompose les entiers naturels, les césures se font sur un
terme de la suite (le lecteur attentif observera que nécessairement i0 = 0),
a0 . . . ai0 , . . . ai1 , , . . . , . . . , ain , . . .
• La suite (in mod p)n parcourt tous les entiers de 0 à p, en effet si l’entier r n’est pas présent alors en
fusionnant ar et a(r+1) mod p on obtient par fusion un motif qui convient, ce qui contredit le caractère
minimal.
• La somme a0 +. . .+ain = 1+. . .+n−1 = (n−1)n
= tn−1 où tk désigne le k-ième nombre triangulaire,
2
ne peut prendre qu’un nombre fini de valeurs modulo m. Dans la suite a0 , . . . ain le motif M apparait
un certain nombre de fois, disons k fois et il reste quelques éléments de sorte tn−1 mod m ne peut
prendre comme valeurs que 0, a0 , a0 + a1 , . . . , a0 + . . . + ap−2 (ce qui détermine la valeur de p).
• Un simple calcul montre que



 tn+2m =

(n+2m)(n+2m+1)
2



 t
2m−n−1 =

= tn +

(2m−n−1)(2m−n)
2

= tn

2nm
2

+

2m(n+2m+1
2

= tn

mod m

mod m

de sorte que pour connaître les valeurs de la suite (tn mod m) il suffit de calculer t0 mod m, . . . , tm
mod m. Si l’on prend toutes ces valeurs, qu’on les classes dans l’ordre croissant et que l’on met à la
suite m, on obtiendra
0, a0 , a0 + a1 , . . . , a0 + . . . + ap−2 , a0 + . . . + ap−1 = m
ce qui permet de reconstituer le motif M = a0 . . . ap−1 .
Nous avons montré que si M est un motif de somme m qui convient alors il est unique et il est
entièrement déterminé par la connaissance de t0 mod m, . . . , tm mod m. Nous allons justifier que si m
est un entier naturel non nul et si M = a0 . . . ap−1 est obtenu par cette construction alors le motif M
est un motif qui convient et qui est minimal.
• il existe des indices i0 , . . . , ip−2 ∈ [[0, m − 1]] tel que a0 = ti0 mod m, . . ., a0 + . . . + ap−2 = tip−2
mod m et 0, ti0 mod m, . . . , tip−2 mod m sont les seules valeurs de la suite (tn mod m)n .
• Supposons que le motif permet de construire les entiers jusqu’au rang q − 1. Il existe un entier i
tel que 1 + . . . + q − 1 mod m est une des valeurs 0, ti0 mod m, . . . , tip−2 mod m et donc pour un
certain indice i ∈ [[0, p − 1]] a0 + . . . + ai mod m, ce qui signifie la décomposition de q − 1 s’arrête à
ai . Nous sommes donc dans la situation suivante
. . . ai , ai+1 ai+2 . . .
où ai est la césure qui correspond à q − 1 et l’on cherche où placer éventuellement la césure suivante
pour obtenir q. Il existe un entier j tel que 1 + . . . + q = a0 + . . . + aj mod m. Par conséquent,


ai+1 + . . . + aj mod m
q = 0 mod m


ai+1 + . . . + ap−1 + a0 + . . . + aj
2

si i < j
si i = j
mod m si j < i

Il est donc possible d’obtenir q en additionnant un certain nombre d’éléments consécutifs du motif
à partir de ai+1 , le modulo m étant réalisé en répétant plusieurs fois un cycle complet soit dans le
premmier cas ai+1 . . . ap−1 a0 . . . ai . Il nous reste à observer que t1 mod m = 1 fait partie des valeurs
de 0, a0 , a0 +a1 , . . . , a0 +. . .+ap−2 , a0 +. . .+ap−1 = m et donc a0 = 1 de sorte que la construction est
possible au rang 1 donc est initialisée. Comme par construction tous les termes du motif apparaissent
comme césure, le motif est minimal.

Soit m un entier naturel non nul. Si l’on note 0 < b0 < . . . < bp−2 les valeurs
classées dans l’ordre de la suite t0 mod m, . . . , tm mod m, et si on pose a0 =
b0 , a1 = b1 − b0 , . . . , ap−2 = bp−2 − bp−3 , ap−1 = m − bp−2 alors le motif M = a0 . . . ap−1
est un motif minimal qui convient.
Il est facile de construire le motif associé à un entier m avec une fonction python




def Prague (m) :
ens=set ([n*(n+1)//2 % m for n in range (m)])
L=list(ens)
L. append (m)
L.sort ()
M=[L[i+1]-L[i] for i in range (len(L)-1)]
return M



et on constate que
>>> Prague ( 1 5 )
[1 , 2 , 3 , 4 , 3 , 2]

Il est facile d’obtenir le premier motif qui contient un nombre plus grand que 24, c’est 665.
>>> Prague ( 6 6 5 )
[1 , 2 , 3 , 4 , 5 ,
3, 4, 3, 5,
3 , 7 , 2 , 6 , 14 ,
2 , 5 , 13 , 8 ,
9 , 5 , 5 , 1 , 10 ,
15 , 7 , 1 , 5 ,
4 , 1 , 2 , 10 , 2 ,

5 , 1 , 7 , 8 , 2 , 3 , 4 , 3 , 7 , 8 , 3 , 10 , 2 , 5 , 2 , 6 , 7 , 3 , 4 , 10 , 5 , 13 ,
2 , 3 , 2 , 6 , 10 , 7 ,
1 , 5 , 2 , 12 , 1 , 7 , 7 , 3 , 5 , 13 , 7 , 3 , 5 , 2 , 3 , 2 , 7 , 5 , 11 , 10 , 2 ,
12 , 7 , 1 , 7 , 3 , 5 ,
4 , 1 , 7 , 5 , 2 , 5 , 16 , 2 , 5 , 2 , 10 , 1 , 14 , 6 , 4 , 3 , 8 , 17 , 5 , 2 , 3 ,
2 , 2 , 3 , 7 , 11 ,
5 , 8 , 7 , 3 , 3 , 25 , 4 ]

Pour le motif de l’horloge de Prague, qui était l’objet du challenge, M. Réda Iks2 a proposé le premier
le code python suivant

2 PCSI-PC*

3







def liste_entiers (n) :
"""
En sommant successivement les éléments de la liste redondante [1,2,3,4,3,2] on
constitue sous forme de chaines de caractères les n premiers entiers
naturels
"""
L=[1,2,3,4,3,2] # Création de la liste redondante
position =0 # initialisation de la position sur la liste redondante
S=[] # Initialisation de la liste en Sortie
t=0 # Initialisation de l'entier t que l'on souhaite former avec les éléments
de la liste L
while t<n : # tant que nous ne sommes pas parvenus à l'entier n (peut être
remplacé par une boucle for)
t+=1 # On passe à l'entier t suivant
k=0 # initialisation de la somme qui devra donner l'entier t
s= ’ ’ # initialisation des chaines de caractères
while k<t : # tant que les éléments de la liste ne sont pas suffisants pour
former l'entier t
l=L[ position ] # sélection l'élément suivant de la liste
if k==0 : # si nous n'avons pas encore commencé à sommer
k+=l # On commence à sommer
s+= str(l) # On met le premier élément dans la chaine de caractère
elif k>0 : # une fois que nous avons commencé à sommer
k+=l # on continue à sommer
s+= ’+ ’ +str(l) # On concatène l'élément dernièrement sommé avec le
reste de la chaine de caractère d'où la nécessité de mettre un
signe '"+" pour plus de compréhension
position +=1 # On passe à lélément suivant de la liste
if position >5 : # Si nous avons dépassé la longuer de la liste L
position =0 # On reprend la liste dès le début ( puisqu 'elle est
redondante )
S. append (s) # On ajoute la chaine de caractère permettant de trouver l'
entier t aux entiers précédents déjà stockés dans la liste en sortie
return (S) # renvoie la liste S





La fonction Conway(n,m) permet de construire les décompositions jusqu’à l’entier n, pour le motif
minimal de somme m.


def Conway (n,m) :
L= Prague (m) # liste des chiffres du motif de somme m
print ( ’ l e m o t i f e s t {} ’ . format (L))
q=len(L)
liste =[] # contient la liste des chaines de caractères
i=0
# L[i%6] est le chiffre numéro i de la suite périodique à partir de l'
indice 0
for j in range (1,n+1) : #j est le chiffre à décomposer
s=L[i%q]
#s est la somme des chiffres à partir de l'indice i
chaine =str(L[i%q]) #la chaine à construire
while s !=j :
# construction de la chaine
i+=1
a=L[i%q]
# chiffre suivant
s+=a
chaine += ’+ ’ +str(a)
i+=1
# passage à l'indice du chiffre suivant
liste. append ( chaine )# ajout de la chaine construite
return (liste )



et par exemple,

4



>>> Conway( 9 , 1 5 )
l e motif est [ 1 ,
[ ’1 ’ , ’2 ’ , ’3 ’ ,
>>> Conway( 9 , 2 3 )
l e motif est [ 1 ,
[ ’ 1 ’ , ’ 2 ’ , ’2+1 ’

2 , 3 , 4 , 3 , 2]
’ 4 ’ , ’3+2 ’ , ’1+2+3 ’ , ’4+3 ’ , ’2+1+2+3 ’ , ’4+3+2 ’ ]
2 , 2 , 1 , 3 , 1 , 3 , 2 , 5 , 1 , 1 , 1]
, ’3+1 ’ , ’3+2 ’ , ’5+1 ’ , ’1+1+1+2+2 ’ , ’1+3+1+3 ’ , ’2+5+1+1 ’ ]

Comme tous les motifs qui conviennnent permettent de construire tous les entiers naturels non nuls,
tous les motifs minimaux permettent de construire une horloge.

5


horloge.pdf - page 1/5


horloge.pdf - page 2/5


horloge.pdf - page 3/5

horloge.pdf - page 4/5

horloge.pdf - page 5/5


Télécharger le fichier (PDF)


horloge.pdf (PDF, 574 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


horloge
info
ds 01 b final
centrale 2019   tsi  m19ci1e 1
polys c mm
structures repetitives

Sur le même sujet..