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 - 27-01-2011 12:35:58

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pi pi ! (la sute)

Soit [latex]n [/latex] un entier naturel [latex]>0[/latex], montrez qu'il existe DEUX séquences de [latex]n [/latex] chiffres [latex](c_1,\ldots,c_n)[/latex] et [latex](d_1,\ldots,d_n)[/latex] qui apparaissent telles quelles, infiniment souvent dans le développement décimal de [latex]\pi^2[/latex]. 
NB : pas besoin d'être très fort en maths. Mais voir d'abord cette énigme.

Question subsidiaire : peut-on appliquer le même type de raisonnement pour prouver qu'il existe TROIS de ces séquences ?

  • |
  • Répondre

#0 Pub

 #2 - 27-01-2011 21:14:22

Tromaril
Habitué de Prise2Tete
Enigmes résolues : 20
Messages : 45

pi pi ! (ma suite)

Si ce n'était pas le cas, tous les [latex]c_i [/latex]seraient égaux et [latex]\pi^2[/latex] serait rationnel :



Supposons que [latex](c_1 ... c_n)[/latex] soit la seule séquence à se répéter infiniment et notons [latex]a_j[/latex] la jieme décimale de [latex]\pi^2[/latex].
Il existe une position K à partir de la quelle seule la suite des [latex]c_i[/latex] se répète.
Soit [latex]h\geq k[/latex] tel que [latex]a_h,a_{h+1},...,a_{h+n-1}=(c_1 ... c_n)[/latex]
alors [latex]a_{h+1},a_{h+2},...,a_{h+n}=(c_1 ... c_n)[/latex]
donc [latex]c_2=c_1[/latex] et par propagation [latex]\forall i, c_i=c_1[/latex]



On peut présenter les choses autrement :
Soit [latex](c_1 ... c_n)[/latex] une séquence qui se répète indéfiniment (on sait qu'elle existe),
si les [latex]c_i[/latex] sont tous égaux 2 à 2 alors il y a forcément une autre séquence qui se répète sinon [latex]\pi^2[/latex] est rationnel
Sinon, il existe une infinité de séquences de la forme [latex](c_2, ..., c_n, d)[/latex] où [latex]0\leq d \leq 9[/latex] et parmi ces 10 types de séquences, il y en a forcément une qui se répète indéfiniment (et qui est forcément différente de [latex](c_1 ... c_n)[/latex]).

 #3 - 27-01-2011 21:49:10

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pi ppi ! (la suite)

Déjà une bonne réponse de Tromaril smile pour la peine, j'ai ajouté une question subsidiaire...

 #4 - 27-01-2011 23:50:26

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

pi pi ! (la suitz)

Une idée me traverse l'esprit.
Elle me semble correcte de prime abord et je suis sûr que les matheux ici pourront la confirmer ou l'infirmer.

Si on considère le nouveau nombre obtenu en "supprimant" les séquences (c1,...cn) de pi^2, ce nombre a lui aussi un nombre infini de décimales (sinon à partir d'un certain rang pi^2 aurait été formé des séquences successives sans chiffres entre et aurait donc été rationnel).
Appelons r ce nouveau nombre. r ne peut être rationnel sinon pi^2 l'aurait été aussi (r aurait été périodique et la façon d'intercaler les séquence aussi: nombre fini de possibilités).

On peut donc appliquer le même raisonnement à r et trouver des séquences (d1, ...,dn) ce qui conclut.

J'espère que ce n'est pas trop confus.

Du coup en itérant le processus, on peut aussi l'appliquer à 3 suites ou même à plus...

 #5 - 28-01-2011 00:40:13

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

iP pi ! (la suite)

On suppose acquis le résultat démontré dans l'énigme précédente.
Pour N donné, on a une première séquence répétée indéfiniment
Supposons qu'il n'y en ait qu'une seule. Autrement dit, toutes les autres séquences sont présentes un nombre fini de fois, et du coup au delà d'un certain nombre de décimales, N sera uniquement composé de notre séquence. Autrement dit, au delà d'un certain nombre de décimales, on aurait un irrationnel périodique, ce qui est absurde.
Conclusion: il y a forcément au moins 2 séquences indéfiniment répétées.

Suivant cette logique, en aurait-on trois? Eh bien, pas nécessairement !
En effet, avec 2 séquences A et B, il est tout à fait possible d'obtenir un développement non périodique. Par exemple:
A B AA BB AAA BBB AAAA BBBB ...

 #6 - 28-01-2011 02:48:25

alnilam
Habitué de Prise2Tete
Enigmes résolues : 49
Messages : 21

pi pi ! (ka suite)

Si ton énoncé est juste et que je l'ai bien compris (mais j'ai des doutes vu ma réponse...), il suffit de prendre n = 1.

Pi est un nombre irrationnel, donc il a un nombre infini de décimales, et ça ne peut pas être la même décimale à l'infini, sinon il ne serait pas transcendant.

Pour 3 séquences, c'est peut-être pas rigoureux comme démonstration, mais à mon avis les 10 chiffres se retrouvent infiniment dans la partie décimale de pi carré, sinon les mathématiciens auraient crié à la découverte du siècle depuis bien longtemps smile


Edit : Le lien de l'énigme vers laquelle ton énoncé renvoie ne fonctionne pas, ce qui explique peut être que je l'ai mal interprété.

 #7 - 28-01-2011 09:22:01

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

pi pi ! (lz suite)

@scarta : tutto bene !

@alnilam : euh non, il faut que ça marche pour n'importe quel n... d'autre part il s'agit de prouver (même pour n=1) qu'il existe au moins une séquence de longueur n qui se répète à l'infini. Enfin, quant à savoir si les 10 chiffres se retrouvent indéfiniment dans [latex]\pi[/latex] comme je l'ai dit plus haut, ça reste un mystère encore aujourd'hui. J'ai corrigé le lien, merci.

@rivas : je crois que ça marche pas car on supprime les (c1,...,cn) et
- soit on les remplace par des zéros mais en ce cas, une des deux séquences qui se répètent est (0,...,0) et on n'a pas avancé
- soit on les supprime vraiment mais on ne peut plus en conclure que le nombre obtenu est irrationnel, en effet 0,10100100010000100000... est irrationnel et pourtant si je supprime les 0 j'obtiens un nombre rationnel...

 #8 - 28-01-2011 09:27:50

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

pi pi ! (ma suite)

@gasole: en effet smile Par contre si le nouveau nombre est rationnel, on peut trouver une séquence de longeur n qui se répète (quitte à prendre plusieurs période et une fraction de période). Mais même si ça marche, ce n'est peut-être pas le plus élégant.

 #9 - 28-01-2011 10:12:54

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pi pi ! (la suitte)

@scarta : autant pour moi ton exemple comporte plus de deux séquences distinctes, regarde mieux (n'oublie pas les possibilités d'overlapping). En fait ça marche aussi pour 3 séquences... jusqu'à combien ça marche ?

 #10 - 28-01-2011 17:05:41

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

Pi pi ! (lla suite)

En effet, on peut aller plus loin que 2 séquences, mais uniquement pour N > 1. C'est pour ça que je n'ai pas traité de ce cas.
Supposons N > 1. Dans ce cas, A et B se répètent indéfiniment, autrement dit, au verra les séquences de 2n chiffres AB et BA se répéter indéfiniment elles aussi.
On considère la séquence ABA. Toute sous-séquences de N chiffres est soit A, soit B, soit à cheval sur AB, soit à cheval sur BA. Chacune d'elles apparaît donc un nombre infini de fois. Cependant, il n'y en a pas 2n+1 différentes, en effet certaines peuvent être similaires (par exemple, on considère 001 et 100, dans 001100001 on ne trouve que 5 séquences différentes et pas 7).
Cependant, comme A et B sont distinctes, on peut trouver au moins une fin de A et un début de B qui nous donne une nouvelle séquence et pareil une fin de B et un début de A qui nous en donne une autre
-si tous les An valent a et tous les Bn valent b, alors a <> b; donc toute séquence à cheval marche.
-si tous les An valent a, et les Bn ne sont pas tous égaux, alors il existe un m tel que Bm soit différent de a. Toutes les séquences à cheval qui contiennent Bm sont donc distinctes.
-enfin, si les An ne sont pas tous égaux et pareil pour les Bn, alors il existe un x tel que Ax <> A1. Toute les séquences qui sont à cheval sur BA et qui contiennent Ax sont donc distinctes. Pareil, il existe un y tel que Ay<>An, toutes les séquences à cheval sur AB qui contiennent Ay sont donc distinctes aussi.

 #11 - 28-01-2011 18:14:26

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Pi pi ! (la suit)e

Ah, j'ai l'impression que j'ai eu la même idée que rivas, qui est de supprimer toutes les occurrences de la première séquence [latex](c_1,c_2,...,c_n)[/latex], donc on sait qu'elle existe depuis cette énigme. La réponse de gasole me fait penser que ce n'est pas la bonne méthode smile
Dommage, car si on était sûr que le nouveau réel obtenu était bien irrationnel, il suffirait de recommencer pour trouver une autre séquence ...

EDIT
Supposons qu'il n'existe qu'une seule séquence, notée [latex](c_1,...,c_n)[/latex] qui se répète indéfiniment dans le développement de notre réel irrationnel r (généralisation aux irrationnels).
Alors les autres sont présentes en nombre fini.
Ce qui signifie qu'à partir d'un certain rang dans les décimales de r, on ne trouve plus que la séquence [latex](c_1,...,c_n)[/latex]. C'est impossible si r n'est pas rationnel.
Ma démo n'est pas très précise, mais je pense avoir saisi le sens.

Je pense qu'on peut généraliser à : il existe une infinité de séquences qui se répètent indéfiniment ?

 #12 - 28-01-2011 19:06:07

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pi pi ! (la usite)

Comme tu dis Looping, dommage... mais il y a peut être quelque chose à creuser, pas pour moi, je suis nul en maths.

 #13 - 30-01-2011 22:27:16

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pi pi ! (la suit)e

Bravo à Looping, Scarta et Tromaril pour leurs démonstrations. Et merci à Scarta pour être allé au-delà.


Pour l'existence d'une 2ème suite (la première ayant été établie ici), l'argument de Looping me sied parfaitement, c'est le plus simple : si une seule séquence [latex](c_1,\ldots,c_n)[/latex] se répétait indéfiniment (les autres étant en nombre fini [latex](10^n-1)[/latex] précisément) au-delà d'un certain rang les décimales seraient sur toute zone de [latex]2n [/latex] chiffres: [latex](c_1,\ldots,c_n,c_1,\ldots,c_n)[/latex], nous aurions donc un rationnel de période [latex]c_1,\ldots,c_n[/latex], or [latex]\pi^2[/latex] est irrationnel (sinon [latex]\pi[/latex] serait algébrique ce qu'il n'est pas puisqu'il est transcendant).
------------------------------------------------------------------------------------------------------------------
                        De existentia tertiae sequentiae.

Supposons [latex]n\geq 2[/latex]. S'il n'y en a que 2 distinctes, disons [latex]A =a_1\ldots a_n[/latex] et [latex] B=b_1\ldots b_n[/latex], notons [latex]\alpha = S_1S_2...S_k...[/latex] la suite des séquences de [latex]n [/latex] chiffres du développement décimal de [latex]\pi^2[/latex] en n'oubliant pas que les [latex]n-1[/latex] premiers caractères de [latex]S_{i+1}[/latex] sont identiques aux [latex]n-1[/latex] derniers de [latex]S_i[/latex]. La suite de chiffres se retrouve en prenant le premier de [latex]S_1[/latex], le premier de [latex]S_2[/latex], ...

Lemme 1: on ne trouve jamais [latex]AA[/latex] dans [latex]\alpha[/latex]. Sinon, [latex]A[/latex] serait constitué d'éléments identiques : on aurait [latex]A=a_1\ldots a_1[/latex] et comme on trouve forcément [latex]AB[/latex] dans [latex]\alpha[/latex], on aurait [latex]B=\fbox{a_1\ldots a_1\fbox{b_n}}[/latex] avec [latex]b_n\neq a_1[/latex] (car [latex]A\neq B[/latex]), et donc aucune possibilité de poursuivre sans faire apparaître une nouvelle séquence.
Corollaire : on ne trouve jamais [latex]BB[/latex] non plus.

Donc [latex]\alpha=ABABA....ABAB....[/latex] et donc [latex]\alpha=a_1 b_1 a_1 b_1...a_1b_1...[/latex] et serait rationnel, ce qui n'est pas le cas.

Quod erat demonstrandum.

PS : on y arrive aussi pour 4, après, je ne sais plus...

 #14 - 30-01-2011 22:37:42

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

pi pi ! (la duite)

En fait, je repensais à "Au moins 3", qui est faux (désolé), en tout cas pour N impair
Supposons que A = ababababa...baba et B=bababababab...abab
Il est impossible d'extraire de AB ou de BA une autre séquence distincte de A et B

Et toc !

 #15 - 30-01-2011 23:10:21

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

Pi pi ! (la suiet)

Je ne suis pas tout à fait d'accord avec les démonstrations données.
Elles se basent toutes sur le fait que s'il y en a qu'une le nombre est rationnel parce que la même se répète.
Il pourrait n'y avoir qu'une séquence qui se répète avec un écart de plus en plus long entre chacune des occurences de cette séquence et que le remplissage entre les séquences est toujours différent.
Je veux dire, la conclusion est vraie mais la façon de conclure dans les démonstrations ne me convainc pas totalement.
Il faudrait prouver que dans le cas, le remplissage est lui-même composé d'une séquence qui se répète.

 #16 - 30-01-2011 23:23:56

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

po pi ! (la suite)

Des écarts remplis de quoi Rivas ? Ben de la séquence qui se répète non ? Y a PAS de trous, d'où la rationnalité...
En tout cas, j'espère avoir bouché les trous.

 #17 - 31-01-2011 00:03:49

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

oi pi ! (la suite)

Au maximum, n+1 séquences obligatoires :

Preuve avec 2 chiffres seulement :
Séquences =
s1 = (a, a, ...,a, a, a)
s2 = (a, a, ...,a, a, b)
s3 = (a, a, ...,a, b, a)
s4 = (a, a, ...,b, a, a)
...
s(n) = (a, b, ...,a, a ,a)
s(n+1) = (b, a, ...,a, a, a)

Ensuite on peut s'amuser à accumuler les s1 en paquets de taille quelconque en séparant les paquets par la série s2,...s(n+1) qui permet de retomber sur s1 pour construire un irrationnel.

 #18 - 31-01-2011 01:01:59

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

pi pi ! (la suote)

gasole a écrit:

Des écarts remplis de quoi Rivas ? Ben de la séquence qui se répète non ? Y a PAS de trous, d'où la rationnalité...
En tout cas, j'espère avoir bouché les trous.

Des écarts remplis des décimales de pi par exemple... Dans ce cas et qu'on on l'a prouvé une autre séquence se répète. La conclusion est correcte à mon avis mais la façon d'y arriver m'interroge...

D'autre part il me semble avoir compris d'une démonstration que la séquence (c2,...cn, cn+1) était considéré comme réponse. En effet soit (c1,cn) se répète et donc r est rationnel (exclu) ou pour le chifre qui suit chaque séquence, il ne peut y avoir que 10 possibilités, on retrouve donc forcément l'un des chiffres répété infinement, ce qui est vrai.
Mais je pense que l'esprit de l'énoncé est d'avoir une 2nde séquence distincte ou disjointe, non?

 #19 - 31-01-2011 01:17:48

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pi p i! (la suite)

Des écarts remplis des décimales de pi par exemple...

Ben non, par hypothèse, seule une (ou deux) séquences de n chiffres survit au-delà d'un certain rang...
Je pense que tu as oublié que nos séquences peuvent (et doivent) se chevaucher...

Prenons l'exemple de séquences de longueur 2. S'il n'y a que 2 séquences, disons 00 et 01, il y en aura forcément une 3ème :
car on va trouver (1).....[latex]\underline{0}\underline{\overline{0}}\overline{1}x[/latex].... : soit x vaut 1 et la séquence 11 est nouvelle, soit x vaut 0 et c'est la séquence 10 qui est nouvelle.

(1) : sinon on a que 00000 et ça donne un rationnel, 10 toute seule n'étant pas possible car ne peut se chevaucher avec elle-même.

 #20 - 31-01-2011 09:44:39

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

Pi pi ! (la suite

Salut gasole,

Je suis un peu confus par ta dernière réponse. Je n'ai pas vu dans les hypothèses que les 2 suites devaient ni même pouvaient se chevaucher.
De plus en autorisant cela, la réponse devient tout à fait triviale.
Il suffit de construire une suite de longueur n+1 avec la méthode du première exercice et la considérer comme 2 suites de longueur n se chevauchant: (c1...cn) et (c2...cn+1).

Il me semblait donc que le but était de prouver qu'il existe des suites disjointes, ce qui à mon avis est faisable en supprimant des décimales la première suite: si le nombre restant est rationnel, il y forcément une période (voire des 0), sinon la méthode du premier exercice s'applique encore ce qui donne une seconde suite...

Est-ce que je rate quelque chose dans ce résumé?

 #21 - 31-01-2011 10:16:42

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pi pi ! (la suie)

Euh on cherche des séquences se répétant dans le développement décimal (DD), qu'elles se chevauchent ou non.

C'est si tu te restreins à des séquences non chevauchantes que c'est immédiat : une seule séquence peut être prouvée indéfiniment répétée, car dès n=2, on peut construire des structures du genre :

12 112 1112 11112 111112 1111112 ... qui est le DD d'un irrationnel et ne contient qu'une seule séquence infiniment souvent (dans le sens où tu l'entends, les deux autres chevauchant la première). 11 chevauche 12 et est chevauchée par 21.
Pourtant j'aurais tendance à dire que dans cette suite, il y a 3 séquences de 2 chiffres se répétant infiniment souvent.

Tu exagères de dire que c'est trivial quand elles se chevauchent, c'est pas de la combinatoire "difficile" certes, mais pas triviale non plus.

Tiens, pour la peine, fais donc la preuve de l'existence de n+1 séquences (c'est le maximum)...

 #22 - 31-01-2011 12:37:50

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

Pi pi ! (la suit)e

Je suis pas tout à fait d'accord avec toi gasole au delà de 3 séquences...
On part de l'hypothèse "Dans le découpage de notre nombre en tranches de N chiffres, on arrive à un certain rang à avoir 2 séquences A et B qui se répètent".
Partant de là, on démontre l'existence d'au moins une 3ème séquence, ok jusque là.
Mais ce résultat invalide notre hypothèse : sachant qu'il y a 3 séquences qui se répètent indéfiniment, rien n'oblige à avoir au delà d'un certain rang A et B qui se répètent dans notre découpage. 2 possibilités:
- effectivement, le découpage reste de la forme AAABBBBBAAABBBBBBB...
- ou au contraire, on a quelque chose de la forme AAABBCCCACBBACBBBAAAB...

 #23 - 31-01-2011 13:57:23

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Pii pi ! (la suite)

Certes Scarta, mais si on rencontre des choses comme : AAABBCCCACBBACBBBAAAB par exemple, ça implique que début(B)=fin(A) à cause de l'occurrence de AB, et début(A)=fin(C) à cause de CA et début(C)=fin(C) à cause de CC, etc bref, A=B=C donc rationnel...

Pour 4 ça marche, je n'ai pas dit que ça marche pour n+1 mais c'est sûr qu'au-delà ça ne marche pas (cf mon exemple).

 #24 - 31-01-2011 17:33:34

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

pi pi ! (la syite)

C'est de plus en plus confus pour moi.
Dans l'exemple 12 112 1112 11112 ... et pour un n choisi on peut trouver 2 séquences: 11..11 et 11..12 de n de long. Ce n'est pas ça qu'on cherche?
Ca fait 2 séquences se répétant indéfiniment non?
On ne doit pas chercher la même chose.
Pour trouver n+1 séquences de n de long ou même n+2 il suffit donc d'en trouver une de n(n+2) et de la découper en autant de sous-séquences de n de long. Il est vrai que certaines pourraient être composées de chiffres semblabloes tout en ayant des rangs différents...

 #25 - 31-01-2011 18:49:20

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

pi pi ! (la suitz)

rivas a écrit:

C'est de plus en plus confus pour moi.
Dans l'exemple 12 112 1112 11112 ... et pour un n choisi on peut trouver 2 séquences: 11..11 et 11..12 de n de long. Ce n'est pas ça qu'on cherche?

ben oui, mais elles se chevauchent ! s'il n'y a que ces deux-là, quand tu trouves la seconde (11..12) tu vas forcément la trouver quelque part en chevauchement de la première non ? Et il faut aussi considérer toutes celles qui contiennent un "2" ailleurs comme 1112111 qui va aussi se répéter infiniment souvent.
tu les imagines comme ça :

La notion de séquence me paraît claire(1), je n'arrive pas à comprendre ta notion de séquences non-chevauchantes, explique-moi ce que tu veux dire dans cet exemple :

* Combien y a t-il (selon toi) de séquences de longueur 2 se répétant infiniment dans 12112111211112111112.... ? Et la(les)quelle(s) ?

(1) dans le jargon de la théorie des langages, on dira qu'un mot w est une séquence d'un mot u ssi u peut s'écrire xwy.

PS : comme tu dis ensuite "c'est vrai que...", ben oui, tout est là, il faut examiner la combinatoire.

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

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