La simplification du cancre

UPO Jean-Manuel Mény

La simplification du cancre

Un cancre doit simplifier la fraction $\frac{16}{64}$. Il "raisonne" ainsi: $\frac{1{\not{6}}}{{\not{6}}4} = \frac{1}{4}$.

  • Vérifier que le résultat est correct dans ce cas.
  • Donner une autre fraction pour laquelle cette façon de procèder ne donnera pas un résultat correct.
  • Montrer qu'il existe une infinité de couples d'entiers $(a;b)$ pour lesquels une simplification de ce type fonctionne.

Résolution

  • $\frac{16}{64} = \frac{16\times 1}{16 \times 4} = \frac{1}{4}$.
  • Par exemple $\frac{25}{24}$ n'est pas égale à $\frac{5}{4}$.
  • Si le chiffre des unités de $a$ ($a\neq 0$) est 0 ainsi que le chiffre des unités de $b$, barrer ce chiffre 0 donne un résultat correct. Il y a donc une infinité de couples $(a;b)$ pour lesquels la simplification du cancre est correcte.

Problème à résoudre

Un prof de maths écrit un exercice de contrôle sur le thème des fractions. Pour cela, il choisit un entier à deux chiffres au hasard (cet entier sera le numérateur) puis il choisit le dénominateur au hasard parmi les entiers à deux chiffres distincts du numérateur.

La consigne est de donner la forme irréductible de la fraction ainsi constituée. L'enseignant donne la consigne de ne pas écrire les détails.

La note sera 1 pour une réponse correcte, 0 pour une réponse incorrecte.

Quelle est la probabilité que le cancre gagne un point?

On résoudra la question à l'aide d'un script python.

Remarque 1

Les entiers $a$ et $b$ à manipuler n'ayant que deux chiffres et étant distincts, ils ont au plus un chiffre commun.

Si l'on cherche à prolonger la question à des entiers de plus de deux chiffres, le problème se complique. Le cancre pourra en effet chercher à simplifier une fraction telle que $\frac{919}{69}$ de deux façons différentes (obtenant soit $\frac{19}{6}$, soit $\frac{91}{6}$).

Remarque 2

Le cancre verra sa réponse comptée comme juste dans les cas suivants:

  • $\frac{a}{b}$ est une fraction sur laquelle une simplification cancre s'applique et pour laquelle le résultat obtenu par cette simplification cancre est correct et irréductible.
  • $\frac{a}{b}$ est une fraction déjà irréductible et aucune simplification cancre n'est applicable.

Fraction cancre-simplifiable

Ecrire une fonction python cancreSimplifiable(a,b)prenant en paramètres les entiers naturels $a$ et $b$ ($b\neq 0$) et renvoyant True si une simplification-cancre peut être opérée et False sinon. On se limite ici à une fonction traitant les entiers a et b à deux chiffres.

In [101]:
def cancreSimplifiable(a,b):
    """
    a et b sont deux entiers naturels (b non nul).
    a et b sont compris entre 10 et 99 et distincts.
    La fonction renvoie True si a et b ont un chiffre commun
    (dans leur écriture en base 10).
    """
    assert(10 <= a <= 99)
    assert(10 <= b <= 99)
    a = (a%10, a//10)
    b = (b%10, b//10)
    return a[0]==b[0] or a[1]==b[1] or a[0]==b[1] or a[1]==b[0]
In [102]:
cancreSimplifiable(22, 32)
Out[102]:
True
In [103]:
cancreSimplifiable(21,34)
Out[103]:
False

Nombre de fractions irréductibles et non cancre-simplifiables.

In [104]:
from math import gcd
def nbIrreductibleNonCancreSimplifiable():
    """
    La fonction renvoie le nombre de fractions a/b telles que:
    - a est différent de b
    - a et b sont compris entre 10 et 99
    - aucune simplication du cancre n'est applicable à la fraction a/b
    - la fraction a/b est irréductible
    """
    compteur = 0
    for a in range(10,100):
        for b in range(10,100):
            if gcd(a,b)==1 and not(cancreSimplifiable(a,b)):
                compteur += 1
    return compteur
In [105]:
nbIrreductibleNonCancreSimplifiable()
Out[105]:
3284

Fraction cancre-simplifiable à résultat correct et irréductible

In [106]:
def  cancreSimplifiableCorrectIrreductible(a,b):
    """
    a et b sont deux entiers naturels distincts, compris entre 10 et 99.
    La fonction renvoie True si:
    - la fraction a/b peut subir une simplification du cancre.
    - le résultat de cette simplification est correct et irréductible
    La fonction renvoie False sinon.
    """
    assert(10 <= a <= 99)
    assert(10<= b <= 99)
    assert(a != b)
    A = (a%10, a//10)
    B = (b%10, b//10)
    if A[0]==B[0] and a*B[1]==b*A[1] and gcd(A[1], B[1])==1: return True
    if A[1]==B[1] and a*B[0]==b*A[0] and gcd(A[0], B[0])==1: return True
    if A[0]==B[1] and a*B[0]==b*A[1] and gcd(A[1], B[0])==1: return True
    if A[1]==B[0] and a*B[1]==b*A[0] and gcd(A[0], B[1])==1: return True
    return False
In [107]:
cancreSimplifiableCorrectIrreductible(16,64)
Out[107]:
True
In [108]:
cancreSimplifiableCorrectIrreductible(64,16)
Out[108]:
True
In [109]:
49/98 == 4/8
Out[109]:
True
In [110]:
from math import gcd
gcd(49,98)
Out[110]:
49
In [111]:
cancreSimplifiableCorrectIrreductible(49,98)
Out[111]:
False

Nombre de fractions cancre-simplifiables à résultat correct et irréductible

In [112]:
def nbCancreSimplifiableCorrectIrreductible():
    """
    La fonction renvoie le nombre de fractions a/b telles que:
    - a est différent de b
    - a et b sont compris entre 10 et 99.
    - la fraction a/b peut subir une simpliciation du cancre
    - cette simplification-cancre mène à un résultat correct et irréductible
    """
    compteur = 0
    for a in range(10,100):
        for b in [k for k in range(10,100) if k!=a]:
            if cancreSimplifiableCorrectIrreductible(a,b):
                compteur += 1
    return compteur
In [113]:
nbCancreSimplifiableCorrectIrreductible()
Out[113]:
60

Nombre de couples (a;b)

Le nombre de couples $(a;b)$ avec $10 \leqslant a \leqslant 99$, $10 \leqslant b \leqslant 99$, $a\neq b$ est égal à $(99-10+1)\times(99-10+1) - 90 = 8010$.

In [114]:
def nbCouples():
    """
    La fonction renvoie le nombre de couples (a,b) tels que
    - a est différent de b
    - a et b sont compris entre 10 et 99
    """
    compteur = 0
    for a in range(10,100):
        for b in [k for k in range(10,100) if k!=a]:
            compteur += 1
    return compteur
In [115]:
nbCouples()
Out[115]:
8010

Probabilité

La probabilité que l'enseignant choisisse une fraction permettant au cancre de gagner un point est donc égale à $\frac{60+3284}{8010}$.

In [116]:
(60+3284)/8010
Out[116]:
0.417478152309613

Une liste

Ecrire une fonction python calculant la liste des couples $(a;b)$ tels que $a\neq b$, $10 \leqslant a \leqslant 99$, $10\leqslant b \leqslant 99$ et la fraction $\frac{a}{b}$ peut subir une simplification du cancre donnant un résultat correct (non nécessairement irréductible).

On éliminera d'office tous les cas $\frac{20}{60}$, $\frac{80}{30}$, ... (rapport de deux multiples de 10) pour ne pas surcharger l'affichage.

In [117]:
def  cancreSimplifiableCorrect(a,b):
    """
    a et b sont deux entiers naturels distincts, compris entre 10 et 99.
    La fonction renvoie True si:
    - la fraction a/b peut subir une simplification du cancre.
    - le résultat de cette simplification est correct.
    La fonction renvoie False sinon.
    """
    assert(10 <= a <= 99)
    assert(10<= b <= 99)
    assert(a != b)
    A = (a%10, a//10)
    B = (b%10, b//10)
    if A[0]==B[0] and a*B[1]==b*A[1]: return True
    if A[1]==B[1] and a*B[0]==b*A[0]: return True
    if A[0]==B[1] and a*B[0]==b*A[1]: return True
    if A[1]==B[0] and a*B[1]==b*A[0]: return True
    return False

def listeCancreSimplifiableCorrect():
    """
    Renvoie la liste des couples (a,b) avec:
    - a distinct de b
    - a et b entre 0 et 99
    - une simplification cancre est possible et donne un résultat correct
    - a et b ne sont pas tous deux multiples de 10
    """
    liste = []
    for a in range(10,100):
        for b in [k for k in range(10,100) if k!=a]:
            if not(a%10==0) or not(b%10==0):
                if cancreSimplifiableCorrect(a,b):
                    liste.append((a,b))
    return liste
In [118]:
listeCancreSimplifiableCorrect()
Out[118]:
[(16, 64),
 (19, 95),
 (26, 65),
 (49, 98),
 (64, 16),
 (65, 26),
 (95, 19),
 (98, 49)]

Fonction cancre-simplifiable pour une fraction quelconque

Objectif: réécrire la fonction cancreSimplifiable(a,b) mais pour des entiers naturels a et b non limités à deux chiffres.

Chiffre de poids p

Le chiffre des unités est le chiffre de poids 0, le chiffre des dizaines est le chiffre de poids 1, le chiffre des centaines est le chiffre de poids 2, le chiffre des milliers est le chiffre de poids 3, etc...

Ecrire une fonction python chiffre(entier, poids) prenant en paramètres deux entiers naturels et renvoyant le chiffre de poids "poids" de l'entier "entier".

In [119]:
def chiffre(entier, poids):
    """
    entier est un entier naturel.
    poids est un entier naturel.
    La fonction renvoie le chiffre de poids "poids" de l'entier "entier".
    
    Exemples:
    chiffre(125, 0) = 5
    chiffre(125, 1) = 2
    chiffre(125, 2) = 1
    chiffre(125, n) = 0  où n > 2
    """
    A = entier // (10**poids)
    return A % 10
In [120]:
chiffre(125, 0)
Out[120]:
5
In [121]:
chiffre(125, 2)
Out[121]:
1

Nombre de chiffres

Ecrire une fonction python nbChiffres(n) prenant un entier naturel en entrée et renvoyant le nombre de chiffres de cet entier (dans son écriture en base 10).

In [122]:
def nbChiffres(n):
    """
    n est un entier naturel.
    La fonction renvoie le nombre de chiffres de l'écriture décimale de n.
    """
    if n < 10: return 1 # cas particulier pour n = 0 notamment 
    nb = 0
    while n != 0:
        nb += 1
        n = n//10
    return nb
In [123]:
nbChiffres(124)
Out[123]:
3
In [124]:
nbChiffres(0)
Out[124]:
1

Cancre simplifiable

Ecrire une fonction python cancreSimplifiableG(a,b) qui renvoie True si on peut appliquer une simplification du cancre à la fraction $\frac{a}{b}$ (c'est à dire si les écritures décimales de a et b présentent au moins un chiffre commun).

In [125]:
def cancreSimplifiableG(a,b):
    """
    a et b sont deux entiers naturels.
    La fonction renvoie True si les écritures décimales de a et b
    présentent au moins un chiffre commun.
    """
    # nombre de chiffres des deux entiers:
    la, lb = nbChiffres(a), nbChiffres(b)
    # pour chaque poids possible pour a
    #    pour chaque poids possible pour b
    for pa in range(la):
        for pb in range(lb):
            if chiffre(a,pa)==chiffre(b,pb): return True
    return False
In [126]:
cancreSimplifiableG(16,64)
Out[126]:
True
In [127]:
cancreSimplifiableG(919,92)
Out[127]:
True
In [128]:
cancreSimplifiableG(987,6543)
Out[128]:
False

Barrer un chiffre

On voudrait "barrer un chiffre" de l'écriture d'un entier pour obtenir l'entier écrit sans ce chiffre.

Exemples:

  • $12{\not{3}} = 12$ (on barre le 3 de 123, on obtient 12)
  • $1{\not{2}}3 = 13$ (on barre le 2 de 123, on obtient 13)
  • ${\not{1}}23 = 23$ (on barre le 1 de 123, on obtient 23)

Définir une fonction python barrerChiffre(entier, poids) qui renverra l'entier obtenu en barrant le chiffre de poids "poids" de l'entier "entier".

In [129]:
def barrerChiffre(entier, poids):
    """
    entier est un entier naturel.
    poids est un entier naturel.
    La fonction renvoie l'entier dont l'écriture est 
    celle de "entier" sans son chiffre de poids "poids".
    
    Exemples:
    chiffre(125, 0) = 12
    chiffre(125, 1) = 15
    chiffre(125, 2) = 25
    chiffre(125, n) = 125  où n > 2
    """
    queue = entier % (10**poids)
    tete = entier // (10**(poids+1))
    return tete * 10**poids + queue
In [130]:
barrerChiffre(125, 0)
Out[130]:
12
In [131]:
barrerChiffre(125, 2)
Out[131]:
25

Simplification correcte

Ecrire une fonction python cancreSimplifiableCorrectG(a,b) prenant en paramètres deux entiers naturels a et b et renvoyant True lorsqu'une simplification du cancre menant à un résultat correct est possible (et renvoyant False sinon).

In [132]:
def cancreSimplifiableCorrectG(a,b):
    la = nbChiffres(a)
    lb = nbChiffres(b)
    for pa in range(la):
        for pb in range(lb):
            if chiffre(a,pa)==chiffre(b,pb) and a*barrerChiffre(b,pb)==b*barrerChiffre(a,pa):
                return True
    return False
In [133]:
cancreSimplifiableCorrectG(64,16)
Out[133]:
True

La fonction précédente a le défaut de ne pas donner le rang des chiffres simplifiables menant à un résultat correct. Lorsque plusieurs chiffres sont communs, cela est gênant. Ecrire une fonction corrigeant ce problème.

In [134]:
def cancreSimplifiableCorrectAvecPoids(a,b):
    """
    Renvoie le premier couple de poids trouvé correspondant
    à une simplification du cancre "valide" sur la fraction a/b.
    """
    la = nbChiffres(a)
    lb = nbChiffres(b)
    for pa in range(la):
        for pb in range(lb):
            if chiffre(a,pa)==chiffre(b,pb) and a*barrerChiffre(b,pb)==b*barrerChiffre(a,pa):
                return (pa,pb)
    return False
In [135]:
cancreSimplifiableCorrectAvecPoids(16,64)
Out[135]:
(0, 1)

Et si plusieurs simplifications du cancre correctes sont possibles?

In [136]:
def listeCancreSimplifiableCorrectAvecPoids(a,b):
    """
    Renvoie la liste des couples de poids correspondant
    à une simplification du cancre "valide" sur la fraction a/b.
    """
    liste = []
    la = nbChiffres(a)
    lb = nbChiffres(b)
    for pa in range(la):
        for pb in range(lb):
            if chiffre(a,pa)==chiffre(b,pb) and a*barrerChiffre(b,pb)==b*barrerChiffre(a,pa):
                liste.append((a,b, pa, pb))
            
    return liste
In [137]:
listeCancreSimplifiableCorrectAvecPoids(16,64)
Out[137]:
[(16, 64, 0, 1)]
In [138]:
listeCancreSimplifiableCorrectAvecPoids(177,9735)
Out[138]:
[(177, 9735, 0, 2), (177, 9735, 1, 2)]

Nombre multisimplifiable sans chiffres consécutifs identiques

Le cas de $\frac{177}{9735}$ qui se simplifie de deux façons est un peu "décevant": la suppression de l'un ou l'autre des 7 du numérateur est en fait la même.

Ecrire un script python cherchant des exemples où plusieurs simplications cancres valides sont présentes mais sans le cas de chiffres consécutifs égaux.

Nombre sans chiffres consécutifs identiques

In [140]:
def consecutifsId(n):
    """
    n est un entier naturel.
    La fonction renvoie True si l'écriture décimale de n 
    présente au moins deux chiffres consécutifs identiques.
    """
    if n < 10: return False
    chiffre1 = n%10
    while n != 0:
        n = n//10
        chiffre2 = n%10
        if chiffre2 == chiffre1: return True
        chiffre1 = chiffre2
    return False
In [141]:
consecutifsId(11)
Out[141]:
True
In [142]:
consecutifsId(212)
Out[142]:
False

Fraction cancre simplifiable plusieurs fois

In [143]:
def cspfsrcc(ma, Ma, mb, Mb):
    """
    Renvoie une liste de fractions a/b telles que:
    - a et b sont différents,
    - a est compris entre ma et Ma, b est compris entre mb et Mb,
    - plusieurs simplifications du cancre sont possibles,
    - les écritures décimales de a et de b ne présentent pas de chiffres consécutifs égaux.
    - on évite également des relations trop simples entre a et b (a = 10b, a = 100b...)
    ainsi que les cas où a et b sont tous deux multiples de 10.
    """
    liste = []
    for a in range(ma, Ma+1):
        for b in range(mb, Mb+1):
            if not(consecutifsId(a)) and not(consecutifsId(b)) and a!=b and (max(a,b)//min(a,b))%10 != 0:
                if not(a%10==0 and b%10==0): 
                    listeab = listeCancreSimplifiableCorrectAvecPoids(a,b)
                    if len(listeab) > 1: liste.append(listeab)
    return liste
In [144]:
cspfsrcc(10, 10000, 10, 10000)
Out[144]:
[[(349, 1396, 0, 1), (349, 1396, 2, 2)],
 [(983, 3932, 0, 1), (983, 3932, 2, 2)],
 [(1016, 4064, 0, 1), (1016, 4064, 2, 2)],
 [(1019, 5095, 0, 1), (1019, 5095, 2, 2)],
 [(1049, 2098, 0, 1), (1049, 2098, 2, 2)],
 [(1306, 3265, 0, 1), (1306, 3265, 2, 3)],
 [(1349, 5396, 0, 1), (1349, 5396, 2, 2)],
 [(1386, 3465, 0, 1), (1386, 3465, 2, 3)],
 [(1396, 349, 1, 0), (1396, 349, 2, 2)],
 [(1396, 3490, 1, 1), (1396, 3490, 2, 3)],
 [(1398, 3495, 1, 1), (1398, 3495, 2, 3)],
 [(1601, 6404, 1, 1), (1601, 6404, 2, 3)],
 [(1602, 6408, 1, 1), (1602, 6408, 2, 3)],
 [(1616, 6464, 0, 1), (1616, 6464, 2, 3)],
 [(1634, 6536, 1, 1), (1634, 6536, 2, 3)],
 [(1649, 6596, 0, 1), (1649, 6596, 2, 3)],
 [(1683, 6732, 0, 1), (1683, 6732, 2, 3)],
 [(1698, 6792, 1, 1), (1698, 6792, 2, 3)],
 [(1901, 9505, 1, 1), (1901, 9505, 2, 3)],
 [(1919, 9595, 0, 1), (1919, 9595, 2, 3)],
 [(1939, 9695, 0, 1), (1939, 9695, 2, 3)],
 [(1959, 9795, 0, 1), (1959, 9795, 2, 3)],
 [(1979, 9895, 0, 1), (1979, 9895, 2, 3)],
 [(1983, 7932, 0, 1), (1983, 7932, 2, 2)],
 [(1986, 4965, 0, 1), (1986, 4965, 2, 2)],
 [(2016, 8064, 0, 1), (2016, 8064, 2, 2)],
 [(2026, 5065, 0, 1), (2026, 5065, 2, 2)],
 [(2049, 4098, 0, 1), (2049, 4098, 2, 2)],
 [(2098, 1049, 1, 0), (2098, 1049, 2, 2)],
 [(2349, 9396, 0, 1), (2349, 9396, 2, 2)],
 [(2602, 6505, 1, 1), (2602, 6505, 2, 3)],
 [(2626, 6565, 0, 1), (2626, 6565, 2, 3)],
 [(3049, 6098, 0, 1), (3049, 6098, 2, 2)],
 [(3265, 1306, 1, 0), (3265, 1306, 3, 2)],
 [(3465, 1386, 1, 0), (3465, 1386, 3, 2)],
 [(3490, 1396, 1, 1), (3490, 1396, 3, 2)],
 [(3495, 1398, 1, 1), (3495, 1398, 3, 2)],
 [(3906, 9765, 0, 1), (3906, 9765, 2, 3)],
 [(3932, 983, 1, 0), (3932, 983, 2, 2)],
 [(3932, 9830, 1, 1), (3932, 9830, 2, 3)],
 [(3934, 9835, 1, 1), (3934, 9835, 2, 3)],
 [(3946, 9865, 0, 1), (3946, 9865, 2, 3)],
 [(4049, 8098, 0, 1), (4049, 8098, 2, 2)],
 [(4064, 1016, 1, 0), (4064, 1016, 2, 2)],
 [(4098, 2049, 1, 0), (4098, 2049, 2, 2)],
 [(4901, 9802, 1, 1), (4901, 9802, 2, 3)],
 [(4902, 9804, 1, 1), (4902, 9804, 2, 3)],
 [(4903, 9806, 1, 1), (4903, 9806, 2, 3)],
 [(4904, 9808, 1, 1), (4904, 9808, 2, 3)],
 [(4949, 9898, 0, 1), (4949, 9898, 2, 3)],
 [(4965, 1986, 1, 0), (4965, 1986, 2, 2)],
 [(5065, 2026, 1, 0), (5065, 2026, 2, 2)],
 [(5095, 1019, 1, 0), (5095, 1019, 2, 2)],
 [(5396, 1349, 1, 0), (5396, 1349, 2, 2)],
 [(6098, 3049, 1, 0), (6098, 3049, 2, 2)],
 [(6404, 1601, 1, 1), (6404, 1601, 3, 2)],
 [(6408, 1602, 1, 1), (6408, 1602, 3, 2)],
 [(6464, 1616, 1, 0), (6464, 1616, 3, 2)],
 [(6505, 2602, 1, 1), (6505, 2602, 3, 2)],
 [(6536, 1634, 1, 1), (6536, 1634, 3, 2)],
 [(6565, 2626, 1, 0), (6565, 2626, 3, 2)],
 [(6596, 1649, 1, 0), (6596, 1649, 3, 2)],
 [(6732, 1683, 1, 0), (6732, 1683, 3, 2)],
 [(6792, 1698, 1, 1), (6792, 1698, 3, 2)],
 [(7932, 1983, 1, 0), (7932, 1983, 2, 2)],
 [(8064, 2016, 1, 0), (8064, 2016, 2, 2)],
 [(8098, 4049, 1, 0), (8098, 4049, 2, 2)],
 [(9396, 2349, 1, 0), (9396, 2349, 2, 2)],
 [(9505, 1901, 1, 1), (9505, 1901, 3, 2)],
 [(9595, 1919, 1, 0), (9595, 1919, 3, 2)],
 [(9695, 1939, 1, 0), (9695, 1939, 3, 2)],
 [(9765, 3906, 1, 0), (9765, 3906, 3, 2)],
 [(9795, 1959, 1, 0), (9795, 1959, 3, 2)],
 [(9802, 4901, 1, 1), (9802, 4901, 3, 2)],
 [(9804, 4902, 1, 1), (9804, 4902, 3, 2)],
 [(9806, 4903, 1, 1), (9806, 4903, 3, 2)],
 [(9808, 4904, 1, 1), (9808, 4904, 3, 2)],
 [(9830, 3932, 1, 1), (9830, 3932, 3, 2)],
 [(9835, 3934, 1, 1), (9835, 3934, 3, 2)],
 [(9865, 3946, 1, 0), (9865, 3946, 3, 2)],
 [(9895, 1979, 1, 0), (9895, 1979, 3, 2)],
 [(9898, 4949, 1, 0), (9898, 4949, 3, 2)]]

Exemple tiré de cette liste:

In [149]:
from fractions import *
Fraction(9765,3906), Fraction(765,306), Fraction(975,390), Fraction(75,30)
Out[149]:
(Fraction(5, 2), Fraction(5, 2), Fraction(5, 2), Fraction(5, 2))