Transport de fromages - Collège Lucien Vadez (Calais)

Établissement
Collège Lucien Vadez (Calais)
Année
2014-2015
Résumé
Le réseau de transport de la Région est représenté par un graphe ; l'une des villes est Calais. Dans chaque ville se trouve un entrepôt de fromages de Maroilles. Et sur chaque route est embusqué un renard par l'odeur alléché.
‣ On transporte des fromages le long des routes, d'une ville à une ville voisine.
‣ Mais, sur chaque route, le renard embusqué prélève la moitié des fromages transportés. Plus précisément, si on transporte un nombre impair de fromages, le renard en prélève la moitié supérieure. Par exemple, si on transporte 7 fromages, le renard en prélève 4.
‣ But : livrer au moins un fromage à Calais.
‣ Question : combien de fromages faut-il avoir au minimum pour que, quelle que soit la façon de les entreposer au début, il soit toujours possible d'atteindre le but ?
‣ Par exemple, pour le graphe O---O---O représentant Calais-Gravelines-Dunkerque, il suffit de placer 4 fromages n'importe où pour atteindre le but. Par contre, avec seulement 3 fromages placés à Dunkerque, c'est impossible. La bonne réponse est donc 4.
‣ En général, la réponse dépend de la complexité du graphe et du nombre de villes. Tester d'abord les “graphes ligne” comme dans l'exemple, puis des arbres, etc... Bon appétit !