Problème 1014
Dans un tiroir, il y a un nombre pair de piles électriques du type "AA". On sait qu'il y en a autant de bonnes que de mauvaises.Pour les tester, Alice ne dispose que d'une lampe torche, qui s'allume à condition que les deux piles qu'on y insère soient bonnes. Elle annonce à Bob qu'il lui faudra au maximum 6 essais pour faire marcher la lampe.
- 1A, 1B, 1C, 1D, 1E. Combien y a-t-il de piles "AA" dans le tiroir ?
S'il y a plusieurs solutions, les écrire dans l'ordre croissant sur la ligne 1, du plus petit au plus grand nombre.
- 2A. Au bout de combien d'essais Bob est-il sûr de voir la lampe s'allumer ?
Le code écrit pour ce problème calcule, pour un nombre N de piles fixé, toutes les paires de piles, puis énumère pour i croissant toutes combinaisons de i paires jusqu'à en trouver une qui satisfasse le critère. Pour tester ce critère, il faut, pour une combinaison de i paires donnée, tester si toutes les configurations de piles valides/non valides résultent en au moins une des paires contenant 2 piles valides.
Cet algorithme explose bien sûr très vite combinatoirement quand le nombre de piles augmente : la valeur maximale possible pour N est de 12 (complétion en moins d'une minute pour 10, en près de deux heures pour 12). Néanmoins, en le testant pour 4, 6, 8, 10 et 12, on peut voir le schéma qui se met en place et en déduire la construction pour un nombre quelconque de piles.
Le code est disponible ici.
Cet algorithme explose bien sûr très vite combinatoirement quand le nombre de piles augmente : la valeur maximale possible pour N est de 12 (complétion en moins d'une minute pour 10, en près de deux heures pour 12). Néanmoins, en le testant pour 4, 6, 8, 10 et 12, on peut voir le schéma qui se met en place et en déduire la construction pour un nombre quelconque de piles.
Le code est disponible ici.
- 1A, 1B. Il y a 4 ou 6 piles « AA » dans le tiroir.
- 2A. Avec 20 piles, Bob est sûr d'allumer la lampe au bout de 13 essais.