Forum de mathématiques - Bibm@th.net

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Test à Pile [Résolu]

Une puissante lampe de poche fonctionne avec 4 piles type LR03 de 1,5 volt. Si l'une d'elles est défaillante, la lampe ne fonctionne plus.

En préparant mon sac pour faire de la spéléo le prochain WE, je me mets à chercher des piles neuves pour cette lampe. Je me souviens que ma femme, particulièrement ordonnée, avait rangé dans le même tupperware 16 piles du modèle souhaitées, mais en avait par mégarde mélangé 8 neuves avec 8 défaillantes.

Partie chez sa mère pour 15 jours, je me retrouve bien embarrassé. Au mieux, je mets 5 minutes (le temps de démonter, remonter et tester la lampe) pour trouver le bon jeu de 4 piles. Au pire, j'en ai pour ... oups, plus de 5 jours.

Pourriez vous m'aider, SVP ?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Test à Pile [Résolu]

Re,

Au pire, j'en ai pour ... oups, plus de 5 jours.

Meuh non... Y a bien un buraliste pas loin de chez toi où, en 10 min, tu pourras acheter 4 piles neuves ! ;-)
Mon papa dit toujours : << Quand on n'a pas de tête, faut avoir des jambes ! >>

... derien ! derien ! C'était juste pour faire avancer le schimiliblick...

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Test à Pile [Résolu]

Hey,

J'y avais bien pensé, mais pas de bol, il était sous la pile du pont qui s'est effondré l'autre jour !

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Test à Pile [Résolu]

Salut, les cracks,
Voyez cette histoire ! Et après ça, on s' étonne qu'il y ait deux millions de femmes battues en France ! Moi, ce qui m'étonne, c'est qu'il y ait environ vingt millions de femmes qui sont jamais battues ! On est vraiment un pays en pleine décadence!
Quant à Freddy, ne le prenez pas trop au sérieux : Chaque fois qu'il descend à la cave, il s'imagine qu'il fait de la spéléologie. Mais faut quand même essayer de l'aider : il a peur dans le noir !
Freddy, j'ai déjà pensé distraitement à ton problème depuis hier soir, il est intéressant : je vais essayer de continuer, mais je ne suis pas optimiste : si un plus doué que moi ne vient pas à ton secours, je crois qu'il faudra te résigner à prendre une bougie.

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Test à Pile [Résolu]

Salut, Freddy,
Quand on est un taupin, c'est normal de vouloir faire de la spéléologie. Ce qui est moins normal, c'est de pas être foutu de tester une pile....
Désolé ! Toutes les méthodes que j'ai essayée conduisent à un nombre d'essais considérables.
Quant à la méthode exhaustive, elle implique 16 x 15 x 14 x 13 = 43.680 possibilités (autrement dit, si tu préféres : factorielle 16 divisée par factorielle 12. Remarque que, sauf erreur de raisonnement de ma part (toujours possible),  ces 43.680 possibilites se décomposent en 1820 groupes de 24 mettant en jeu les 4 mêmes piles.
C'est tout de même moins décourageant.
Tout de même, à moins qu'un plus futé que moi t'offre une solution, prend ton vélo et va t'acheter un lampe digne de ce nom, avec des LR 20 (des LR 03 !! Pourquoi pas des piles bouton, pendant que tu y es !! ).

P.S. Ta femme absente pour 15 jours ! Je me demande quel genre de spéléologie tu pratiques.... Tu progresses vraiment avec une lampe de poche ? C'est une lampe torche ?

Dernière modification par nerosson (28-01-2010 19:18:13)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Test à Pile [Résolu]

Salut,

  J'ai essayé de résoudre un problème plus simple en divisant tout par deux. On a 8 piles, 4 fonctionnent, 4 ne fonctionnent pas, et on cherche à trouver 2 piles qui fonctionnent.
On commence par séparer les piles en 4 paquets de 2. Si un des 4 paquets fonctionne, c'est ok.
Sinon, dans chaque paquet, on a 1 pile qui fonctionne et 1 qui ne fonctionne pas.
On prend alors 2 paquets parmi ces 4 paquets, et on teste toutes les combinaisons possibles,
il n'y en a plus que 4*3/2=6. Ca fait au pire 10 tests.

Le problème, avec 16 piles, c'est que si on fait des paquets de 4 piles et qu'aucun ne fonctionne, on sait que dans chaque paquet, il y a 1,2 ou 3 piles qui fonctionnent. Donc on n'a pas forcément une information très précise...

Cela dit, je soupçonne notre probabiliste de faire un raisonnement du type : avec ce type de manipulations, l'espérance du nombre d'essais à faire est petite (en algorithmique, on parle de coût en moyenne, à différencier du coût dans le pire des cas).

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Test à Pile [Résolu]

Salut,

je confirme que la division par 2 du problème est intéressante, l'inconvénient est que passer ensuite à 4x4 paquets enferme l'imagination ... On tombe dans le fameux "obstacle épistémologique" cher à Bachelard. Cela étant, on doit aussi y arriver, mais il faut trouver la bonne procédure de test (c'est pour Barbichu, je pense ... j'ai un complice qui cherche).

Une solution qui sort des sentiers battus est de réutiliser le théorème des tiroirs, à savoir : former deux paquets de 8 piles ... Ainsi, on est sûr qu'un paquet contient au moins 4 bonnes piles ... reste ensuite à choisir un paquet et tester les piles 4 par 4 (70 combinaisons possibles).

Combien de temps cela va t-il prendre ? Sûrement pas 5x2x70 minutes (soit 11 heures et 40 minutes), car on peut trouver en moins de temps.

En effet, au pire, on trouve en 140 - 5 = 135 essais.

Mais je pense qu'on peut faire encore plus rapide ...

Dernière modification par freddy (01-02-2010 23:40:09)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Test à Pile [Résolu]

Re-

  J'ai mis un collègue à moi sur l'affaire, et il a trouvé une solution en 60 essais.
On commence par partager les piles en 8 paquets de 2, et on teste
tous ses paquets 2 à 2. Cela fait [tex]\binom{8}{2}=\frac{8\times 7}{2}=28[/tex] essais.

Si ca marche, c'est ok.

Sinon, on est nécessairement dans un des deux cas suivants :
1. Tous les paquets comportent une pile bonne et une pile mauvaise.
2. Un paquet comporte deux piles bonnes, un paquet comporte deux piles mauvaises, et les 6 autres comportent une pile bonne, une pile mauvaise.

On isole alors 4 paquets de 2 piles, et on teste toutes les choix possibles :
une pile du paquet 1, une pile du paquet 2, une pile du paquet 3, une pile du paquet 4.
Ca fait 2^4=16 essais.

Si on a trouvé 4 piles qui fonctionnent, c'est ok.
Sinon, c'est que forcément, dans ces 4 paquets de pile, on a un paquet de 2 mauvaises piles.
Mais alors, comme dans ces 8 paquets, il y en a au plus un avec deux mauvaises piles,
on considère les 4 autres paquets de 2 piles, et on fait les 2^4=16 mêmes essais.
Au cours de ces essais, on est sûr de trouver 4 piles qui conviennent.

Il faut donc au plus 28+16+16=60 essais.

Je crois que tu peux partir en spéléo maintenant!

Fred.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Test à Pile [Résolu]

Oups, trop fort !

Retour dimanche soir !