Effacer par paire

  • Niveau ciblé: classe de première.
  • Points du programme abordés:
    • Suites arithmétiques: calcul de 1+2+...+n.
    • Générer une liste (en extension, par ajouts successifs ou en compréhension).
    • Manipuler des éléments d’une liste (ajouter, supprimer...) et leurs indices.
    • Parcourir une liste.
    • Itérer sur les éléments d’une liste.

Partie 1: la situation

Aurore écrit sur un tableau tous les entiers de 1 à 2019.

Puis elle en sélectionne deux au hasard (a et b), les efface et écrit à la place le nombre $\left| b - a\right|$.

Elle recommence l'opération jusqu'à n'avoir plus qu'un seul entier au tableau.

Le dernier nombre écrit au tableau est 3.

On aimerait montrer qu'Aurore s'est trompée dans ses opérations.

Partie 2

Question 1

Écrire une fonction python prenant en entrée une liste d'entiers et renvoyant en sortie la somme des éléments de la liste.

Une réponse

def somme(liste):
    s = 0
    for x in liste:
        s = s+x
    return s

Question 2

  • Utiliser cette fonction pour déterminer la somme des entiers écrits initialement au tableau.
  • Vérifier ce calcul à l'aide d'une formule appropriée.
Une réponse

On vérifie que la somme 1+2+...+2019 a pour valeur 2 039 190.

Par utilisation du programme: somme([i for i in range(1,2020)]).

Par calcul: formule usuelle de la somme de termes en progression arithmétique.

Partie 3

Question 1

Écrire une fonction etape python prenant en entrée une liste d'entiers.

La fonction devra simuler une étape du processus décrit en introduction:

  • créer une nouvelle liste L ayant même contenu que la liste initiale, sauf deux éléments a et b supprimés (choisis au hasard).
  • ajouter la valeur absolue de la différence de a et b à L.
  • renvoyer L.
Une réponse

Il existe bien des façons de répondre à la demande en Python.

En voici une:


from random import randint

def etape(liste):
    # un indice au hasard:
    i = randint(0, len(liste)-1)
    # un second indice au hasard
    j = 0
    while j == i:
        j = randint(0, len(liste)-1)

    a = liste[i]
    b = liste[j]
    L = [liste[k] for k in range(len(liste)) if k!=i and k!=j]
    L.append(abs(b-a))
    return L

Une autre:


from random import randint

def etape(liste):
    L = [x for x in liste]
    a = L.pop(randint(0, len(L)-1))
    b = L.pop(randint(0, len(L)-1))
    L.append(abs(b-a))
    return L

Question 2

En déduire une fonction python qui simule plusieurs "parties" du jeu d'Aurore.

Quelle conjecture peut-on émettre sur le nombre qui reste seul au tableau en fin de processus ?

Une réponse

On lance des parties avec le code ci-dessous.

La cinquantaine de résultats obtenus semble suggérer qu'une fin de partie est toujours paire.


from random import randint

def etape(liste):
    L = [x for x in liste]
    a = L.pop(randint(0, len(L)-1))
    b = L.pop(randint(0, len(L)-1))
    L.append(abs(b-a))
    return L

def partie(n):
    liste = [k for k in range(1,n+1)]
    while len(liste) > 1:
        liste = etape(liste)
    return liste[0]

def plusieurs_parties(n):
    """
    fin de parties pour une cinquantaine de parties
    """
    return [partie(n) for k in range(50)]


plusieurs_parties(2019)

Question 3

Exprimer la somme S' obtenue après une étape en fonction de la somme S avant cette étape.

Pour cela, on s'interdira d'utiliser la fonction valeur absolue: on envisagera deux cas.

Une réponse
  • Si a > b: S' = S - (a+b) + (a-b), soit S' = S -2b.
  • Sinon: S' = S -2a.

Question 4

Pouvez vous maintenant garantir qu'Aurore a commis une erreur de calcul ?

Une réponse Dans tous les cas la parité de S est un invariant: le dernier nombre obtenu ne peut être que pair et ne saurait être 3.
In [ ]: