Enigme pour les surdoués, l'élite de l'élite est-elle présente ?

Le 15 janvier 2023 à 16:33:47 :

Le 15 janvier 2023 à 16:31:04 :

Le 15 janvier 2023 à 16:28:26 :
Soit X le palier que l'on veut optimiser (tous les X etages on lance la pasteque).

Il faut 100/X essais pour que la pasteque se brise et ensuite X essais pour determiner le palier exacte.

Donc on veut le minimum de 100/X + X

C'est atteint en X=10

On lance tous les 10 etages

Pourquoi prendre un seuil constant ?

Car les étages sont les mêmes (c'est "linéaire" si tu veux mais oui on pourrait prendre une autre stratégie et montrer que dans le pire des cas il y aura toujours plus du 20 essais alors qu'avec ma stratégie c'est 20 essais au maximum)

Non on ne pourrait pas car c'est faux

Imaginons que la reponse est 51

Tester le palier 1-100, donc tu lances a 50
puis tester le palier 50-100, donc tu testes a 75
puis tester le palier 50-75, donc tu testes a 62
puis tester le palier 50-62, donc tu testes a 56
puis tester le palier 50-56, donc tu testes a 53
puis tester le palier 50-53, donc tu testes a 52
puis tester le palier 50-52, donc tu testes a 51

Donc en 7 tests maxi, tu trouves le resultats que que soit le nombre de depart

Quand vous lancez une pastèque, il y a 2 issues :
- explosion => je descend dans l'immeuble. (cas 1)
- pas exmplosion => je monte dans l'immeuble. (cas 2)

On veut limiter le nombre d'essais. On veut donc avoir le plus petit nombre d'essais même dans le pire scenrio
Or plus on lache une pastèque haut dans l'immeuble, plus ça augmente le nombre d'essais necessaires dans le scenario cas du cas 1.
Et inversement, plus on lache une pasteque bas, plus ça augmente le nombre d'essais necessaires dans le pire scenario du cas 2.

Ainsi, il y a un equilibre à trouver entre les 2. Il faut donc égaliser le pire scenrario dans chaque cas

Je lache une pasteque à l'étage n :
- Si elle explose, je dois tester tous les étages entre 1 et n-1
=> pire scenrario = (n-1) - 1 + 1 + (le lancer du début)
=> pire scenrario = n
- Si elle n'explose pas, je dois monter de "p" étages. Puis, si elle explose, tester tous les étages de n+1 à n+p-1
=> pire scenario = (le lancer du début) + (le deuxieme lancer) + (n+p-1) - (n+1) + 1
=> pire scenario = p+1

On doit donc avoir n = p+1.

Autrement dit, si vous êtes montés de n étages à un moment, il faut, au lancer d'après monter de (n-1) étages.
Toujours pour minimiser le nombre de lancers, il faut pouvoir arriver à peu près à 0 quand on est arrivé à l'étage 100.
On résoud donc :

(somme des chiffres de 1 à n) > 100
(n*(n+1))/2 > 100
n² + n - 200 > 0
n > 13.5
n = 14

14 est le plus petit nombre n tel que la somme des nombre de 1 à n vaut au moins 100.

Lancer a l'etage 50
Puis au 25 (ou au 75 si elle a explosée)
Puis au 12 (ou au 18 si elle a explosé)

Etc... Bref toujours réduire ou augmenter de 50%

Par palier constant c'est 10 étages le mieux, il suffit de calculer l'espérance d'essais.

E = (1 + 2 + 3 + ... + 10 + 2 + 3 + .... + 10 + 3 + 4 + ... + 11 + .... + 11 + 12 + .... + 20) / 100

Rien ne sera mieux

Le 15 janvier 2023 à 16:34:47 :

Le 15 janvier 2023 à 16:33:47 :

Le 15 janvier 2023 à 16:31:04 :

Le 15 janvier 2023 à 16:28:26 :
Soit X le palier que l'on veut optimiser (tous les X etages on lance la pasteque).

Il faut 100/X essais pour que la pasteque se brise et ensuite X essais pour determiner le palier exacte.

Donc on veut le minimum de 100/X + X

C'est atteint en X=10

On lance tous les 10 etages

Pourquoi prendre un seuil constant ?

Car les étages sont les mêmes (c'est "linéaire" si tu veux mais oui on pourrait prendre une autre stratégie et montrer que dans le pire des cas il y aura toujours plus du 20 essais alors qu'avec ma stratégie c'est 20 essais au maximum)

Non on ne pourrait pas car c'est faux

Et pourquoi ?

Si on avait autant de pasteques il suffirait de subdiviser en deux parts égales à chaque fois mais là ce n'est pas le cas.

Le 15 janvier 2023 à 16:39:13 :

Le 15 janvier 2023 à 16:34:47 :

Le 15 janvier 2023 à 16:33:47 :

Le 15 janvier 2023 à 16:31:04 :

Le 15 janvier 2023 à 16:28:26 :
Soit X le palier que l'on veut optimiser (tous les X etages on lance la pasteque).

Il faut 100/X essais pour que la pasteque se brise et ensuite X essais pour determiner le palier exacte.

Donc on veut le minimum de 100/X + X

C'est atteint en X=10

On lance tous les 10 etages

Pourquoi prendre un seuil constant ?

Car les étages sont les mêmes (c'est "linéaire" si tu veux mais oui on pourrait prendre une autre stratégie et montrer que dans le pire des cas il y aura toujours plus du 20 essais alors qu'avec ma stratégie c'est 20 essais au maximum)

Non on ne pourrait pas car c'est faux

Et pourquoi ?

Si on avait autant de pasteques il suffirait de subdiviser en deux parts égales à chaque fois mais là ce n'est pas le cas.

Parce que la réponse optimalte est inférieure à 20 et se fait avec une incrémentation non constante

Le 15 janvier 2023 à 16:39:48 :

Le 15 janvier 2023 à 16:39:13 :

Le 15 janvier 2023 à 16:34:47 :

Le 15 janvier 2023 à 16:33:47 :

Le 15 janvier 2023 à 16:31:04 :

> Le 15 janvier 2023 à 16:28:26 :

>Soit X le palier que l'on veut optimiser (tous les X etages on lance la pasteque).

>

> Il faut 100/X essais pour que la pasteque se brise et ensuite X essais pour determiner le palier exacte.

>

> Donc on veut le minimum de 100/X + X

>

> C'est atteint en X=10

>

> On lance tous les 10 etages

Pourquoi prendre un seuil constant ?

Car les étages sont les mêmes (c'est "linéaire" si tu veux mais oui on pourrait prendre une autre stratégie et montrer que dans le pire des cas il y aura toujours plus du 20 essais alors qu'avec ma stratégie c'est 20 essais au maximum)

Non on ne pourrait pas car c'est faux

Et pourquoi ?

Si on avait autant de pasteques il suffirait de subdiviser en deux parts égales à chaque fois mais là ce n'est pas le cas.

Parce que la réponse est inférieure à 20 et se fait avec une incrémentation non constante

Désolé avec 10 c'est 19 le pire des cas et pas 20

Le 15 janvier 2023 à 16:42:42 :

Le 15 janvier 2023 à 16:39:48 :

Le 15 janvier 2023 à 16:39:13 :

Le 15 janvier 2023 à 16:34:47 :

Le 15 janvier 2023 à 16:33:47 :

> Le 15 janvier 2023 à 16:31:04 :

>> Le 15 janvier 2023 à 16:28:26 :

> >Soit X le palier que l'on veut optimiser (tous les X etages on lance la pasteque).

> >

> > Il faut 100/X essais pour que la pasteque se brise et ensuite X essais pour determiner le palier exacte.

> >

> > Donc on veut le minimum de 100/X + X

> >

> > C'est atteint en X=10

> >

> > On lance tous les 10 etages

>

> Pourquoi prendre un seuil constant ?

Car les étages sont les mêmes (c'est "linéaire" si tu veux mais oui on pourrait prendre une autre stratégie et montrer que dans le pire des cas il y aura toujours plus du 20 essais alors qu'avec ma stratégie c'est 20 essais au maximum)

Non on ne pourrait pas car c'est faux

Et pourquoi ?

Si on avait autant de pasteques il suffirait de subdiviser en deux parts égales à chaque fois mais là ce n'est pas le cas.

Parce que la réponse est inférieure à 20 et se fait avec une incrémentation non constante

Désolé avec 10 c'est 19 le pire des cas et pas 20

Désolé la réponse optimale est aussi inférieure à 19

Voici un algorithme qui me semble pas trop risqué

Soit N le nombre d'étages qu'on explore
Au début N=33 (nombre d'etge total /3)
On lance à N
Si ça explose on lance de 1 à N jusqu'à ce que ça explose
Sinon on recommence la boucle avec N = (100+2N)/3

Ainsi dans le pire des cas on fait 33 occurrences de lancer de pastèque

Ma logique est donc qu'il faut explorer tiers par tiers. On teste à 33, si ça explose faut explorer les 33 étages un à un vu qu'il nous reste qu'une pastèque, si ça explose pas faut explorer les 67 étages restant en utilisant la même méthode. On va donc tester au premier tiers des 67 étages restant soit l'étage 55, si ça explose pas on teste l'étage 70 puis 80 puis 86 etc..

J'espère que je suis clair

Le 15 janvier 2023 à 16:43:17 :

Le 15 janvier 2023 à 16:42:42 :

Le 15 janvier 2023 à 16:39:48 :

Le 15 janvier 2023 à 16:39:13 :

Le 15 janvier 2023 à 16:34:47 :

> Le 15 janvier 2023 à 16:33:47 :

>> Le 15 janvier 2023 à 16:31:04 :

> >> Le 15 janvier 2023 à 16:28:26 :

> > >Soit X le palier que l'on veut optimiser (tous les X etages on lance la pasteque).

> > >

> > > Il faut 100/X essais pour que la pasteque se brise et ensuite X essais pour determiner le palier exacte.

> > >

> > > Donc on veut le minimum de 100/X + X

> > >

> > > C'est atteint en X=10

> > >

> > > On lance tous les 10 etages

> >

> > Pourquoi prendre un seuil constant ?

>

> Car les étages sont les mêmes (c'est "linéaire" si tu veux mais oui on pourrait prendre une autre stratégie et montrer que dans le pire des cas il y aura toujours plus du 20 essais alors qu'avec ma stratégie c'est 20 essais au maximum)

Non on ne pourrait pas car c'est faux

Et pourquoi ?

Si on avait autant de pasteques il suffirait de subdiviser en deux parts égales à chaque fois mais là ce n'est pas le cas.

Parce que la réponse est inférieure à 20 et se fait avec une incrémentation non constante

Désolé avec 10 c'est 19 le pire des cas et pas 20

Désolé la réponse optimale est aussi inférieure à 19

Ah ok je vois peut-être qu'il faut reduire l'incrementation petit à petit pour avoir une plus petite esperance n puis n-1 etc...

L'espérance que j'ai calculé est d'environ 13 avec le max à 19 mais il y a moins d'avoir un plus petit ecart type.

En faisant n puis n-1 puis n-2 etc... donc vers 13-14 je pense et redescendre de 1 a chaque fois

Le 15 janvier 2023 à 16:50:07 :
Voici un algorithme qui me semble pas trop risqué

Soit N le nombre d'étages qu'on explore
Au début N=33 (nombre d'etge total /3)
On lance à N
Si ça explose on lance de 1 à N jusqu'à ce que ça explose
Sinon on recommence la boucle avec N = (100+2N)/3

Ainsi dans le pire des cas on fait 33 occurrences de lancer de pastèque

Ma logique est donc qu'il faut explorer tiers par tiers. On teste à 33, si ça explose faut explorer les 33 étages un à un vu qu'il nous reste qu'une pastèque, si ça explose pas faut explorer les 67 étages restant en utilisant la même méthode. On va donc tester au premier tiers des 67 étages restant soit l'étage 55, si ça explose pas on teste l'étage 70 puis 80 puis 86 etc..

J'espère que je suis clair

Ahi j'suis HS j'ai bien fait d'abandonner les maths

Le 15 janvier 2023 à 16:53:51 :

Le 15 janvier 2023 à 16:50:07 :
Voici un algorithme qui me semble pas trop risqué

Soit N le nombre d'étages qu'on explore
Au début N=33 (nombre d'etge total /3)
On lance à N
Si ça explose on lance de 1 à N jusqu'à ce que ça explose
Sinon on recommence la boucle avec N = (100+2N)/3

Ainsi dans le pire des cas on fait 33 occurrences de lancer de pastèque

Ma logique est donc qu'il faut explorer tiers par tiers. On teste à 33, si ça explose faut explorer les 33 étages un à un vu qu'il nous reste qu'une pastèque, si ça explose pas faut explorer les 67 étages restant en utilisant la même méthode. On va donc tester au premier tiers des 67 étages restant soit l'étage 55, si ça explose pas on teste l'étage 70 puis 80 puis 86 etc..

J'espère que je suis clair

Ahi j'suis HS j'ai bien fait d'abandonner les maths

C'est pas grave si tu comprends pas, parce que c'est pas la bonne réponse.

Le 15 janvier 2023 à 15:58:15 :
Dichotomie
Tu commences à l'étage 50, si ça explose tu relances à l'étage 25, sinon tu lances à l'étage 75, etc.

Eh non les shills !
Tu commences à l'étage 14, si ça n'explose pas tu vas au 27, puis 39, puis 50, puis 60, 69, ... etc bref t'incrémentes le nombre d'étages de 14-k à chaque fois. Donc tu t'en sors en 15 lancers au pire du pire.

Oui ça doit être ça, dans mes souvenirs le résultat était autour de 13 mais c'est peut-être 15

Le 15 janvier 2023 à 16:56:04 :

Le 15 janvier 2023 à 16:53:51 :

Le 15 janvier 2023 à 16:50:07 :
Voici un algorithme qui me semble pas trop risqué

Soit N le nombre d'étages qu'on explore
Au début N=33 (nombre d'etge total /3)
On lance à N
Si ça explose on lance de 1 à N jusqu'à ce que ça explose
Sinon on recommence la boucle avec N = (100+2N)/3

Ainsi dans le pire des cas on fait 33 occurrences de lancer de pastèque

Ma logique est donc qu'il faut explorer tiers par tiers. On teste à 33, si ça explose faut explorer les 33 étages un à un vu qu'il nous reste qu'une pastèque, si ça explose pas faut explorer les 67 étages restant en utilisant la même méthode. On va donc tester au premier tiers des 67 étages restant soit l'étage 55, si ça explose pas on teste l'étage 70 puis 80 puis 86 etc..

J'espère que je suis clair

Ahi j'suis HS j'ai bien fait d'abandonner les maths

C'est pas grave si tu comprends pas, parce que c'est pas la bonne réponse.

Ah mais c'est mon propre message, j'ai juste vu qu'en comparaison des autres je suis hors sujets et que y'a plus optimal