Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 02-11-2011 02:58:43

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

a vous de payer - syite (1/3)

Suite a cette énigme, je vous propose une variante:

2 mathematiciens (A et B) jouent au probleme suivant:
A choisit mentalement un nombre X dans l'ensembre {1,2,....,27200}.
B qui cherche à découvrir X, peut choisir un sous-ensemble E de  {1,2,....,27200} et demander si X appartient à E ou non.
- Si la réponse de A est Oui, B doit payer 3 euros.
- Si la réponse de A est Non, B doit payer 1 euro.

Quel est la somme minimale nécessaire que B doit posséder au départ pour être assuré de trouver X ?
Et bien sur, quelles sont donc les étapes?


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
  • |
  • Répondre

#0 Pub

 #2 - 02-11-2011 10:31:08

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

A vous de payer - suite (1/3

Je dirais 28 euros (pour 27201 pareil, pour 27202 là il en faudrait 29)
Ca reprend un peu le principe avec Fibonacci sauf que là c'est F'0=F'1=F'2=1; F'(n+1) = F'(n) + F'(n-2)

La somme des termes de cette suite s'exprime aussi sous la forme d'un des termes de la suite: Somme(F'(i); i=0..n) = F'(n+3)-1
Démo par récurrence: F'(0) = 1 = F'(3)-1
Si Somme(F'(i); i=0..n) = F'(n+3)-1
alors Somme(F'(i); i=0..n+1) = F'(n+3)-1+F'(n+1) = F'(n+4)-1

Du coup, si F'(n) < N <= F'(n+1); alors il faut un minimum de n+1 euros pour trouver N. Application ici: F'(27) = 18560; F'(28) = 27201; il faut 28 euros pour N compris entre 18561 et 27201

 #3 - 02-11-2011 14:18:15

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

a vous de payer - suire (1/3)

Le plus grand ensemble que l'on peut constituer pour jouer en n pièces n'est plus donné par la suite de fibonacci mais la suite :

u(0)=1
u(1)=1
u(2)=1
u(n) = u(n-1)+u(n-3) pour n >= 3

Il faut 28 pièces.

En python :

Code:

def u_aux(n, u2, u1, u0):
    if n == 2:
        return u2
    else:
        return u_aux(n-1, u2+u0, u2, u1)

def u(n):
    if n <= 2:
        return 1
    else:
        return u_aux(n, 1, 1, 1)

> [u(i) for i in range(28, 0, -1)]

[27201, 18560, 12664, 8641, 5896, 4023, 2745, 1873, 1278, 872, 595, 406, 277, 189, 129, 88, 60, 41, 28, 19, 13, 9, 6, 4, 3, 2, 1, 1]

 #4 - 02-11-2011 15:16:46

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

A vous de payyer - suite (1/3)

Pour les étapes: j'ai un ensemble E de cardinal C, avec N+1 euros en poche tel que F'(N)<C<=F'(N+1)

Je découpe mon ensemble E en 2 sous ensembles E1 et E2, de cardinaux respectifs C1=F'(N-2) et C2 = C-F'(N-2)
Je pose ma question "la réponse est-elle dans E1?"
- oui, ça me coûte 3 euros, et je me retrouve avec le même problème pour un ensemble de cardinal de C1
=> il me faut en théorie N-2 euros alors; plus les 3 ça nous fait N+1
- non, ça me coûte 1 euro, et je me retrouve avec le même problème pour un ensemble de cardinal de C2 = C-F'(N-2) <= F'(N+1)-F'(N-2) = F'(N)
=> il me faut donc en théorie N euros alors; plus le 1 ça nous fait N+1

 #5 - 02-11-2011 18:12:00

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

A vous de payer - uite (1/3)

Bonnes reponses de Scarta et Nicouj.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #6 - 02-11-2011 22:56:18

Bamby2
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 152

A vous de payer - suie (1/3)

j'ai une solution avec 28 pièces, par contre, l'arbre est ma foi assez grand smile

la première décision est de coupé en 8440 et 18560 .
en demandant évidement 8440 (qui me coûtera 25 à résoudre)
et si c'est dans 18560, ça me coûtera 27.
ensuite reste a decider pour ces deux cas la ... mais dieux que ca va etre long de tout ecrire.

ai-je bon ? dois je en dire plus ?

P.S. du coup j'avais coder le truc, mais pour la 2nde énigme, ça ne marche plus, y a vraiment trop de zéro smile
je cherche une autre voie.

 #7 - 03-11-2011 19:00:45

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

A vous de payer - site (1/3)

Avec 5 €, on peut trouver le nombre mystère parmi 4.
Avec 6 €, on peut trouver le nombre mystère parmi 6.
Avec 7 €, on peut trouver le nombre mystère parmi 9.
et ensuite on a un=u(n-1)+u(n-3) soit
Avec 8 €, on peut trouver le nombre mystère parmi 9+4=13
Avec 9 €, on peut trouver le nombre mystère parmi 13+6=19
Avec 28 €, on peut trouver le nombre mystère parmi 27201.

Sauf erreur de calcul.

 #8 - 03-11-2011 20:11:57

nicolas647
Passionné de Prise2Tete
Enigmes résolues : 24
Messages : 96

A vous de payer - suite 1/3)

La réponse se trouve dans la suite :

A000930         a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).

une suite du même type que la suite de Fibonacci.

Bon, maintenant je vais essayer d'expliquer pourquoi :

On appelle N le nombre d'élément de E et f la fonction qui associe à N la somme minimale dont B a besoin pour être sûr de pouvoir deviner X.
Prenons une somme arbitraire n. Prenons [latex]N_1[/latex] tel que [latex]f(N_1)=n-3[/latex], [latex]N_2[/latex] tel que [latex]f(N_2)=n-1[/latex]

On sait qu'avec n euros, on est sûr de pouvoir deviner pour un ensemble de taille [latex]N=N_1+N_2[/latex]

Voyons maintenant si on peut deviner avec moins d'argent. Il faudrait trouver une décomposition [latex]N=N_3+N_4[/latex] telle que [latex]f(N_3)<f(N_1)[/latex] et [latex]f(N_4)<f(N_2)[/latex].
f étant une fonction croissante, il faudrait donc que [latex]N_3<N_1[/latex] et [latex]N_4<N_2[/latex], ce qui est impossible.

On peut donc déduire que f(N)=n.

Si on a pris [latex]N_1[/latex] et [latex]N_2[/latex] les plus grands possibles tels que [latex]f(N_1)=n-3[/latex] et [latex]f(N_2)=n-1[/latex], on peut en déduire que N est le plus grand possible tel que f(N)=n.

Occupons-nous maintenant de la fonction [latex]f^{-1}[/latex], réciproque de f, qui associe à un entier n son plus grand antécédent par f.
On a vu précédemment que si [latex]f^{-1}(n-3)[/latex] et [latex]f^{-1}(n-1)[/latex] sont définis, alors [latex]f^{-1}(n)=f^{-1}(n-3)+f^{-1}(n-1)[/latex].
C'est une propriété qu'on retrouve dans la fameuse suite A000930.

Il ne suffit plus maintenant que de trouver les résultats de f pour les petites valeurs en essayant toutes les combinaisons, d'en sortir 3 entiers consécutifs pour lesquels [latex]f^{-1}[/latex] est défini, et tous les résultats de la fonction [latex]f^{-1}[/latex] pourront être obtenus à partir de la suite A000930 :
[TeX]f^{-1}(1)[/latex] n'est pas défini.
[latex]f^{-1}(2)[/latex] n'est pas défini.
[latex]f^{-1}(3)=2[/TeX]
[TeX]f^{-1}(4)=3[/TeX]
[TeX]f^{-1}(5)=4[/TeX]
A partir de là on en déduit que [latex]f^{-1}(6)=f^{-1}(5)+f^{-1}(3)=4+2=6[/latex] et ainsi de suite. On s'aperçoit que [latex]f^{-1}(n)[/latex] est égal au terme numéro n de la suite A000930.

Pour N=27200, on a [latex]f^{-1}(27)=18560[/latex] et [latex]f^{-1}(28)=27201[/latex].
La réponse est donc f(27200)=28.

 #9 - 04-11-2011 01:01:47

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

A vous de payer - suite (13/)

Bonnes réponses de tout le monde pour l'instant.

Félicitations a ceux qui ont trouvé.

I fallait bien trouver 28.

Pour une explication, regardez les réponses de Scarta ou Nicolas.

PS: j'avais mis 27200 au lieu de 27201, parce que 27201 était trouvable trop facilement sur OEIS. Voila.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete