| G244. Les puces de mon vieux PC |
|
| G2. Combinatoire - Dénombrements |
 
Mon vieux PC est équipé de quatre puces mises en série qui
sont toutes hors d'usage. Je dispose
d'un lot de seize puces de rechange dont huit sont défectueuses mais j'ignore
lesquelles. L'ordinateur fonctionne seulement quand les quatre puces sont en
bon état.Pour installer une ou plusieurs puces ou les retirer, je prends
toujours la précaution d'éteindre l'ordinateur et chaque essai entre deux
allumages dure deux minutes. Avec mes réminiscences d'analyse combinatoire, je
sais qu'il y a C(16,4) = 1820 façons de choisir quatre puces dans un lot de
seize puces parmi lesquelles il y a seulement C(8,4) = 70 façons d'en prendre
quatre qui sont en bon état.Dans le cas le plus défavorable ma réparation peut
donc durer fort longtemps.Je vous demande de m'aider à réduire la durée
maximale D de la réparation. Déterminer la plus petite valeur possible de D.
SolutionIl est facile de voir qu'après le partage des 16 puces en deux lots de 8 puces chacune, le principe des tiroirs garantit au moins 4 bonnes puces dans l'un des 2 lots. Dans le pire des cas, en testant les puces de ce deux lots prises 4 par 4, il y a donc 2*C(8,4) = 2*70 = 140 essais qui demandent 280 mn soit 4h 40 mn. Tous les lecteurs qui ont traité ce problème ont amélioré sensiblement ce score en opérant une partition des 16 puces en sous-lots de a,b,c,... puces. Les réponses font apparaître un large éventail avec des sous-lots de même taille (par exemple : 4,4,4,4) ou distincts (par exemple 9,7 ou 7,7,2). Michel Lafond a réalisé le meilleur temps D avec 60 essais, suivi par Claudio Baioochi avec 71 essais. Peut-on faire mieux? Voir les solutions de: Michel Lafond,Claudio Baiocchi,Jérôme Pierard,Yves Etievant,Jean Moreau de Saint Martin,Pierre Henri Palmade,Claude Morin.
|