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 - 28-10-2012 10:58:53

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

soustraire, addirionner.

Bonjour à tous.
C'est un problème que j'avais proposé il y a déja pas mal de temps sur un autre site et qui n'avait pas eu de réponses (pour tous: du coup on peut le remettre sur la table). Je n'ai pas tenté pour l'instant de retrouver la solution. J'espère que vous pourrez la trouver. 

Cet algorithme se déduit de la suite des nombres entiers successifs 1,2,3...
On ôte au résultat Ri donné l'entier successif suivant, sauf si R(i+1) <=0, auquel cas on fait une addition.
Le début donne:
Avec 1 on ajoute 2, car 1-2<=0 donc 1+2=3
avec 3 on ajoute 3 car 3-3<=0 donc 3+3=6
6-4=2
2+5=7
7-6=1
1+7=8
8+8=16
16-9=7
etc

Avec quel entier obtiendra t on le résultat 100 000 ?

  • |
  • Répondre

#0 Pub

 #2 - 28-10-2012 11:24:26

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

soustrzire, additionner.

Tu veux dire qu'au bout d'un moment avec ta suite, on arrive à 100 000, et il faut qu'on trouve le rang du terme ?

Ou bien tu veux dire qu'en considérant une autre suite, qui commence non pas à 1 mais à 5 par exemple, 5+6=11, 11-7=4, 4+8=12, etc... on va arriver à 100 000, et il faut trouver le premier terme de cette suite ?

 #3 - 28-10-2012 12:32:53

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

Soustraire, additionner

Bonjour smile

On peut remarquer qu'en commençant à 0 l'entier 3n-1 tombe pile sur son rang , je laisse le reste aux amateurs de calcul .

Vasimolo

 #4 - 28-10-2012 13:36:12

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

soustraire, additoonner.

Vasi a déja compris. Bon, c'est pas pour son niveau.
Titou, si tu veux aussi calculer le résultat à l'entier 100 000 tu peux, mais la question est: à quel entier obtient on 100 000 (si jamais on l'obtient) ?
Pour toi non plus ça ne devrait pas durer longtemps.

ça se fait sans l'ordi. bien sûr. 

Le problème est à classer dans les faciles, niveau Lycée voire Collège.

 #5 - 28-10-2012 14:41:57

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

soustraire, adsitionner.

Ok. J'ai compris.
[TeX]u_1=1, u_2=1+2=3[/TeX]
[TeX]u_3=3+3=6[/TeX]
[TeX]u_4=6-4=2, u_5=2+5=7[/TeX]
[TeX]u_6=7-6=1, u_7=1+7=8[/TeX]
[TeX]u_8=8+8=16[/TeX]
[TeX]u_9=16-9=7, u_{10}=7+10=17[/TeX]
[TeX]u_{11}=17-11=6, u_{12}=6+12=18[/TeX]
[TeX]u_{13}=18-13=5, u_{14}=5+14=19[/TeX]
...

Alors, on voit qu'en régime normal la suite des opérations sera -+-+-+, donc une sous-suite (1 terme sur 2) où ça monte de 1 en 1, et une autre sous-suite (1 terme sur 2) où ça descend de 1 en 1. Jusqu'à ce que la sous-suite décroissante doive atteindre 0, et à la place on a un doublement. Puis on reprend le régime normal -+-+-+, et ainsi de suite...

Il est facile de voir que s'il y a eu un doublement au rang [latex]n[/latex], alors le suivant aura lieu au rang [latex]3n-1[/latex].

On cherche le plus grand doublement inférieur à 100 000, donc de rang inférieur à 50 000.

On note [latex]d_n[/latex] le rang du [latex]n^{ème}[/latex] doublement.
[TeX]d_1=3, d_2=8, d_3=23, d_4=68, ..., d_{10}=49 208[/TeX]
Donc [latex]u_{49 208}=98 416[/latex] et donc [latex]u_{52 376}=100 000[/latex].

Remarque : ce n'est que le premier terme (parmi une infinité) qui vaut 100 000. Par exemple, [latex]u_{242 868}=100 000[/latex].

 #6 - 28-10-2012 18:13:59

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,010E+3

soustraire, additionnrr.

Il y a un moment ou ça diminue ou augmente de 1 tous les 2 coups avant de doubler.
On va donc à 7 auquel on rajoute 8 (x2) pour redescendre =23
22 + 46 = 68
67 + 136 = 203
...
49207 ==> 98416  manquent 1584x2 = 3168 coups pour atteindre 100000 depuis 49208

Soit 52376


100 000 est atteint pour 52376 ?

 #7 - 28-10-2012 18:40:44

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

Soustraire, additinner.

Sans surprise, 2 bonnes réponses.

 #8 - 28-10-2012 19:41:52

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2131

Soustriare, additionner.

C'est un peu long à écrire.
Soit u(n) la suite où l'algorithme prend la valeur 1.
On établit par récurrence que u(n) vérifie
u(0) =5
u(n+1) = 3u(n) +5.

u(n)= 5/2*(3^(n+1)-1)

A l'échelon N+2 à partir de ces valeurs, la suite fait un "saut" par doublement du pas pour une valeur égale à 2u(n)+16.
Entre deux valeurs de u(n), les termes alternent entre Pas et 1 en décroissance et entre Pas et 2*Pas-1 en valeur croissantes.

Partant de là toutes les valeurs s'expriment en fonction de n, avec par morceaux des plages de maximum strictement croissantes.

Pour l'application: Au point 52375, on trouve la valeur 100 000 pour la première fois.

J'attends la démo classe en deux phrases.


"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde

 #9 - 28-10-2012 22:16:10

gilles355
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 421

Soustraire, additionne.

Bonsoir,

je trouve qu'il y a une infinité de réponses, la première étant pour 52376.

Pour trouver ce résultat j'ai construit une suite arithmético-géométrique donnant les résultats égaux à 1 de la forme U(n+1) = 3 U(n) + 3, en passant par une suite auxiliaire V(n) = U(n) + 3/2 j'en ai déduit:

U(n) = 5/2 * 3^n - 3/2 donnant donc tous les entiers qui donnent 1 comme résultat.

A partir de là j'ai pu voir pour quel entier apparaît le premier 100 000.

Je ne développe pas tout vu qu'apparemment la solution est plus simple et surtout plus complète.

 #10 - 29-10-2012 11:07:50

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Soustraire, additionne.

Je trouve 52376.

Pourquoi ne pas proposer de case réponse???

 #11 - 29-10-2012 12:25:06

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

Soustraire, addittionner.

C'est bon Rivas.
Titou me faisait remarquer que 100 000 n'apparaissait pas qu'une seule fois. A t'il raison et si oui combien peut on en trouver ?

 #12 - 29-10-2012 21:17:46

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2131

Soustraire, additioner.

Niveau Collège hmm

Tout est là.
Au premier terme qui diffère.

http://oeis.org/search?q=3%2C6%2C2%2C7% … ;go=Search

This is a concatenation S_0, S_1, S_2, ... where S_i = [b_0, b_1, ..., b_{k-1}], k=5*3^i, with b_0 = 1, b_{2j} = k+j, b_{2j+1} = (k+1)/2-j.

E.g. S_0 = [1, 3, 6, 2, 7].

Benoit Cloitre écrit:

For any m>=1,
for k such that 5*3^k+3>12m, a((5*3^k+3-12*m)/6)= m.
For example, for k>=1, a((5*3^k-9)/6) = 1.

On retrouvera donc 100000 une infinité de fois.

Et hop !


"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde

 #13 - 30-10-2012 00:03:55

looozer
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 697
Lieu: Belgique

Soustraire, additinner.

Appelons f cette fonction.
Pour x=1 ; 6 ; 21 ; 67 ; 201 ; 606 ; 1821 ; ... (chaque valeur vaut le triple de la précédente augmentée de 1), f(x+1)=2*f(x) et f(x)=x+2

Je choisis x=49206 (10ème élément de la suite dont je viens de parler et dernier à être inférieur à 100 000)

J'obtiens donc:

f(49206) = 49208
f(49207) = 98416

A partir de là f(x) augmente d'une unité chaque fois que x augmente de 2 unités.

Comme il me reste 1584 unités pour arriver à 100 000, j'augmente x du double, soit 3168: 49207 + 3168 = 52375.

Très empirique mais j'ai pas mieux big_smile

 #14 - 31-10-2012 09:44:32

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Soustraire, addittionner.

@nodgim.
100000 va apparaitre une infinité de fois.

En effet, on voit bien que la suite des nombres peut être divisée en 2 sous-suites de rangs pairs/impairs et que l'une des deux décroit de 1 en 1 jusquà 1 puis à la suite des 2 additions successives, repart d'un nombre de plus en plus grand: 1+N+(N+1) où N est le rang auquel se produisent les additions successives. Puis la sous-suite decroit à nouveau de 1 en 1 jusqu'à 1 et passe donc par 100000. Le nombre qu'on a donné est la premier occurence de ce mécanisme.

 #15 - 31-10-2012 10:35:26

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3222
Lieu: Luxembourg

Soustraire,, additionner.

Les maximas locaux successifs sont obtenus pour les entiers du type:
(15/2).3^n-(3/2) et donneront une valeur de: (15/2).3^n+(1/2).
Le maxima local le plus proche de 100 000 est donc 147 623, de part
et d'autre duquel les valeurs diminuent avec une pente de (1/2).
On obtient donc 100 000 pour les deux valeurs: 52 375 et 242 867.

 #16 - 01-11-2012 10:04:35

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1494
Lieu: Coutiches

soustraire, additiinner.

@Papiauche : Niveau collège ? roll

Si c'est vrai ça doit faire longtemps que tu en es sorti, et le niveau doit avoir bien baissé... sad

 #17 - 02-11-2012 10:22:56

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

sousyraire, additionner.

Tout le monde a à peu près trouvé la réponse de la question originale, mais personne n'a vraiment décrit l'ensemble complet des solutions, l'ensemble des entiers tel que le résultat est 100 000.
J'attends bien sûr une fonction.

 #18 - 02-11-2012 12:43:54

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3222
Lieu: Luxembourg

sousttaire, additionner.

@nodgim
Premier terme (calculé spécifiquement): 52375.
Termes suivants: [5 x 3^(N+10) - 400001] / 2, avec N entier supérieur ou égal à 1.
En fonction du début du comptage, il faut ajouter 1 aux valeurs précédentes.
Je propose de fournir rapidement une formule pour toute valeur (dont 100 000) qui est presqu'au point.
A+

 #19 - 02-11-2012 13:32:29

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

Soustraire, additioner.

Attention, Francky, la 1ère valeur 100 000 est atteinte à 52376.
Tu n'es pas loin pour la formule générale qui donnera tous les résultats 100 000. Reste juste à affiner.

 #20 - 02-11-2012 13:46:45

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3222
Lieu: Luxembourg

soustrzire, additionner.

@nodgim
Comme j'ai dit dans mon post précédent (mais l'as tu lu ?), on trouve 52375 ou 52376 en fonction de là où on a commencé à compter (mais ce n'est qu'une convention).
Visiblement, 5 personnes (titoufred, gwen27, gilles355, rivas et toi) ont compté à partir de f(0)=1 et 3 autres personnes (papiauche, looozer et moi) à partir de f(1)=1+2=3.
Convenons alors de compter comme la majorité: c'est un principe souvent appliqué en démocratie (même si la minorité n'a pas toujours tort).
lol

 #21 - 02-11-2012 14:11:41

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Soustraire, aditionner.

Après [latex]52376[/latex], les prochaines apparitions de 100 000 sont données par la formule
[TeX]\frac{3^n\times5-399999}2[/latex] pour [latex]n \geq 11[/TeX]

 #22 - 02-11-2012 17:26:18

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

Soustraire, additionnr.

Francky,
Si tu commences à 0, la suite donne:0,1,3,6....face aux entiers:0,1,2,3..
Si tu commences à 1, la suite donne 1,3,6,...faces aux entiers 1,2,3,..
Il n'y a donc pas de différence selon le départ, la question étant bien pour quel entier....Formalisé, c'est f(n) qui est demandé.
A mon sens, et sauf si une nuance m'a échappé, il ne semble pas y avoir d'ambigüité dans l'énoncé.
Mais bon, ça reste de la pinaillerie, j'en conviens.

 #23 - 02-11-2012 17:30:33

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

Soustraire, addditionner.

En revanche, je suis d'accord avec toi, Francky, pour la formule générale d'apparition du résultat 100 000 !

 #24 - 02-11-2012 17:39:29

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3222
Lieu: Luxembourg

soustraire, additiinner.

Voici donc la formule générale promise (aux erreurs de calcul près).
On appelle a l’entier avec lequel on veut obtenir le résultat (soit 100 000 dans le cas particulier).
Je calcule d’abord quelques valeurs.
Le rang r est le r-ième maximum local: r = ent { [ log(2a-3) - log15 ] / log3 + 3 }
lequel maximum local a pour valeur: v = 5 x [ 3^(r-1) - 1 ] / 2
Un écart e permettra de déterminer la première valeur spécifique:
e = 2 x ( v + 1 – a ), ou encore: e = 5 x 3^(r-1) + 1 - 2a
La première valeur spécifique (c'est-à-dire non courante) vs sera:
- si e est négatif, inexistante,
- si e est nul, confondue avec la première valeur courante,
- si e est positif, de: vs = v - e, ou encore : vs = 2a - 3/2 - 5 x 3^(r-1) / 2
Les valeurs courantes seront de la forme: vn = 5 x [ 3^(n-1) - 1 ] / 2 + e, ou encore : vn = 5 x [ 3^(n-1) / 2 + 3^(r-1)] + 1/2 - 2a, avec n supérieur ou égal à r.

 

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 42ème, en quelle position êtes-vous ?

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