Briques

 

Calcul "à la main" versus programme Python.

Position du problème:

On dispose de deux types de briques qui ne différent que par la longueur et la couleur.

On souhaite constituer avec elles une rangée (de briques) de longueur donnée.

On s'intéresse au nombre de réalisations possibles, étant entendu que deux réalisations différent par la répartition des blocs de couleurs.

Précisons:

Briques de type 1 : longueur m, couleur a

Briques de type 2 : longueur n, couleur b

Rangée à construire de longueur L

La question va être de déterminer tous les couples d'entiers (k et h) tels que :

                                   mk+nh = L                (e)

puis, pour chacun de ces couples (h,k), de déterminer les rangs possibles, de 1 à k+h, où on placera les k briques de couleur a.

Sur ce dernier décompte, on connaît la réponse: il y a C(k+h;k) possibilités de répartition des k briques de couleur a, où C(k+h;k) est le  nombre de combinaisons k à k de k+h objets et se calcule par le quotient de factorielles : (k+h)!/k!h! avec, pour n un entier quelconque,  n! comme produit de 1 à n des entiers successifs (par exemple : 5!=1x2 x3 x4 x5 = 120).

Pour le premier décompte, on tombe sur une question d'arithmétique classique, l'équation diophantienne aux inconnues entières (x,y) (de Diophante (d'Alexandrie, deuxième ou troisième siècle avant JC)) de type : ax+by = c, où a,b et c sont des entiers donnés.

Il est assez évident que si le pgcd (plus grand commun diviseur) de a et b ne divise pas c, l'équation sera sans solution.

Si le pgcd de a et b divise c, en divisant les deux membres de l'équation par ce pgcd, le problème est ramené au cas où a et b sont des entiers premiers entre eux.

Pour ne pas trop alourdir le propos, on va continuer sur un exemple, sachant que la méthode est de généralisation immédiate. Ainsi, avec m=25, et n = 30. L'équation (e) devient :

25k + 30h = L

Le pgcd de 25 et 30 est 5.

Soit : 5(5k + 6h) = L

Si L n'est pas un multiple de 5, le problème est sans solution.

Sinon, par exemple avec L = 420, on obtient, à résoudre : 5k + 6h = 84

5 et 6 sont premiers entre eux.

Un résultat général d'arithmétique ( l'algorithme d'Euclide) permet de déterminer, pour tout couple (m,n) de nombres premiers entre eux, un couple (u,v) d'entiers relatifs (c-à-d positifs ou négatifs) tels que : um+vn = 1.

Ici, le résultat est évident :

6 – 5 = 1 soit 5x(-1) + 6 x 1 = 1

On en déduit trivialement :    5 x (-84) + 6 x 84 = 84

On cherche :                           5 x k + 6 x h = 84

Par soustraction, on obtient : 5 x (k+84) + 6 x (h-84) = 0

Soit :                                      5 x (k+84) = 6 x (84-h)

On sait par ailleurs (c'est un théorème arithmétique de Gauss (1777-1855)) que:

Si c divise a x b  en étant premier avec a, alors, c divise b.

6 est premier avec 5. Donc 6, qui divise 6 x (84-h), divise aussi  5 x (k+84), et, par Gauss, divise (k+84).

On peut donc écrire, où u est un entier : k+84 = 6u

Soit: k = 6u-84

On en déduit immédiatement : 5 x 6u = 6 x (84-h)

Soit: h = 84 – 5u

On ne s'intéresse évidemment qu'aux solutions positives de (e).

Ce qui impose :  u ≥ 84/6 soit u ≥ 14   et u ≤ 84/5 soit u ≤ 16

Ce qui nous fournit pour u les possibilités : {14,15,16}

Et pour (k,h) les couples possibles : (0,14), (6,9) et (12, 4)

Cas (0,14) : 14 briques de 30. Pas de jeu sur les couleurs. 1 seule possibilité.

Cas (6,9) : 6 briques de 25, 9 briques de 30.

Mais il reste à choisir les 6 positions des briques de 25 parmi les 15 positions possibles: C(15;6) = 5005

Cas (12,4) : 12 briques de 25 et 4 briques de 30.

Mais il reste à choisir les 4 positions des briques de 30 parmi les 16 positions possibles : C(16;4) = 1820

1+5005+1820 = 6826

Il y a donc 6826 façons possibles d'aligner sur 4,2 mètres des briques de 25 cm et des briques de 30 cm.

En maintenant à 4,2 m la longueur de la rangée de briques, on peut, rapidement refaire les calculs pour différentes situations

A - Cas (m,n) = (30,32) :

L'équation (e) devient :          30k + 32h = 420

Le pgcd de 30 et 32 est 2.

Soit : 2(15k + 16h) = 420

On obtient, à résoudre : 15k + 16h = 210

15 et 16 sont premiers entre eux.

Ici encore,  on n'exige rien de l'algorithme d'Euclide:

16 – 15 = 1 soit 15x(-1) + 16 x 1 = 1

On en déduit trivialement :    15 x (-210) + 16 x 210 = 210

On cherche :                           15 x k + 16 x h = 210

Par soustraction, on obtient : 15 x (k+210) + 16 x (h-210) = 0

Soit :                                      15 x (k+210) = 16 x (210-h)

16 est premier avec 15. Donc 16, qui divise 16 x (210-h), divise aussi  15 x (k+210), et, par Gauss, divise (k+210).

On peut donc écrire, où u est un entier : k+210 = 16u

Soit: k = 16u-210

On en déduit immédiatement : 15 x 16u = 16 x (210-h)

Soit: h = 210 – 15u

On ne s'intéresse évidemment qu'aux solutions positives de (e).

Ce qui impose :  u ≥ 210/16 soit u ≥ 14   et u ≤ 210/15 soit u ≤ 14

Ce qui nous fournit pour u la seule  possibilité : {14}

Et pour (k,h) l'unique couple possible : (0,14)

Soit : 14 briques de 30. Pas de jeu sur les couleurs.

1 seule rangée possible de longueur 4,2 m avec 14 briques de 30

B – Cas (m,n) = (14,35)

L'équation (e) devient :          14k + 35h = 420

Le pgcd de 14 et 35 est 7.

Soit : 7(2k + 5h) = 420

On obtient, à résoudre : 2k + 5h = 60

2 et 5 sont premiers entre eux.

Ici encore,  on n'exige rien de l'algorithme d'Euclide:

5 – 2x2 = 1 soit 2x(-2) + 5 x 1 = 1

On en déduit trivialement :    2 x (-120) + 5 x 60 = 60

On cherche :                           2 x k + 5 x h = 60

Par soustraction, on obtient : 2 x (k+120) + 5 x (h-60) = 0

Soit :                                      2 x (k+120) = 5 x (60-h)

5 est premier avec 2. Donc 5, qui divise 5 x (60-h), divise aussi  2 x (k+120), et, par Gauss, divise (k+120).

On peut donc écrire, où u est un entier : k+120 = 5u

Soit: k = 5u-120

On en déduit immédiatement : 2x 5u = 5 x (60-h)

Soit: h = 60 – 2u

On ne s'intéresse évidemment qu'aux solutions positives de (e).

Ce qui impose :  u ≥ 120/5 soit u ≥ 24   et u ≤ 60/2 soit u ≤ 30

Ce qui fournit pour u les possibilités {24, 25, 26, 27, 28, 29, 30}

Et pour (k,h) les couples : (0,12), (5, 10), (10, 8), (15, 6), (20, 4), (25, 2), (30, 0)

Il faut maintenant dénombrer les jeux de couleurs :

(0,12) : 1 seule possibilité. 12 briques de 35

(5,10) : C(15,5) = 3003 possibilités

(10,8) : C(18,8) = 43758 possibilités

(15,6) : C(21,6) = 54264 possibilités

(20,4) : C(24,4) = 10626 possibilités

(25,2) : C(27,2) = 351 possibilités

(30,0) : 1 seule possibilité. 30 briques de 14

Au total : 112 004 façons de procéder .

C- (m,n) = (23, 36)

L'équation (e) devient :          23k + 36h = 420

23 et 36 sont premiers entre eux.

Cette fois, au lieu de tâtonner, on utilise l'algorithme d'Euclide:

36 = 1 x 23 + 13

23 = 1 x 13 + 10

13 = 1 x 10+ 3

10 = 3 x 3 + 1

Soit en "remontant" à partir du dernier reste 1 :

1 = 10 - 3 x 3

1 = 10 – 3 x (13 – 1 x 10) = 4 x 10 - 3 x 13

1 = -3 x 13 + 4 x (23-1 x 13) = 4 x 23 - 7 x 13

1 = 4 x 23 -7 x (36 – 1 x 23) = 11 x 23 - 7 x 36

En multipliant par 420 on obtient :   4620 x 23 - 2940 x 36 = 420

On cherche :                                       23 x k + 36 x h = 420

Par soustraction, on obtient : 23 x (k-4620) + 36x (h+2940) = 0

Soit :                                      23 x (4620-k) = 36 x (h+2940)

23 est premier avec 36. Donc 23, qui divise 23 x (4620-k), divise aussi  36 x (h+2940), et, par Gauss, divise (h+2940).

On peut donc écrire, où u est un entier : h+2940 = 23u

Soit: h= 23u-2940

On en déduit immédiatement : 36x 23u = 23 x (4620-k)

Soit: k = 4620 – 36u

On ne s'intéresse évidemment qu'aux solutions positives de (e).

Ce qui impose :  u ≥ 2940/23 soit u ≥ 128   et u ≤ 4620/36 soit u ≤ 128

Il n'y a donc que la possibilité : u=128

Donc que le couple (k,h) = (12,4)

Avec C(16,4) = 1820 jeux de couleurs pour 12 briques de 23 et 4 briques de 36. 

Programmation – Langage PYTHON

On peut constater que le  travail de résolution "à la main" est malgré tout assez exigeant en termes d'attention, et mobilise quelques compétences en arithmétique élémentaire.

Il est alors intéressant (et à mon avis, assez spectaculaire en termes de performance) de confier la question , via l'écriture d'un petit programme Python (langage adopté en Classes préparatoires et poursuivi en Grandes écoles) , à l'ordinateur.

Façon de juger de la pertinence d'un micro-détour par l'intelligence artificielle.

Il suffit de mettre en œuvre le petit programme suivant:

(les lignes commençant par # ne sont que des commentaires de présentation ou d'accompagnement)

# Combien de possibilités pour le problème des briques?

print("Rangée à construire. Deux types de briques") 

# On annonce la question; print = imprimer

# Et on saisit les longueurs des deux types de briques  dans les variables m et n

m=int(input("Longueur brique de type 1: ",))

n=int(input("Longueur brique de type 2 : ",))

# On range dans les variables b (pour bas) et h (pour haut) respectivement la plus petite et la plus grande longueur par

# une instruction if … else …, c-à-d : si … alors…

if m<n:

    b,h = m,n

else:

    b,h=n,m

L=int(input("Longueur de la rangée à construire: ",))

# On saisit la longueur de la rangée

# On va définir la fonction-réponse, appelée "briques(m,n,L)".

def briques(m,n,L):

    if L<b:

        return 0              # si la rangée est plus courte que la plus petite brique … pas de solution

    elif L==b or L==h:

        return 1              # si la rangée a la longueur d'un des deux types de briques …

    else:

        return briques(m,n,L-b)+briques(m,n,L-h)

# On utilise la récursivité (le renvoi de la fonction à elle-même).

# La rangée se termine nécessairement par une brique de longueur m ou n

# L'ensemble des possibilités cherchées est donc obtenu sur deux rangées de longueurs

# respectives (L-m) et (L-n), avec les mêmes types de briques … à partir desquelles on

# recommence

# l'algorithme boucle ainsi de façon descendante sur lui même jusqu'à déboucher sur un des

# cas triviaux L<b, L =m ou L=n , comme un arbre dont on dessinerait les racines

#  qui se divisent progressivement. Il n'y a plus qu'à compter les "1" terminaux,

# et à afficher – ci-après – le résultat.

print ("Il y a ", briques(m,n,L), " façons de procéder.")

 

Je recopie sans les commentaires pour qu'on juge de la brièveté de la partie opérationnelle de l'algorithme:

print("Rangée à construire. Deux types de briques") 

m=int(input("Longueur brique de type 1: ",))

n=int(input("Longueur brique de type 2 : ",))

if m<n:

    b,h = m,n

else:

    b,h=n,m

L=int(input("Longueur de la rangée à construire: ",))

def briques(m,n,L):

    if L<b:

        return 0             

    elif L==b or L==h:

        return 1             

    else:

        return briques(m,n,L-b)+briques(m,n,L-h)

print ("Il y a ", briques(m,n,L), " façons de procéder.")

 

On contrôle immédiatement les résultats obtenus "à la main".

Et on peut s'amuser à en collectionner à moindres frais d'autres :

Briques(12,17, 256) : 43758

Briques (21, 29, 395): 3003

Briques (17, 31, 315): impossible

Briques (17, 31, 387): 19448

Briques (12,17, 100) : impossible

Briques (12, 17, 200): 1365

MAIS :

Paradoxalement (?), certaines configurations peuvent mettre en difficulté l'ordinateur …

Ainsi : Briques (12, 17, 500)  fournit "à la main" 4 060 020 775 possibilités, avec trois types de répartitions :

2 briques de 12 et 28 briques de 17              C(30,2) = 435

19 briques de 12 et 16 briques de 17            C(35,16) = 4 059 928 950

36 briques de 12 et 4 briques de 17              C(40,4) = 91390

                                                                 Total : 4 060 020 775

On a là un ordre de grandeur dans lequel la récursivité du programme perd pied …