Énigme
Un bateau transportant des clés USB EURODECISION a été attaqué par des pirates et 100 sacs contenant chacun 100 clés USB ont été subtilisés. Comme l’équipage d’EURODECISION s’attendait à cette attaque, elle avait anticipé le coup et avait préalablement rempli les sacs de fausses clés USB. Mais dans la précipitation, un « bon » sac a été oublié parmi les autres. Les vraies clés USB, contenant d’excellents algorithmes, sont légèrement plus lourdes que les fausses clés : une fausse clé pèse 1 g, alors qu’une vraie clé pèse 1,01 g.
Vous disposez d’une balance numérique, et comme vous aimez l’optimisation, vous souhaitez minimiser le nombre de pesées pour identifier le bon sac (parmi les 100 sacs volés).
Quel est le nombre minimum de pesées nécessaire pour identifier le bon sac ?
Solution
Il est possible de déterminer le sac avec les vraies clés USB en une seule pesée.
Pour cela, numéroter les sacs de 0 à 99, et prendre 0 clé du sac 0, 1 clé du sac 1, 2 clés du sac 2, et ainsi de suite jusqu’au sac 99.
On a donc un total de 1+2+…+99 = 4950 clés.
Le poids P donné par la balance vaut P = 4950 x 1 + N x 0.01, où N est le numéro du sac contenant les vraies clés USB.
En isolant N, on obtient N = (P – 4950)x 100, ce qui nous donne directement le numéro du bon sac.