Très jolie variante dhrm77
je vais essayer de la résoudre ( avec la contrainte du temps )
merci pour ces énigmes

J'ai fait tourner mon programme de l'énigme précédente :

find_u(1000000000, 10, 1)
> 121
find_u(1000000000, 9, 2)
> 143
find_u(1000000000, 8, 3)
> 157
find_u(1000000000, 7, 4)
> 164
find_u(1000000000, 6, 5)
> 167

Il faut donc choisir 10 et 1

La méthode de résolution des différents cas est la même que pour les énigmes précédentes donc je vais me contenter de donner les résultats :

a) 121
b) 143
c) 157
d) 164
e) 167

Ça peut paraître étonnant, mais on observe que moins la répartition est équilibrée, moins ça coûte cher. On peut le comprendre en comparant les rapports efficacité/coût pour les cas a) et e) quand les ensembles sont encore grands:

a) On prend une fraction x de l'ensemble.
Si la réponse est oui, on a un coût de 10 pour une réduction d'un facteur 1/x : r=log(1/x)/10
Si la réponse est non, on a un coût de 1 pour une réduction d'un facteur 1/(1-x) : r=log(1/(1-x))
On chercher à maximiser r dans le pire cas donc à que les 2 r soient équivalents :
log(1/x)/10=log(1/(1-x))
log(x)/10=log(x-1)
[TeX]\sqrt[10]{x}=x-1[/TeX][TeX]x\approx0,164921[/TeX]
[TeX]r\approx0,078272[/TeX]
Vous allez me demander pourquoi j'utilise le log, hé bien c'est parce qu'on a besoin que l'efficacité d'une réduction d'un facteur 100 soit le double de celle d'une réduction d'un facteur 10. Propriété vérifiée par le log : log(100)=2log(10)

e) On prend une fraction x de l'ensemble.
Si la réponse est oui, on a un coût de 6 pour une réduction d'un facteur 1/x : r=log(1/x)/6
Si la réponse est non, on a un coût de 5 pour une réduction d'un facteur 1/(1-x) : r=log(1/(1-x))/5
On chercher à maximiser r dans le pire cas donc à que les 2 r soient équivalents :
log(1/x)/6=log(1/(1-x))/5
log(x)/6=log(x-1)/5
[TeX]\sqrt[6]{x}=\sqrt[5]{x-1}[/TeX][TeX]x\approx0,468445[/TeX]
[TeX]r\approx0,05489[/TeX]