Transport de fromages - Collège Jean Jaurès (Calais)

Titre du sujet
Transport de fromages
Établissement
Collège Jean Jaurès (Calais)
Année
2018-2019
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. Sur chaque route, on ne peut transporter qu'un nombre pair de fromages ; en le faisant, le renard embusqué en prélève la moitié.

Le but est d'arriver à livrer au moins un fromage à Calais.

Question : Combien de fromages faut-il au minimum pour que, quelle que soit leur distribution initiale, il soit toujours possible d'atteindre le but ?