J'ai besoin de (vos) lumière(s)...

[Ben314]

Qui n'en veut du casse tête tout frais que je connaissait pas et que j'ai pas la soluce ?

Vous voulez remettre votre lampe de poche en état de marche.
Il vous faut donc trouver 4 piles en bon état, sauf que, dans votre fouillis, vous avez 16 piles mais vous savez que la moitié d'entre elles sont totalement hors service
Evidement, le seul moyen que vous avez pour tester les piles est de les mettre dans la lampe (par 4) et la lampe ne marche que si les 4 sont bonnes.

Naturellement, vous aimeriez limiter le plus possible le nombre d'essai. (là, l'énoncé n'est pas clair, on peut soit minimiser le nombre d'essais dans le pire des cas, soit le nombre moyen d'essai...)

:id2: Auriez vous quelques lumières sur le sujet ? :id2:

[nodgim]

Salut à toi.
Si on y va franco, on fait toutes les combis sauf les gagnantes, soit C(16,4)-C(8,4)+1=1751.

Sinon, on prend 8 piles et on fait toutes les combis =70. Au pire, il y a 3 bonnes piles dans ce groupe.
Ensuite, on prend 7 autres piles parmi lesquelles au moins 4 piles bonnes, donc C(7,4)=35 essais.
Donc au total 105 essais.

Y a t il un mieux disant ?

[LeJeu]

Dans la même idée
je fais un paquet de 7 + un paquet de 7 + 1 paquet de 2

1° paquet C(7,4) = 35 essais - si échec au pire 3 bonnes piles dans le paquet
2° paquet idem

3° paquet si échec dans les deux paquets précédents - alors on a deux bonnes piles !

On repart avec un des deux premiers paquets de 7 et on cherche les deux bonnes qui nous manquent
soit C( 7,2)

donc je dirais 2*C(7,4) +C(7,2)
soit 91

[nodgim]

Il y a mieux, avec 79 essais.
Je laisse réfléchir.

[LeJeu]

On repart avec un des deux premiers paquets de 7 et on cherche les deux bonnes qui nous manquent
soit C( 7,2)

donc je dirais 2*C(7,4) +C(7,2)
soit 91

Pour améliorer ma proposition :

Comme il y a au moins 3 bonnes piles dans le paquet de 7, on peut retirer une pile et ne chercher les 2 que dans 6
soit C(6,2)

pour un résultat final de 85

C'est mieux je me rapproche ...

[LeJeu]

Comme il y a au moins 3 bonnes piles dans le paquet de 7, on peut retirer une pile et ne chercher les 2 que dans 6
soit C(6,2)

un peu mieux : on fait un premier essai en prenant 2 piles dans le paquet de 7
Si pas ok on cherche dans les 5 autres

ce qui nous fait 1 +C(5,2)

pour un total de 81

[Galax]

Donc 80 car le dernier essai n'est pas vraiment nécessaire ?

[Galax]

Sauf erreur, après le meme depart que Lejeu, 70 essais pour faire 2 groupes de 7 (ayant chacun 3 bonnes piles) , et un groupe de 2 bonnes piles.
On teste ces 2 bonnes avec 2 parmi un sous groupe de 4 d'un des groupes de 7, soit 6 essais. Si échec alors on en a forcément 2 bonnes parmi 3 restantes, que l'on trouvera en 2 essais supplémentaires.
Soit 70+6+2=78

[nodgim]

C'est ça, et donc 79 manip pour allumer la lampe à la fin!

[alavacommejetepousse]

C'est ça, et donc 79 manip pour allumer la lampe à la fin!

on a largement le temps de courrir au prisu en acheter une neuve

[LeJeu]

Bien vu Galax et Nodgim

Pour revenir à la question de Benj : on (vous !) a optimisé le nombre maximum d'essais .
Ok

Mais : qu'en est-il du nombre moyen d'essais ? Quelle est l'espérance de réussite avec la solution de Nodgim?

Est ce que la démarche pour minimiser le maximum - minimise la moyenne ?

[LeJeu]

on a largement le temps de courrir au prisu en acheter une neuve

ok - aLaVaCommeJeTePousse

Tu reviens du prisu avec UNE pile neuve - Et après ? en combien de coup la soluce ?

[Ben314]

Salut tout le monde....
J'ai réfléchi tout le week-end à la question (sur les télésièges...)
Il me semble avoir une soluce (pire des cas en 60 essais) :
On fait 8 groupes de deux piles.

1) On teste tout les couples possible de groupes de deux piles -> 8*7/2=28 essais.
Si rien ne marche c'est que les huit groupes sont OK-HS ou bien qu'un couple est OK-OK, un est HS-HS et les six autres sont OK-HS.

2) On prend 4 des 8 groupes de deux piles et on teste toutes les combinaisons en en prenant une par groupe -> 2^4=16 tests.
Si rien ne marche c'est qu'il y a un groupe HS-HS dans les 4 groupes choisis.

3) Il n'y a plus qu'a prendre les 4 autres groupes de 2 piles et tester toutes les combinaisons en en prenant une par groupe

TOTAL : 28+16+16=60

PS : je n'ais pas regardé le "temps moyen" de cette méthode...

[nodgim]

Super, cette méthode.
Il me semble que, dans le final, on doit pouvoir faire mieux que 16, compte tenu des informations qu'on connait déja.

[Ben314]

Super, cette méthode.
Il me semble que, dans le final, on doit pouvoir faire mieux que 16, compte tenu des informations qu'on connait déja.

Je pense que tu est en train de commetre la même erreur que moi...
Dans les 4 derniers groupes de deux piles, on n'est pas sûr qu'il y ait le groupe OK-OK, il aurait pu être avec les 4 premiers groupes de 2 piles (i.e. avec le groupe HS-HS)...

Je viens de calculer l'espérance de cette méthode : 19,63 essais en moyenne mais j'ai utilisé l'ordi. car l'espérance dépend de l'ordre dans lequel on fait les 60 tests et j'ai fait calculer à l'ordi ce qui semble être le "meilleur" ordre (parmi les tests non encore effectué, on prend celui qui a le plus de chance d'être bon...)

[nodgim]

OK d'accord.

[Ben314]

Si il y en a que ça interesse : la méthode en 60 coups (maxi) avec une espérance de 19,63 est détaillée ici

En fait, si dés le départ, on cherche (avec l'ordi) le test ayant la plus grande probabilité, on tombe sur une soluce en 81 coups maxi mais avec une espérance de 18,64 : voir ici

Mais je ne vois pas de raison particulières pour lesquelles ces deux soluces soient optimale (la première pour le maxi, la seconde pour la moyenne)
Donc on risque de pouvoir faire mieux...