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 - 21-12-2011 14:01:16

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

Paires de crarés + indices

Un problème assez compliqué, inspiré d'un des problèmes mensuels du site diophante.fr (en plus dur, histoire d'ajouter des choses ^^)

Soit k un entier strictement positif, soit n un entier strictement positif tel que n*k+1 et n*(k+1)+1 sont tous deux des carrés.

1) Quels sont les derniers chiffres du plus petit n possible, écrit en binaire, pour tout k ? (Je ne précise pas combien de chiffres, c'est vous qui verrez)

2) Prenons un nombre : nous sommes le 21/12/2011 et il est 14h00, on va prendre 211220111400. Pour quelle valeur de k le plus petit n possible est-il 211220111400?

3) Montrer enfin que pour tout k, la plus petite valeur de n divise toutes les autres.

4) Question Bonus
Trouver une formule TRES simple qui lie k ainsi que 3 valeurs successives de n

La case valide la réponse 2


Indices:
Spoiler : [Afficher le message]  Si on note nos deux carrés a² et b², il est possible d'écrire une équation qui lie a, b et k. Commencez par trouver cette équation.
Spoiler : [Afficher le message] (k+1)a² = k(k+1)n + (k+1) = kb² + 1; donc (k+1)a²-kb² = 1
C'est une équation diophantienne du second degré ça

Spoiler : [Afficher le message]
Comment résoudre une équation de type X² - aY² = b ?

On appellera "triplet valide" un triplet (x,y,z) tel que x²-ay² = z. Si (x0, y0, z0) et (x1, y1, z1) sont 2 triplets valides, alors (x0*x1 + a*y0*y1, x0*y1+x1*y0, z0*z1) en est un aussi.
La preuve: (x0*x1+a*y0*y1)² -a(x0*y1+x1*y0)² =
x0²x1² + 2a*x0*y0*x1*y1+a²y0²y1² -ax0²y1² -2a*x0*y0*x1*y1 -ax1²y0² =
x0²x1² + a²y0²y1² - ax0²y1² - ax1²y0² =
x0² ( x1² -ay1²) - a*y0² (x1²-ay1²) =
(x1²-ay1²)(x0²-ay0²) = z1*z0

Par conséquent, si on cherche à résoudre X² - aY² = b, en ayant un triplet (Xi, Yi, b) et un triplet (Xg, Yg, 1); on pourrait générer une infinité de triplets de manière récursive: le premier serait par exemple (Xi*XG+a*Yi*Yg, Yi*Xg+Xi*Yg, b). Autrement dit, les 2 premiers nombres de notre triplet seraient des valeurs X et Y solutions de notre équation.

On peut aussi montrer (c'est plus complexe) que toutes les solutions possibles sont bien générées ainsi.

Pour résumer, si je cherche à résoudre X²-aY²=b:
- je cherche une solution initiale (Xi, Yi)
- je cherche une solution générale (Xg, Yg) à l'équation X²-aY² = 1
- je génère tous les (Xn, Yn), la solution suivante étant à chaque fois (Xn.Xg+aYn.Yg, Yn.Xg+Xn.Yg)



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 22-12-2011 15:42:28

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

paires de carrés + infices

Bonjour,

réponse à la question 1) :  1000
réponse à la question 2) :  13201256962

en attendant la suite...
Cordialement,
masab

 #3 - 22-12-2011 15:48:52

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

Paires de carrés + inddices

Bonnes réponses de masab pour les 2 premières questions, mais un petit détail des calculs serait apprécié smile
Je demande ça parce qu'on peut "deviner" quelle est la plus petite valeur de n en fonction de k en tâtonnant; mais si on "montre" quelle est cette valeur, on a normalement tout en main pour répondre à la question 3 sans trop chercher

J'en profite pour ajouter une question 4.

 #4 - 23-12-2011 15:53:52

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

Paires de carrés + indicess

J'ajoute un indice pour ceux qui auraient du mal à démarrer

 #5 - 24-12-2011 11:50:03

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Paires de carrés + indicces

Soit [latex]k>0[/latex] un entier fixé. Etudions les [latex]n>0[/latex] entiers tels que [latex]nk+1[/latex] et [latex]n(k+1)+1[/latex] soient des carrés. On pose  [latex]nk+1=a^2[/latex], [latex]n(k+1)+1=b^2[/latex], [latex]b=a+r,\ r>0[/latex].
Il vient [latex]n=b^2-a^2[/latex] d'où
[TeX](b^2-a^2)\,k+1=a^2[/TeX]
[TeX]a^2\,(k+1)-b^2\,k=1[/TeX]
[TeX]a^2\,(k+1)-(a+r)^2\,k=1[/TeX]
[TeX]a^2-2rk\,a-r^2k-1=0[/TeX]
Le premier membre est un trinôme du second degré en [latex]a[/latex], de discriminant réduit
[TeX]\Delta'=r^2k^2+r^2k+1[/TeX]
[TeX]a[/latex] étant un entier, [latex]\Delta'[/latex] doit être un carré parfait ; posons [latex]\Delta'=\alpha^2[/latex] ; on a [latex]\alpha>rk[/latex].
Finalement [latex]a=rk+\alpha[/TeX]
Pour [latex]r=1[/latex], on a [latex]\Delta'=k^2+k+1[/latex] qui n'est pas un carré parfait car
[TeX]k^2<k^2+k+1<(k+1)^2[/TeX]
Donc [latex]r\geq 2[/latex].
Par suite
[TeX]\Delta'=r^2k^2+r^2k+1\geq r^2k^2+2rk+1 = (rk+1)^2[/TeX]
[TeX]\alpha\geq rk+1[/TeX]
Par suite
[TeX]n=b^2-a^2=(a+r)^2-a^2=2ar+r^2=2r(rk+\alpha)+r^2[/TeX]
[TeX]n=2r^2k+2r\alpha+r^2[/TeX]
[TeX]n\geq 2r^2k+2r(rk+1)+r^2[/TeX]
[TeX]n\geq 4r^2k+2r+r^2\geq 16k+8[/TeX]
Montrons maintenant que [latex]n_1=16k+8[/latex] est une solution. En effet
[TeX]nk+1=16k^2+8k+1=(4k+1)^2[/TeX]
[TeX]n(k+1)+1=(16k+8)\,(k+1) = 16k^2+24k+9=(4k+3)^2[/TeX]
Pour [latex]k[/latex] fixé, le plus petit entier [latex]n[/latex] solution est donc [latex]n_1=16k+8[/latex].

Par suite [latex]8[/latex] divise [latex]n_1[/latex], donc [latex]n_1[/latex] en binaire se termine par [latex]1000[/latex].

De plus pour avoir [latex]n_1=211220111400[/latex], il faut prendre
[latex]k=(n_1-8)/16=13201256962[/latex].

 #6 - 24-12-2011 19:46:57

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

Paires ed carrés + indices

Je n'avais pas pensé à ce type de demo. C'est vrai que c'est bien plus simple que ma démonstration, mais ça ne donne que la première solution.
Je posterai un autre indice demain.

 #7 - 25-12-2011 22:10:59

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

paires dr carrés + indices

Allez, un autre indice pour bien démarrer

 #8 - 26-12-2011 09:36:05

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

Pairess de carrés + indices

Ce que j'ai pu trouver:
On pose
nk=a²-1
n(k+1)=b²-1
en éliminant n
(k+1)a²-kb²=1
en posant (a0,b0)=(1,-1) et (a1,b1)=(1,1) et
an=(4k+2)a(n-1)-a(n-2) et idem pour bn, on a la suite de tous les (ai,bi) solutions.

Et plus spécialement pour (a2,b2)=((4k+2)a1-1, (4k+2)b1+1)) qui se redémontre facilement.
Autrement dit les carrés impairs font tous partie de cet ensemble !
 
Le n correspondant à (a2, b2) vaut alors 4(4k+2). Pour k=1 n=24

Les (ai,bi) sont l'expression d'un polynome de degré i-1 dont le X est 4k+2.
a2=X.a1-a0
Ce polynome a une valeur +1 ou -1 en degré zéro. Si on met au carré et si on lui ôte 1, cette valeur fixe tombe, et il ne reste que des X, donc divisible par X.
Par ailleurs ces carrés sont impairs, si on ôte 1, ils sont divisibles par 4. Donc les ni=(ai²-1)/k sont divisibles par le plus petit n=4(4k+2).

NB
la suite n'a pas été démontrée, c'est un constat. Sauf pour (a2,b2) qui est assez simple.

 #9 - 26-12-2011 14:35:15

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

Paaires de carrés + indices

@nodgim: si je prends ta formule, le couple qui te donne n est (4k;4k+2), mais ça ne vérifie pas l'équation que tu poses au départ, non?

 #10 - 26-12-2011 18:56:14

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

paires de cartés + indices

Si; peut être n'as tu pas remarqué le couple de départ (a0;b0)=(+1;-1) ceci pour différencier par la suite les an des bn. J'aurais aussi bien pu ne faire démarrer l'algo qu'à partir du 3ème rang, mais cette astuce permet le démarrage à partir des 2 couples de départ a0b0 et a1b1, ce qui est bien nécessaire compte tenu que la suite a besoin des 2 an (ou bn) précédents.

 #11 - 27-12-2011 08:10:40

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

pairzs de carrés + indices

Euh... je me trompe ou c'était 4k+1 hier dans tes formules ?
En tout cas, là je suis d'accord

 #12 - 27-12-2011 09:43:56

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

Piares de carrés + indices

Oui, j'ai corrigé après relecture, je pensais que ta remarque ne concernait pas cette formule là, ce en quoi j'avais tort apparemment.

 #13 - 28-12-2011 14:48:30

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

paires de carrés + indiced

Ajout d'un méga indice sur la méthode de résolution générale d'un certain type d'équation.

 #14 - 01-01-2012 22:50:32

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

paired de carrés + indices

On cherche les valeurs de n telles que
nk+1 = a²
et n(k+1)+1 = b²

On commence par remarquer que (k+1)a² =(k+1)nk + k+1 = k(n(k+1) + 1) + 1 = kb²+1
Autrement dit, (k+1)a²-kb² = 1

On pose alors c=a(k+1), et on obtient
c²-k(k+1)b² = k+1

Pour résoudre ce genre d'équations, il y a une chose à savoir:
Soit E l'ensemble des triplets (x,y,z) tels que x²-Dy² = z
Dans ce cas, si (p,q,r) et (x,y,z) sont deux triplets de E, alors (px+Dqy, py+qx, rz) en est un autre.

Pour résoudre ce genre d'équations, on commence par trouver une solution particulière (c,b,k+1) et une autre générale (c0, b0, 1); et on génère toutes les solutions grâce aux formules ci-dessus. On peut aussi montrer que toutes les solutions sont bien générées par cette méthode, mais ça n'est pas le but. Je pense que Wikipedia ou mieux Mathworld ont bien un article sur le sujet.

Ici, on cherche une solution particulière: vu que a=b=1 est une solution triviale, on va vérifier rapidement que b=1 et c=k+1 en est bien une:
(k+1)²-k(k+1) = k+1

Pour la solution générale, l'idée est d'appliquer la formule ci-dessus au triplet de la solution particulière et lui-même.
Du triplet (k+1, 1, k+1), on génère un autre triplet ((k+1)²+k(k+1), 2(k+1), (k+1)²)
Autrement dit, ((k+1)²+k(k+1))² - 4k(k+1)^3 = (k+1)²
En divisant par (k+1)², on obtient notre solution générale: c=2k+1 et b=2

L'ensemble des solutions est donc obtenu via les formules suivantes:
b_0 = 1, c_0 = k+1
c_(x+1) = (2k+1).c_x + 2k(k+1)b_x
b_(x+1) = (2k+1).b_x + 2.c_x

Comme on cherchait à la base a et b, on a alors:
a_0 = b_0 = 1
a_(x+1) = (2k+1)a_x + 2kb_x
b_(x+1) = (2k+1)b_x + 2(k+1)a_x

Partant de là, si je cherche les valeurs de n, je trouve, via la formule n = b²-a²:
n_0 = 0
n_(x+1) = b²_(x+1) - a²_(x+1)
= (4k+3)a²_x + (4k+1)b²_x + a_x * b_x * (8k+4)
= (4k+3)(k.n_x+1) + (4k+1)((k+1)n_x+1) + a_x * b_x * (8k+4)
= n_x (4k²+3k + 4k²+5k+1) + 8k+4 + a_x * b_x * (8k+4)
= n_x (8k²+8k+1) + (8k+4) (1 + a_x*b_x)
= n_x (8k²+8k+1) + (8k+4) (1 + sqrt((k.n_x+1)((k+1)n_x+1)))
= n_x (8k²+8k+1) + (8k+4) (1 + sqrt(k(k+1)n²_x+(2k+1)n_x+1))

On remarque juste que même si n_0 = 0 vérifie l'équation, il n'est pas accepté par l'énoncé. La plus petite valeur de n est donc n_1, qui vaut alors:
n_1 = 16k+8

On peut donc répondre aux questions:

1) n_1 est un multiple de 8 mais pas de 16. En binaire, il finit donc par 1000

2) n_1 = 16k+8 = 211220111400; donc k=13201256962

3) Une simple récurrence:
n_1 divise n_1.
Soit x tel que n_1 divise n_x, on a alors:
n_(x+1) = n_x (8k²+8k+1) + (8k+4) (1 + sqrt(k(k+1)n²_x+(2k+1)n_x+1))
n_1 = 16k+8 est pair, donc n_x aussi, et donc k(k+1)n²_x+(2k+1)n_x+1 est impair. Sa racine est donc impaire aussi et vaut 2q-1
Du coup, n_(x+1) = n_x (8k²+8k+1) + (8k+4)*2q = n_x (8k²+8k+1) + q*n_1
COmme n_1 divise n_x, il divise aussi n_(x+1)
CQFD.

4) A partir de n_x, on peut calculer n_(x+1). Autrement dit, en inversant la formule, on peut à partir de n_(x+1) retrouver n_x.
Les calculs sont un peu longs et bourrins, je laisse les sceptiques vérifier par eux-mêmes, toujours est-il qu'on trouve le résultat suivant:
n_(x-1) = n_x (8k²+8k+1) + (8k+4) (1 - sqrt(k(k+1)n²_x+(2k+1)n_x+1))
C'est quasiment la même formule sauf que le +sqrt est devenu -sqrt.
Partant de là, on peut faire disparaître la racine et trouver un résultat remarquable:
n_(x+1) * n_(x-1) = n_x (n_x-16k-8)
(En effet, (1+sqrt(x))(1-sqrt(x)) se simplifie en 1-x)

Du coup, si x,y, et z sont trois valeurs successives de n, avec x<y<z, on a:
xz = y(y-16k-8)


Quelques exemples:
Pour k=2, la plus petite valeur n est 40; en effet 2*40+1 = 9² et 3*40+1 = 11²
La valeur suivante est 40 * 49 + 20 (1+9*11) = 3960; en effet 2*3960+1 = 89² et 3*3960+1 = 109²
La suivante est (3960*3920)/40 = 388080; en effet 2*388080 = 881² et 3*388080+1 = 1079²
La suivante est (388080*388040)/3960 = 38027920; en effet 2*38027920+1 = 8721² et 3*38027920+1 = 10681²
etc...


Pour k=125, la plus petite valeurs est 2008; 2008*125+1 = 501² et 2008*126+1 = 503²
La suivante est 2008*126001 + 1004*(1+501*503) = 506022024; en effet 125*506022024+1 = 251501² et 126*506022024+1 = 252505²
La suivate est (506022024*506020016)/2008 = 127518562092048; 127518562092048*125+1 = 126253001² et 127518562092048*126+1 = 126757007²
La suvante est (127518562092048*127518562090040)/506022024 = 32134932683814260080
125*32134932683814260080+1 = 63378755001²
126*32134932683814260080+1 = 63631765009²
etc...

 

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 : 

Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Sujets similaires

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