[Index Jeux] Enigmes, suites logiques et autres casse-têtes !

Pour les gens qui ont simplement envie de discuter sans souhaiter faire passer d'information particulière.
Avatar du membre
Ixy
Prolifique
Messages : 4667
Enregistré le : jeudi 20 mars 2014 à 20:59
Localisation : 92

Re: Enigmes, suites logiques et autres casse-têtes !

Message par Ixy »

Oui mais la question est plutôt d'ordre mathématique :lol:
phi a écrit :Hmm, 62 pour 2 billes
27 pour 3 billes
20 pour 4 billes

"Partie supérieure"("hauteur"^(1/"nombre billes")-1_|) * "nombre billes" dans le cas général ?
Il faut que tu expliques ta formule, en tout cas c'est pas mal du tout :bravo:
Manichéenne a écrit :45 avec deux billes.
Aucune idée pour 3.
Bravo :bravo: C'est exactement ça !
Tu peux peut-être expliquer comment tu fais ça donnera des idées pour 3 billes (oui c'est un peu plus dur). A mon avis c'est pas très loin de l'idée de phi
Je n'ai pas de diagnostic /!\
Ce que tu as la force d'être, tu as aussi le droit de l'être - Max Stirner
Avatar du membre
phi
Prolifique
Messages : 1321
Enregistré le : vendredi 15 mars 2013 à 9:50

Re: Enigmes, suites logiques et autres casse-têtes !

Message par phi »

On va prendre l'exemple avoir 3 billes.

On détermine d'abord la valeur de la centaine de l'étage limite.
On lance une bille aux étages 101, 201, 301, 401, 501, 601, 701, 801, 901.

Ainsi si la bille casse à l'étage 101, ça veut dire que l'étage limite est avant. De 1 à 100.
Si elle ne casse pas mais qu'elle casse à l'étage 201, l'étage limite est entre 101 et 200.
...
Si elle ne casse pas à 901, ça veut dire que l'étage limite est entre 901 et 1000.

Supposons qu'on soit dans la situation entre 101 et 200.

On jette une bille aux étages 111, 121, 131, 141, 151, 161, 171, 181, 191.

Rebellotte, on arrive à déterminer un intervalle de dix étages en fonction de la casse.
Par exemple, entre 111 et 120.

On réitère pour trouver le chiffre des unités.

On a donc fait trois fois neuf lancers.
3 mars 2016, Dr L : "Je n'ai aucun doute sur le fait que vous soyez autiste"
22 juillet 2016, diag effectué. TSA-SDI \o/
Avatar du membre
Ixy
Prolifique
Messages : 4667
Enregistré le : jeudi 20 mars 2014 à 20:59
Localisation : 92

Re: Enigmes, suites logiques et autres casse-têtes !

Message par Ixy »

Oui Phi c'est une très bonne stratégie :bravo:

On peut faire un peu mieux car si on casse la bille dès le premier lancer, c'est-à-dire à 101, on a en quelque sorte gagné 8 lancers par rapport à si on avait cassé la bille à 901.


C'est ce que fait Manichéenne pour deux billes. Pour homogénéiser le nombre d'essais, je jette une bille à l'étage d, puis l'étage 2d-1, puis à l'étage 3d-2, etc.

Au final ça nous donne le résultat optimal pour deux billes càd 45 essais max.


Si vous faites une synthèse des 2 stratégies vous arriverez à la solution optimale pour 3 billes.
Je n'ai pas de diagnostic /!\
Ce que tu as la force d'être, tu as aussi le droit de l'être - Max Stirner
Avatar du membre
phi
Prolifique
Messages : 1321
Enregistré le : vendredi 15 mars 2013 à 9:50

Re: Enigmes, suites logiques et autres casse-têtes !

Message par phi »

Certes, mais bon, pour quelques poussières :mryellow:
3 mars 2016, Dr L : "Je n'ai aucun doute sur le fait que vous soyez autiste"
22 juillet 2016, diag effectué. TSA-SDI \o/
Avatar du membre
Ixy
Prolifique
Messages : 4667
Enregistré le : jeudi 20 mars 2014 à 20:59
Localisation : 92

Re: Enigmes, suites logiques et autres casse-têtes !

Message par Ixy »

On peut faire quasiment 30% meilleur :) Je donnerai le résultat optimal plus tard sauf si une personne veut s'y essayer avant
Je n'ai pas de diagnostic /!\
Ce que tu as la force d'être, tu as aussi le droit de l'être - Max Stirner
Avatar du membre
phi
Prolifique
Messages : 1321
Enregistré le : vendredi 15 mars 2013 à 9:50

Re: Enigmes, suites logiques et autres casse-têtes !

Message par phi »

Attends un peu, je vais faire une simulation.

Pas envie de réfléchir :lol:
3 mars 2016, Dr L : "Je n'ai aucun doute sur le fait que vous soyez autiste"
22 juillet 2016, diag effectué. TSA-SDI \o/
Avatar du membre
phi
Prolifique
Messages : 1321
Enregistré le : vendredi 15 mars 2013 à 9:50

Re: Enigmes, suites logiques et autres casse-têtes !

Message par phi »

19 ?
(fichu limite de 8 caractères)
3 mars 2016, Dr L : "Je n'ai aucun doute sur le fait que vous soyez autiste"
22 juillet 2016, diag effectué. TSA-SDI \o/
Avatar du membre
Ixy
Prolifique
Messages : 4667
Enregistré le : jeudi 20 mars 2014 à 20:59
Localisation : 92

Re: Enigmes, suites logiques et autres casse-têtes !

Message par Ixy »

Exact ! :D Je suis curieux de savoir comment tu t'y es pris pour la simulation
Je n'ai pas de diagnostic /!\
Ce que tu as la force d'être, tu as aussi le droit de l'être - Max Stirner
Avatar du membre
phi
Prolifique
Messages : 1321
Enregistré le : vendredi 15 mars 2013 à 9:50

Re: Enigmes, suites logiques et autres casse-têtes !

Message par phi »

J'ai appliqué directement ce que tu as dis.

Un code en bon vieux C.
Spoiler :  : 

Code : Tout sélectionner

#include <stdlib.h>
#include <stdio.h>


int hauteur_max(int nb_essais, int nb_billes)
{
	if (nb_billes == 0)
		return 0;
	if (nb_billes == 1)
		return nb_essais+1;
	if (nb_essais == 0)
		return 1;
	int j;
	int resultat = 0;
	for (j = 1; j <= nb_essais; j++)
		resultat += hauteur_max(nb_essais-j, nb_billes-1);
	resultat+=1;
	return resultat;
}

int main()
{
	int nb_essais = 1;
	while (hauteur_max(nb_essais,3) < 1000) 
	{
		nb_essais++;
	}
	printf("%d\n", nb_essais);
	return 0;
}
À mon avis, ça ne doit pas être compliqué de faire un algo en programmation dynamique au cas où il y a beaucoup de billes et beaucoup d'étages.

Mais donne ta solution, mon approche est peu élégante.
3 mars 2016, Dr L : "Je n'ai aucun doute sur le fait que vous soyez autiste"
22 juillet 2016, diag effectué. TSA-SDI \o/
Avatar du membre
Ixy
Prolifique
Messages : 4667
Enregistré le : jeudi 20 mars 2014 à 20:59
Localisation : 92

Re: Enigmes, suites logiques et autres casse-têtes !

Message par Ixy »

Sinon voici le raisonnement à faire :

Soit d le nombre d'essais minimal (pire cas)

Imaginons que ma première et deuxième billes se cassent dès le premier coup.
Il me reste d - 2 essais.
Donc je peux tester seulement les (d - 2) premiers étages. Avec le test de la deuxième bille ça fait d - 1 étages

Si la première bille casse mais pas la deuxième, je peux faire les (d - 2) étages suivants, puis les d - 3, etc. selon la fois où la deuxième bille casse.

Donc si la première bille casse, j'ai (d-1)(d)/2 étages que je peux tester au total en considérant tous les cas. (formule de Gauss, jusque ici c'est le raisonnement de Manichéenne)

Si la première bille se casse la deuxième fois, c'est la même chose mais j'ai le droit à un coup de moins. On remplace seulement d - 1 par d - 2.

Et ainsi de suite

La formule est donc de trouver le d minimal tel que

(d-1)(d)/2 + (d-2)(d-1)/2 + ... + 1*2/2 > 1 000 (pour couvrir tous les cas, en particulier si la bille casse au dernier étage)

Bon c'est une formule un peu moche, on peut vérifier que le d plus petit qui marche est 19, mais ceux qui ont fait un peu de mathématiques savent qu'on peut aussi minorer l'expression à gauche par une intégrale

(d)(d-1)/2 + (d-2)(d-1)/2 + ... + 1*2/2 > intégrale de 0 à d de x(x-1)/2 = 1/6 d^3 - 1/4 d^2

Pour d = 19 cette expression est égale à 1053, c'est bon !

EDIT : Joli :bravo: Je n'avais pas penser à la récursivité
Je n'ai pas de diagnostic /!\
Ce que tu as la force d'être, tu as aussi le droit de l'être - Max Stirner
Avatar du membre
freeshost
Intarissable
Messages : 37757
Enregistré le : lundi 15 juillet 2013 à 15:09
Localisation : CH

Re: Enigmes, suites logiques et autres casse-têtes !

Message par freeshost »

Bon, je n'ai pas trop le temps de réfléchir sur le forum en ce moment. Je dois partir dans trente minutes. Je continue de parcourir le forum. Je reviendrai ce soir (vers 21h00). :)

Intéressant. On pourrait même alors calculer le nombre de marches parcourues (mettons 20 marches par entre-deux-étages) sachant qu'il n'y a pas d'ascenseur. C'est sport ! :lol:
Pardon, humilité, humour, hasard, confiance, humanisme, partage, curiosité et diversité sont des gros piliers de la liberté et de la sérénité.

Diagnostiqué autiste en l'été 2014 :)
Avatar du membre
dpld
Prolifique
Messages : 802
Enregistré le : jeudi 31 juillet 2014 à 15:30

Re: Enigmes, suites logiques et autres casse-têtes !

Message par dpld »

je réitère ma question : quelle est la nature de la bille (caoutchouc, métal, verre...) la densité des différents matériaux implique une probabilité qui lors d'une chute à un même étage aura un résultat différent ? Non ?
Juste partir
Avatar du membre
Ixy
Prolifique
Messages : 4667
Enregistré le : jeudi 20 mars 2014 à 20:59
Localisation : 92

Re: Enigmes, suites logiques et autres casse-têtes !

Message par Ixy »

Freeshost, c'est une autre question celle de faire le moins de marches possibles :lol: Tu peux t'y atteler si tu le souhaites :bravo:
dpld a écrit :je réitère ma question : quelle est la nature de la bille (caoutchouc, métal, verre...) la densité des différents matériaux implique une probabilité qui lors d'une chute à un même étage aura un résultat différent ? Non ?
La question n'est qu'un prétexte, il s'agit d'un problème mathématique/de logique
Je n'ai pas de diagnostic /!\
Ce que tu as la force d'être, tu as aussi le droit de l'être - Max Stirner
Avatar du membre
dpld
Prolifique
Messages : 802
Enregistré le : jeudi 31 juillet 2014 à 15:30

Re: Enigmes, suites logiques et autres casse-têtes !

Message par dpld »

Certainement mais ce sont des choses (mathématiques et logiques) que je n'ai pas eu l'occasion d'étudier, ayant très peu fréquenté l'école. Cependant, lorsque cette question est posée, ce qui me vient à l'esprit est : la composition de la bille (bois, verre, métal, caoutchouc...) et une autre question (que je n'avais pas envisagée au départ) est la matière du sol à l'arrivée.... Maintenant, effectivement, je n'avais pas envisagé qu'il était possible de la faire passer par ailleurs que par la fenêtre :roll:
Ixy a écrit :Freeshost, c'est une autre question celle de faire le moins de marches possibles :lol: Tu peux t'y atteler si tu le souhaites :bravo:
dpld a écrit :je réitère ma question : quelle est la nature de la bille (caoutchouc, métal, verre...) la densité des différents matériaux implique une probabilité qui lors d'une chute à un même étage aura un résultat différent ? Non ?
La question n'est qu'un prétexte, il s'agit d'un problème mathématique/de logique
Juste partir
Avatar du membre
dpld
Prolifique
Messages : 802
Enregistré le : jeudi 31 juillet 2014 à 15:30

Re: Enigmes, suites logiques et autres casse-têtes !

Message par dpld »

Bon voilà il n'y a plus personne à cet étage.... Pauvre bille :(
Juste partir