chasse au cafard

[akasolace 0]

Soit n cases successives sur lesquelles un insecte microscopique se déplace. 
Une personne qui n'arrive pas à voir l'insecte - car trop petit, veut éliminer l'insecte. S'il y parvient, il le saura, car l'insecte dégagera alors une odeur nauséabonde.
La personne peut pulvériser l'insecticide sur une case a la fois, alors:
       - soit l'insecte meurt
       - soit il se déplace vers une case adjacente de manière aléatoire


La personne adopte une stratégie S(n) lui permettant de minimiser la quantité d'insecticide a répandre - noté que S(n) ne minimise pas forcéement l'espérance !

Soit E(n) le nombre moyen de doses nécessaires pour éliminer l'insecte

Sachant que E(1)=1, E(2)=1.5, E(3)=1.5 et E(4)=2.3125, que vaut  E(5) ?


Précision : le calcul de E(n) sera basé uniquement sur tous les trajets possibles de l'insecte exactement S(n) déplacements, comme s'il se déplaçait toujours S(n) fois, qu'il ait été pulvérisé avec de l'insecticide ou non.

[Cybero 4 206]

Merci pour ta participation  

 

Perso mes maths doivent être trop loin...

Je trouve l'énoncé un peu compliqué par rapport à la question mais bon

J'ai du mal à saisir comment

1. Comment E(2) peut-être égal à E(3) et différent de E(4)
2. Comment réfléchir  

La précision ne fait que rajouter du brouillard dans la tête

Je ne comprends rien à S(n)

 

Bref, c'est ps gagné

[akasolace 0]

pour n= 1, une seule case donc S(1) = 1 et E(1) = 1

pour n=2, on vise d'abord une case, puis ensuite la même pour etre sur de gagner  (soit on tue l'insecte la premiere ois ou alors la deuxieme s'il était sur l'autre case)

S(2) = 2   E(2) = 1*1/2 + 2*1/2 = 1.5

 

[ribi 763]

D'accord avec E(3).

Pour le moment, j'estime mal E(4), j'en suis à 2.4375.

Minimiser l'insecticide, c'est bien minimiser le nombre de coups pour être sûr d'avoir tué le cafard ?

 

[akasolace 0]

@ribi alors moi c'est l'inverse je trouve E(4) mais je ne trouve pas E(3) !

comment fais-tu pour E(3) ?

[ribi 763]

Révélation

Pour trois cases :

Premier coup : on frappe au milieu :

statistiquement un tiers de cafard de  tué

Deuxième coup : le cafard qui n'était pas au milieu se met au milieu, donc on refrappe au milieu.

Le cafard est  mort quoi qu'il arrive.

L'espérance est 1/3+2*2/3=5/3 et non pas 3/2 comme je l'avais dit prématurément.

Une moyenne entre 1 et 2 n'est pas forcément 3/2  .

 

Quoique, quoique, je relis l'énoncé, on compte tous les déplacements possibles, donc ça change tout : le premier cafard tué compte double parce qu'il avait deux déplacements possibles au deuxième tour.

Donc 1/4*2+2*2/4= 3/2 = E(3)

mes erreurs se sont compensées. 🍀

 

[ribi 763]

Révélation

Du coup pour 4 les possibilités de mouvement des cafards sont :

1234

1232

1212

2343

2323

2321

2123

2121

3434

3432

3234

3232

3212

4343

4323

4321

On peut tuer à coup sûr le cafard en 4 coups en frappant successivement 2,3,3,et 2.

En rouge le coup mortel :

Ce qui donne en moyenne (3+3+4+1+1+1+1+1+3+3+3+3+4+2+2+2)/16=2,3125=E(4)

 

[Cybero 4 206]

Sujet déplacé dans les demandes d'aide.

[ribi 763]

Pour n=5, je vois très bien une stratégie en 6 coups qui permet de tuer à coup sûr la cafard.

Révélation

Soit 2,3,4,4,3,2 soit 2,3,4,2,3,4 (pour la suite des cases à écraser)

Il ne reste plus qu'à évaluer l'espérance sur l'ensemble des parcours de 6 cases possibles.

Âmes sensibles s'abstenir :

Révélation

(j'en ai peut être oublié) En rouge le coup de la mort pour la stratégie 234432

(234234 est pareil)

123454
123434
123432
123234
123232
123212
121234
121232
121212
234545
234543
234345
234343
234323
234321
232345
232343
232323
232321
232123
232121
212345
212343
212323
212321
212123
212121
345454
345434
345432
343454
343434
343432
343234
343232
343212
323454
323434
323432
323234
323232
323212
321234
321232
321212
454545
454543
454345

454343
454323
454321
434545
434543
434345

434343
434323
434321
432345
432343
432323
432321
432123
432121
545454
545434
545432
543454
543434
543432
543234
543232
543212

Nombre de cas 9+18+18+18+9=72

 

Ce qui nous fait E(5)=1*1/4+2*1/6+3*1/12+4*1/4+5*1/6+6*1/12=1/4+1/3+1/4+1+5/6+1/2=3+1/6=3,1666... (aux erreurs de calcul près)

 

 

[Cybero 4 206]

 

[Cybero 4 206]

@akasolace ?

[Cybero 4 206]

Sans réponse de l'auteur, ce sujet sera suspendu d'ici quelques jours

 

Ceci est une réponse automatique due à une absence de nouvelles de l'auteur de l'énigme

[Freddy 235]

Révélation

L'énoncé est plutôt ambigu. On ne sait pas trop ce qu'est S(n), ni ce qu'est l'espérance. Est-ce que l'espérance est E(n) ? Comment les cases sont-elles disposées ? J'ai supposé qu'elles sont en ligne et que l'insecte se retrouve limité dans ses déplacements lorsqu'il atteint une extrémité. Cela dit, j'ai beau lire les explications données, j'ai du mal avec les propositions E(3) = 3/2 et E(4) = 2,3125.

 

Tout d'abord, en s'inspirant de ce que Ribi a expliqué plus haut, on détermine les stratégies gagnantes.

• Tableau de 1 case : 1
• Tableau de 2 cases : 11 ou 22
• Tableau de 3 cases : 22
• Tableau de 4 cases : 2332 ou 3223
• Tableau de 5 cases : 234234 ou 234432 ou 432234 ou 432432
• Tableau de 6 cases : 23455432 ou 54322345
• Tableau de 7 cases : 2345623456 ou 2345665432 ou 6543223456 ou 6543265432

Il faut bien voir que l'insecte passe d'une case paire à une case impaire, ou d'une case impaire à une case paire. Il n'a pas le choix, il ne peut pas rester sur une case de même parité. La stratégie gagnante consiste donc à balayer le tableau (23456) et après 6 ne pas changer de parité (revenir à 2 par exemple). Ainsi, l'un des deux voyages 23456 se fera sur des cases de même parité que l'insecte, ce qui empêchera l'insecte et le pulvérisateur de se croiser sans se toucher. Lorsqu'on arrive sur le 2 pour la deuxième fois sans avoir touché l'insecte, celui-ci est forcément à droite du pulvérisateur et sur une case paire (tester les différents cas possibles pour se convaincre). Il est donc cuit et lors de la deuxième montée 23456 on ne pourra pas le louper.

 

Pour un tableau de 4 cases, on est sûr de pouvoir atteindre l'insecte en 4 coups maximum. Pour 5 cases, c'est 6 coups maxi.

En fait, si l'on pulvérise jusqu'au bout de la stratégie, même quand l'insecte est touché, et si l'on considère que E(n) est le nombre moyen de pulvérisations, alors c'est simple :

• Si n = 1, E(n) = 1
• Si n > 1, E(n) = 2(n-2)

Mais je me doute bien que ce n'est pas la réponse attendue !

 

Par contre, si E(n) est le nombre moyen de pulvérisations nécessaires pour éliminer l'insecte, alors :

• E(1) = 1
• E(2) = 1,5 = 3/2
• E(3) = 1,666... = 5/3
• E(4) = 2,4375 = 39/16
• E(5) = 3,55 = 71/20
• E(6) = 4,359375 = 279/64
• ...

Les calculs sont à vérifier. Pour trouver ces résultats, il faut énumérer, en prenant en compte tous les trajets possibles de l'insecte.

Note : puisque E(n) est le nombre moyen de pulvérisations nécessaires pour éliminer l'insecte, le fait de continuer à pulvériser jusqu'au bout ne change rien à l'affaire.

 

En résumé, je pense que E(3) = 1,5 et E(4) = 2,3125 ne sont pas des réponses correctes.