Accueil
Programme Primaire CM2Cours MathématiquesRésoudre des problèmes de dénombrement, d’optimisation et préparant à l’utilisation d’algorithmeundefined : Résoudre des problèmes de dénombrement, d’optimisation et préparant à l’utilisation d’algorithmeRésoudre des problèmes de dénombrement, d’optimisation et préparant à l’utilisation d’algorithme
Introduction
Les problèmes de dénombrement et d'optimisation sont bien plus fréquents qu'il n'y paraît. Néanmoins, on dit que ce sont des problèmes atypiques, c'est-à-dire qu'un schéma suivi d'un ou plusieurs calculs ne suffit pas pour les résoudre. Dans ce cours, nous allons découvrir des méthodes de résolution pour ce genre de problèmes.
Problèmes de dénombrement
Définition
Un problème de dénombrement est un problème dans lequel on cherche à compter le nombre de possibilités dans une situation donnée.
S'aider d'un tableau pour dénombrer les solutions
Pour déterminer le nombre de situations possibles, on peut faire des catégories de possibilités. Faire un tableau peut être une façon de se représenter clairement l'énoncé et la réponse qu'on lui donne.
Exemple
Prenons une boîte contenant plein de billes rouges, jaunes et vertes. Mathieu, qui souhaite jouer avec, en pioche trois.
Combien de possibilités de tirages peut-il avoir ?
Nous allons nous servir d'un schéma pour représenter toutes les possibilités. Appelons R la boule rouge, J la boule jaune et V la boule verte. Mathieu peut donc obtenir :
- 3 couleurs identiques :
- les combinaisons RRR, JJJ et VVV donnent 3 possibilités différentes.
- Deux couleurs identiques :
- les combinaisons RRJ, RRV, JJR, JJV, VVR et VVJ nous donnent 6 possibilités différentes.
- Toutes les couleurs différentes :
- ici, il n’y a que la combinaison RJV qui est possible.
|
3 couleurs identiques |
2 couleurs identiques |
Toutes les couleurs différentes |
|
RRR JJJ VVV |
RRJ RRV JJV JJR VVR VVJ |
RJV |
Il y a donc $3 + 6 + 1 = 10$ possibilités différentes.
Attention
Ne pas compter la même solution plusieurs fois : RJV et RVJ sont identiques.
S'aider d'un arbre pour dénombrer les solutions
S'aider d'un arbre pour dénombrer les solutions
Parfois, il est plus judicieux de résoudre un problème avec une autre méthode : celle-ci consiste à utiliser ce que l'on appelle un « arbre » dont les branches vont de possibilité en possibilité jusqu'aux dernières. Une fois que l'on a fini son arbre, il suffit de compter combien il a donné de branches à la fin.
Exemple
Au restaurant, le menu propose :
- Une entrée : salade de tomates ou quiche au fromage.
- Un plat : escalope de poulet ou filet de maquereau ou ratatouille.
- Un dessert : île flottante ou mousse au chocolat.
Combien de repas différents est-il possible d'avoir dans ce restaurant ?
Dans cet exemple, l'arbre permet de trouver douze possibilités de menu.
La composition : quiche au fromage / escalope de poulet / mousse au chocolat est l'une des douze possibilités de menu.
Problème d'optimisation
Problème d'optimisation
Définition
Un problème d'optimisation permet de rechercher la meilleure solution possible : on l'appelle la solution optimale.
Exemple
Mélanie souhaite fabriquer des coffrets de décoration.
Chaque coffret aura :
- 3 petits cœurs sur le couvercle ;
- 8 diamants mauves sur les côtés.
Elle a :
- 10 coffrets ;
- 24 cœurs ;
- 56 diamants mauves.
Combien de coffrets pourra-t-elle fabriquer au maximum ?
L'objectif est de trouver le plus grand nombre de coffrets que Mélanie peut fabriquer avec son stock.
- Il faut 1 coffret pour fabriquer 1 coffret de décoration.
- elle pourra produire au maximum 10 coffrets de décoration.
Mais a-t-elle assez de cœurs et de diamants ?
- Il faut 3 cœurs pour fabriquer 1 coffret. Mélanie a 24 cœurs. On calcule donc $24 \div 3 = 8$.
- Elle pourra produire au maximum 8 coffrets de décoration.
Mais a-t-elle assez de diamants mauves ?
- Il faut 8 diamants mauves pour fabriquer un coffret. Mélanie a 56 diamants. On calcule donc $56 \div 8 = 7$.
- Elle pourra produire au maximum 7 coffrets de décoration.
Avec son stock, elle pourra donc confectionner 7 coffrets de décoration au maximum.
Attention
Dans ce genre de problème, il faut faire tous les calculs avant de choisir la meilleure possibilité.
Problème préparant à l'utilisation d'algorithmes
Problème préparant à l'utilisation d'algorithmes
Ce genre de problème doit permettre de compter toutes les solutions possibles en utilisant plusieurs fois le même raisonnement.
Définition
Un algorithme est une suite d'étapes à effectuer pour obtenir un résultat. Les algorithmes permettent notamment de faire fonctionner les programmes d'ordinateurs.
Exemple
Matéo ne se rappelle plus du code à quatre chiffres de son cadenas qui permet d'ouvrir sa boîte secrète. Il se souvient seulement que :
- Le premier chiffre est un 4.
- La somme de tous les chiffres est égale à 7.
Quels sont tous les codes possibles pour ce cadenas ?
- On sait que le premier chiffre est 4, il faut donc chercher les 2ème, 3ème et 4ème chiffres possibles.
- On sait que la somme des quatre chiffres est égale à 7. Comme le premier chiffre est déjà connu, la somme des 2ème, 3ème et 4ème chiffres est donc 3, car $7 - 4 = 3$.
La stratégie à mettre en place est de regarder la plus grande valeur possible pour le 2ème chiffre.
- Ici c'est 3 car $4 + 3 = 7$. En prenant 4 et 3 nous avons obligatoirement 0 en 3ème chiffre et 0 en 4ème chiffres
Ensuite on essaie toutes les possibilités avec un 2e chiffre égal à 2.
- Ici on a $4 + 2 + 1 + 0$ ou $4 + 2 + 0 + 1$.
Puis on essaie toutes les possibilités avec un 1 en 2ème chiffre, et on terminera avec un 0 au 2ème chiffre.
On peut noter les possibilités dans un tableau pour clarifier ce que l’on a trouvé :
1er chiffre |
2e chiffre |
3e chiffre |
4e chiffre |
4 |
3 |
0 |
0 |
4 |
2 |
1 |
0 |
4 |
2 |
0 |
1 |
4 |
1 |
2 |
0 |
4 |
1 |
1 |
1 |
4 |
1 |
0 |
2 |
4 |
0 |
3 |
0 |
4 |
0 |
2 |
1 |
4 |
0 |
1 |
2 |
4 |
0 |
0 |
3 |
Il y a donc 10 codes possibles.
