The Muffin problem
Suis tombé sur cette conférence de William Gasarsh donnée à la Gathering 4 Gardner de 2018. Elle est géniale, visible ici sur YouTube et dure 4 minutes. Résumé ci-dessous.
Voici l'histoire : il s'agit de diviser en parts égales 5 pizzas entre 3 étudiants (affamés). Comment faire ? Eh bien par exemple comme ça :
On voit que ça marche facilement.
Mais la question que pose William Gasarch dans sa vidéo, c'est de savoir s'il existe une découpe où le plus petit morceau soit le plus grand possible ?
(Ici le plus petit morceau vaut 1/3 – il ira chez Carol avec le second morceau de 1/3 ; ainsi aura-t-elle en tout 1 pizza et 2/3 de pizza, comme les autres).
La réponse est oui – on peut découper mieux :
Voilà : avec cette découpe, le plus petit morceau vaut 5/12 [et, en effet, 5/12 est plus grand que 1/3 (de 1/12)].
Les trois personnes ont coupé autrement les 5 pizzas mais ont résolu le problème : il n'y a pas moyen de faire mieux, la taille maximum du plus petit morceau est, pour le couple {5,3} (étudiants/pizzas) de 5/12.
William Gasarch s'est posé la question de savoir si d'autres couples façon {5,3} étaient intéressants à analyser – et si l'on pouvait, pour tous ces couples, trouver à chaque fois un « plus petit morceau qui soit le plus grand possible ».
La réponse est... on ne sait pas ! Certains couples {étudiants,pizzas} où les étudiants sont jusqu'à 50 pour 60 pizzas, n'ont pas encore trouvé de solution aujourd'hui (9 couples irrésolus, semble-t-il, listés ci-dessous dans le tableau – avec LB = lower bound et UB = upper bound) :
Voici l'histoire : il s'agit de diviser en parts égales 5 pizzas entre 3 étudiants (affamés). Comment faire ? Eh bien par exemple comme ça :
Mais la question que pose William Gasarch dans sa vidéo, c'est de savoir s'il existe une découpe où le plus petit morceau soit le plus grand possible ?
(Ici le plus petit morceau vaut 1/3 – il ira chez Carol avec le second morceau de 1/3 ; ainsi aura-t-elle en tout 1 pizza et 2/3 de pizza, comme les autres).
La réponse est oui – on peut découper mieux :
Les trois personnes ont coupé autrement les 5 pizzas mais ont résolu le problème : il n'y a pas moyen de faire mieux, la taille maximum du plus petit morceau est, pour le couple {5,3} (étudiants/pizzas) de 5/12.
William Gasarch s'est posé la question de savoir si d'autres couples façon {5,3} étaient intéressants à analyser – et si l'on pouvait, pour tous ces couples, trouver à chaque fois un « plus petit morceau qui soit le plus grand possible ».
La réponse est... on ne sait pas ! Certains couples {étudiants,pizzas} où les étudiants sont jusqu'à 50 pour 60 pizzas, n'ont pas encore trouvé de solution aujourd'hui (9 couples irrésolus, semble-t-il, listés ci-dessous dans le tableau – avec LB = lower bound et UB = upper bound) :
Merci à William Gasarch et à la G4G pour ce problème et cette vidéo !
Commentaires
Enregistrer un commentaire