D.S. 1 I.P.T. MP

Exercice 1. On demontre que l’ensemble N × N est denombrable (i.e. en bijection avec N) ennumerotant chaque couple (x, y) ∈ N2 suivant le procede suggere par la figure ci-dessous, appeleenumerotation de Cantor de N2 :

a) Ecrire une fonction recursive Cantor(x,y) qui retourne le numero du point de coordonnees(x, y).

b) Ecrire une fonction recursive CantorInverse(n) pour la fonction reciproque.

N.B. On veillera a ne pas multiplier les appels recursifs.

c) Il est facile de donner une formule explicite pour la fonction Cantor(x,y) mais on ne lademande pas ici. En revanche, mathematiquement, pour definir CantorInverse(n) on doitdistinguer le cas ou n prend une des valeurs 0,1,3,6,10... marquees sur l’axe des abscissesdu schema. On note (Tk)k∈N la suite de ces valeurs :

(i) Definir (Tk)k∈N mathematiquement.

(ii) Ecrire une fonction imperative Tk(n) qui renvoie True si n est une valeur de cette suite(Tk) et False sinon.

Exercice 2. On s’interesse ici au nombre de facons d’obtenir n euros avec des pieces et des billetsde 1,2,5 et 10 euros.

Par exemple n = 5 peut se decomposer en 1+ 1+ 1+ 1+ 1, 1+ 1+ 1+ 2, 1+ 2+ 2, 5, ce qui donne4 facons.

D’une maniere generale une decomposition sera donc donnee par un quadruplet [a1, a2, a5, a10]tel que a1 × 1 + a2 × 2 + a5 × 5 + a1010 = n.

Il est utile pour la suite de penser que n = 0 admet une decomposition associee au quadruplet[0,0,0,0].

1) On veut ecrire une fonction comptepiece qui recoit comme parametre un entier n et quirenvoie le nombre de decompositions comme ci-dessus.Indication – On peut separer les decompositions entre celles qui contiennent (au moins) un billetde 10 euros et les autres.

Pour compter les decompositions de n qui contiennent un billet de 10 euros, il est equivalentde compter celles de n − 10.

Pour les autres decompositions de n, on est ramene a une decomposition avec une liste pluspetite.

Ainsi, une bonne facon de resoudre ce probleme est de le generaliser : on ecrira plutot unefonction compteavecListe(n,L) qui prend comme argument n et L ou n est un entier strictementpositifs et L est une liste d’entiers et compteavecListe renvoie le nombre de facons d’ecrire n

comme somme d’elements de L. On en deduira ensuite facilement la fonction comptepiece.

2) (Plus difficile) Ecrire ensuite une fonction decompose(n,L) qui renvoie sous forme d’une listede listes toutes les decompositions de l’entier n a l’aide des elements de la liste L.

Par exemple :

>>>decompose(5,[1,2,5,10])

[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]]

1

Probleme : suites de Farey

Introduction : Pour tout n ∈ N∗, la suite de Farey d’ordre n, notee Fn, est la suite croissantedes fractions irreductibles a

bavec 0 ≤ a ≤ b ≤ n dans N, qui sont donc dans l’intervalle [0,1].

Par exemple F1 = [ 01, 11] et F5 = [ 0

1, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11].

Le but de ce petit probleme est d’etudier plusieurs methodes de construction des suites deFarey.

Convention : Une ecriture fractionnaire a/b sera codee par une liste [a,b].

0) Quelques outils pour la suite :

a) Creer une fonction chaine qui prend en argument une liste [a,b] et renvoie la chaıne decaractere "a/b".

b) En deduire une fonction chaineListe qui recoit une liste de rationnels (toujours ecritschacun sous la forme [a,b]), ne renvoie rien mais affiche la chaıne de caracteres formee deces rationnels ecrits sous la forme "a/b", separes par des virgules.

c) Ecrire une fonction recursive pgcd qui recoit deux entiers a et b et renvoie le pgcd de a etb.

d) En deduire une fonction simplifieListe qui recoit une liste L de couples [a,b] codant desrationnels et qui renvoie une autre liste M obtenue a partir de L en enlevant les couples telsque pgcd(a,b)≠ 1.

e) Creer une fonction elimine qui recoit une liste L de rationnels irreductibles et un entierpositif n et renvoie une liste M obtenue a partir de L en enlevant les rationnels dont ledenominateur est strictement superieur a n.

1) Tri par insertionEcrire une fonction Tri qui recoit une liste L et renvoie une liste triee deduite de L par la

methode de tri par insertion.

2) Une methode brutale pour obtenir la suite de Farey

a) Ecrire une fonction listebrute qui recoit un entier n et renvoie la liste de tous les couples[i,j] avec 0 ≤ i < j ≤ n a laquelle on rajoute [1,1].

b) A l’aide de fonctions precedentes (ou de modifications de ces fonctions) deduire de la fonctionlistebrute une fonction Fareybrut(n) qui renvoie la suite de Farey Fn sous la forme d’uneliste ordonnee de couples.

3) Un peu de mathematique pour trouver un meilleur algorithme !Dans la methode precedente, on a du utiliser un algorithme de tri. On va voir qu’on peut s’en

passer.Dans la suite, on va utiliser les deux proprietes suivantes des suites de Farey :

Prop. 3.1 Si a1/b1 et a2/b2 sont deux termes consecutifs de Fn alors :

a2b1 − a1b2 = 1.

Prop. 3.2 Si a1/b1, a2/b2 et a3/b3 sont trois termes consecutifs de Fn, alors :

a2b2

=a1 + a3b1 + b3

.

Question de maths (plutot facile !) : Montrer que la propriete 3.1 entraıne la propriete 3.2.

On admet provisoirement la propriete 3.1, cf partie 6)

4) Un algorithme plus efficaceA l’aide de la propriete 3.2, on peut construire F2 a partir de F1 = [ 0

1, 11] : il suffit de rajouter

0 + 1

1 + 1=

1

2au milieu (cette fraction est appelee mediante des deux ecritures precedentes).

2

a) Obtenir ainsi, a la main, sur votre copie, les suites F2,F3,F4,F5. Bien noter ce qu’il fautfaire en plus, a part le calcul des fractions mediantes, pour obtenir vraiment F4 et F5

b) Ecrire une fonction ajouteMediante qui recoit une liste L dont les entrees sont des couplesde la forme [a,b] et modifie cette liste L pour ajouter entre chaque entrees [a,b] et [a’,b’]successives la mediante [a+a’,b+b’].

c) Deduire de ce qui precede une fonction Farey qui recoit un entier n et renvoie la liste Fn

toujours sous la forme d’une liste de couples.

Remarque : on admet ici (voir le § 6) pour une preuve) que si (a, b) et (a′, b′) sont deuxtermes successifs d’une suite Fn alors a + a′ et b + b′ sont encore premiers entre eux.

5) Un petit dessin pour finir

Avec les algorithme precedent, on construit pour chaquea

bdans Fn, le cercle de Ford de centre

(a

b,

1

2b2) de rayon

1

2b2. On obtient pour n = 10 :

On donne le script suivant qui definit une fonction cercle permettant de tracer un cercle avecpylab :

import pylab as pl

pl.clf()

F=pl.gca()# get current axis

def cercle(x,y,r):

"""cree un cercle de centre (x,y) et de rayon r"""

cir=pl.Circle([x,y],radius=r,fill=False)

F.add_patch(cir) # ajout du cercle

# a la figure F var. globale.

cercle(0,0,1) # creation d’un cercle de centre (0,0) et de rayon 1

pl.axis(’scaled’) # pour que la figure soit centree sur notre cercle...

pl.show() # affichage de la figure

Travail a faire : Ecrire un script permettant de tracer les cercles de Ford associes a une suitede Farey Fn.

3

Appendice au probleme : questions de maths (points bonus, a rediger sur une copieseparee) ou a la maison

6) Un peu de geometrie des nombres :

Definition 6.1. On se place dans le plan R2 : dans ce plan on appelle reseau les sous ensembles dela forme R = Zu+Zv ou u = (x1, y1) et v = (x2, y2) sont deux vecteurs du plan fixes. Autrement ditun vecteur w est dans R si, et seulement si, il existe deux entiers k et l dans Z tels que w = ku+ lv.Par exemple sur le dessin ci-dessous w = u + 3v.

Definition 6.2. On note e1 = (1,0) et e2 = (0,1) les deux vecteurs de la base canonique de R2. Onappelle reseau fondamental le reseau Λ = Ze1 +Ze2 = Z2 ⊂ R2.

a) On considere une transformation lineaire f ∶ Λ → Λ, (x, y) ∈ Z2 ↦ (ax + by, cx + dy) avec

(a, b, c, d) ∈ Z2 autrement dit de matrice A = (a bc d

) ∈M2(Z).

Demontrer que f(Λ) = Λ si, et seulement si, le determinant det(f) = det(A) est egal a ±1.

b) En deduire que pour deux vecteurs u et v de Z2 le reseau Zu + Zv engendre par u et v estegal au reseau fondamental Z2 si et seulement si ∣det(u, v)∣ = 1, ce qui revient a dire quel’aire du parallelogramme de cote u et v vaut 1.

N.B. Ce parallelogramme est appele maille du reseau en cristallographie.

Definition 6.3. Un point P ∈ Z2 est dit visible depuis l’origine s’il n’y a aucun point du reseauΛ = Z2 dans l’intervalle ]O,P [, ou O = (0,0).

Exemple : (1,1) est visible depuis O, mais (2,2) ne l’est pas puisque justement (1,1) le cache.

Remarque : Il est facile de voir que, de maniere generale, un point P = (x, y) ∈ Z2 est visibledepuis l’origine si, et seulement si, pgcd(x, y) = 1.

c) Soient P et Q deux points de Z2 visibles depuis l’origine. Soit ∆ = ∣det(Ð→OP,

Ð→OQ)∣ l’aire du

parallelogramme Π de cote OP et OQ. Montrer qu’il n’y aucun point de Z2 a l’interieur duparallelogramme Π si, et seulement si, ∆ = 1.

4

d) Application a la prop. 3.1. Les fractions [a,b] avec 0 ≤ a ≤ b ≤ n et pgcd(a, b) = 1,correspondent aux points (a, b) visibles depuis l’origine a l’interieur ou au bord du triangledelimite par les droites d’equations x = 0, y = x et y = n.

Si on fait tourner une droite passant par l’origine, a partir du bord d’equation y = x, dansle sens inverse trigonometrique, cette droite va rencontrer successivement tous les pointsvisibles.

En deduire la propriete 3.1. : si [a1, b1] et [a2, b2] representent deux fractions de Fareyconsecutives alors :

a2b1 − a1b2 = 1.

e) En deduire aussi que si [a1, b1] et [a2, b2] representent deux fractions de Farey consecutivesdans F alors en posant a = a1 + a2 et b = b1 + b2, on a encore pgcd(a, b) = 1.

5