Solution du défi
Choisis l'énigme dont tu veux voir une solution.Explications : Une fois qu'on a compris la consigne, on peut essayer tous les ordres et on trouve alors 53 minutes.
Plats | Temps de préparation (mns) | Temps de cuisson (mns) |
---|---|---|
A | 11 | 16 |
B | 8 | 12 |
C | 15 | 17 |
L'ordre optimal est donné par BAC. Les temps de cuisson étant longs par rapport aux temps de préparation, il faut utiliser le four le plus vite possible en commençant par la plus petite préparation et ranger ensuite les plats dans l'ordre croissant des temps de préparation pour employer le four en continu. Le résultat obtenu est optimal car une borne inférieure est donnée par temps total de cuisson (45) + temps minimal de préparation (8) = 53.
Source : Énigme issue de l’expo « Dans ma cuisine ».
Référence : dossier scientifique de l’expo pour les preuves (Solution téléchageable en PDF)
Explications : Une fois qu'on a compris la consigne, on peut essayer tous les ordres et on trouve alors 49 minutes.
Plats | Temps de préparation (mns) | Temps de cuisson (mns) |
---|---|---|
A | 16 | 8 |
B | 11 | 10 |
C | 14 | 14 |
L'ordre optimal est donné par CAB. Cette fois-ci, ce sont les temps de cuisson qui sont courts. L'idée est alors de finir par la plus petite cuisson et en fait de ranger les plats par ordre décroissant de temps de cuisson. Le temps obtenu est optimal car une borne inférieure est donnée par temps total de préparation (41) + temps minimal de cuisson (8)=49.
Source : Énigme issue de l’expo « Dans ma cuisine ».
Référence : dossier scientifique de l’expo pour les preuves (Solution téléchageable en PDF)
Explications : Ce n’était pas facile car une fois qu'on a compris la consigne, on ne peut pas forcément essayer tous les ordres. On peut se convaincre après tâtonnement qu'on a trouvé la solution optimale de 102 minutes.
Plats | Temps de préparation (mns) | Temps de cuisson (mns) |
---|---|---|
A | 12 | 8 |
B | 8 | 12 |
C | 17 | 20 |
D | 19 | 12 |
E | 19 | 20 |
F | 19 | 17 |
L'ordre optimal est donné par BCEFDA. C'est un mélange des deux premiers. L'algorithme de Johnson (1953) donnera toujours la solution optimale et il fonctionne ainsi : dans le premier groupe, on met tous les plats dont la préparation est plus courte que la cuisson (BCE) et on les classe dans l'ordre croissant des temps de préparation (BCE) puis dans le deuxième groupe, on met les plats dont le temps de cuisson est plus court que le temps de préparation (ADF) et on les classe par ordre décroissant des temps de cuisson (FDA). L'ordre optimal est donné par les plats du premier groupe ainsi ordonnés suivis des plats du deuxième groupe ainsi ordonnés. Ici on obtient un temps de 102 qui est aussi nécessairement optimal car il atteint une des deux bornes inférieures précédentes puisque le temps de préparation total est de 94 minutes et le temps minimal de cuisson de 8 minutes.
Source : Énigme issue de l’expo « Dans ma cuisine ».
Référence : dossier scientifique de l’expo pour les preuves (Solution téléchageable en PDF)
Retour au calendrier.