je dirais 16€ ~
on cherche entre 1~>144 un nombre donc on retranche de moitié a chaque fois qu'il appartienne ou pas à l'ensemble car on prend celui complémentaire.
etape 1 : E {1,...,72} au maximum perte de 2€
etape 2 : E {1,...,36} au maximum perte de 2€ -> -4€
etape 3 : E {1,...,18} au maximum perte de 2€ -> -6€
etape 4 : E {1,...,9} au maximum perte de 2€ -> -8€
etape 5 : E {1,...,6} au maximum perte de 2€ -> -10€
etape 6 : E {1,...,3} au maximum perte de 2€ -> -12€
etape 7 : après il reste 3 choix : 1,2 ou 3 (ou encore 3 autres chiffres se suivant)  et sachant qu'un mauvais choix = -1€ et qu'il y a 3 choix donc 2*-1=-2€ et que le dernier choix se finit par un -2€ alors -2-2=-4€
et -12-4 = -16€ il faut donc qu'il possède au minimum 16€

mais je ne sais pas du tout comment m'y prendre avec "p" nombres ^^"

En partant d'un nb d 'éléments de E croissant et en cherchant les meilleurs partages, on tombe sur la suite de Fibonacci.
Avec 144, qui est le 12 ème nombre de Fibo,on doit s'en sortir avec 11 euros.
Plus généralement on aura besoin de k-1 euros pour les nombres <= au kième nb de Fibo.

On découpe l'ensemble E en deux sous ensembles de même taille (on peut le faire car 144 est divisible par 2).
[TeX]E_1 = \{1,\ldots,72\}[/latex] et [latex]E_2 = \{73,\ldots,144\}[/TeX]
On demande si a est dans E1.
Si la réponse est OUI, on garde le premier ensemble (et on perd 2 euros). Si la réponse est NON, on garde le second ensemble (et on perd 1 euro).

On découpe encore en 2 l'ensemble gardé (72 est divisible par 2) et on demande la même chose que précédement. Si la réponse est OUI, on garde le premier ensemble (et on perd 2 euros). Si la réponse est NON, on garde le second ensemble.

On découpe encore en 2 l'ensemble gardé (36 est divisible par 2) et on demande la même chose que précédement. Si la réponse est OUI, on garde le premier ensemble (et on perd 2 euros). Si la réponse est NON, on garde le second ensemble.

On découpe encore en 2 l'ensemble gardé (18 est divisible par 2) et on demande la même chose que précédement. Si la réponse est OUI, on garde le premier ensemble (et on perd 2 euros). Si la réponse est NON, on garde le second ensemble.

Ensuite il nous reste plus qu'un ensemble à 9 éléments. On le découpe en 3 et on fait demande si a est dans le premier ensemble. Si OUI, on garde le premier ensemble. Sinon, on demande s'il est dans le deuxième ensemble. Si OUI, on garde le deuxième. Si NON, on garde le troisième.

Il nous reste plus qu'un ensemble à 3 éléments et on le divise en 3 (il ne restera plus qu'un élément) et on fait comme précédemment.

Donc si le nombre a = 144, on aura perdu 1+1+1+1+1+1+1+1 = 8 euros...

MthS-MlndN a écrit:

Mathias défigure Ash avec un cure-dents en le traitant de "sale Belge" et lui vole son portefeuille

clement.boulonne : Mauvaise réponse !

Bravo gwen Félicitation

Et bravo Scarta ! Excellent

non un peu moins

on a besoin de 11 euros.
Pour 144 on commence par donner un sous ensemble de 144/((3+√5)/2) soit 55 elements
si il dit oui, on a 55 elements restant si non il en reste 89
sur les 89, on donne un sous ensemble de 34 elements, qui nous donne soit 34 elements avec un cout de 3 ou 55 avec un cout de 2. On generalise:
144 coute 0
89 coute 1
55 coute 2
34 coute 3
21 coute 4
13 coute 5
8 coute 6
5 coute 7
3 coute 8
2 coute 9
1 coute 10 si on vient de 3
ou  10 ou 11 si on vient de 2
Donc le maximum dont on a besoin  est 11.
Je pense qu'on peut generaliser avec pour un nombre de depart N:
on a besoin de INT (2 * ln (N)÷ ln ((3+√5)/2))+1 euros. (INT etant la partie entiere du nombre)

Formule plus simple: F est la suite de Fibonacci toujours, et si
F(n) + 1 <= p <= F(n+1); alors la réponse est n+1

(Ben oui, la somme des termes de la suite de Fibonacci peut aussi s'exprimer sous la forme d'un nombre de Fibonacci). Du coup, je pense qu'à démontrer, ça doit être plus simple

Exemple ici: F(10) = 89; F(11) = 144 donc comme 90 <= 144 <= 144; la réponse est 11

Pas réussi à trouver de formule générale, mais je peux dire que la proportion de nombres à prendre dans le sous-ensemble doit s'approcher de 1/3.

Par contre je pense avoir trouvé un algorithme pour trouver la réponse, que j'ai mis en œuvre dans un tableur.

Pour p=144, ma réponse est 12.

Il suffit de trouver [latex]x[/latex] le nombre d'itération ou l'on divise le nombre d'élément par 2 pour se retrouver avec un seul et unique [latex]p_i[/latex]

On résout donc :
[TeX]\frac{p}{2^x}=1[/latex] donne [latex]x=\frac{-ln(\frac{1}{p})}{ln(2)}[/latex] avec [latex]\frac{1}{p}>0[/TeX]
Avec [latex]p[/latex] éléments il faudra payer [latex]x[/latex] euros soit avec 144 éléments [latex]\fbox{x=\frac{2.ln(12)}{ln(2)}=7.1699...}[/latex] donc 8€


Shadock (En espérant ne pas avoir dit de bêtises)

Effectivement j'avais oublié des possibilités, la somme minimale est de 11. Il faut prendre un premier sous ensemble de 55 éléments, après c'est en fonction des réponses de Ash.

Toujours pas capable de donner de formule générale...