Arg, en effet ... j'ai stoppé les calcules à 50 (c'est stupide ...).Envoyé par yat
Pour le raisonnement en revanche, je suis quasiment sûr de moi, il suffit d'ajouter aux contraintes ce que nous apprend le doute de Serge et de Corine chacun leur tour. (cf. mon premier post du topic)
--Yankel Scialom
Je n'en doute pas. Mais il va me falloir plus d'explications pour le comprendre.
Non car la somme S=c+d pourrait très bien ne pas passer l'épreuve Serge ne trouve pas. En effet si pour toutes les autres décompositions S=c'+d', c'²+d'² ne s'écrit que de de cette manière en somme de carrés, Serge trouve. corine réfléchissant à celà elle trouve à ce tour si on ne suppose rien sur la décomposition de c+d.
Voici où j'en suis :
{a,b} paire solution, dans la suite quand j'écris une égalité les paires de chaque membre sont distincts (on ajoute des "il existe"... mais je soulage l'écriture)
C1 : Carine ne trouve pas au 1er tour
Donc a²+b²=c²+d²=... (au moins deux décompositions)
S1 : Serge ne trouve pas au 1er tour
a+b=i+j avec {i;j} satisfaisant C1 {a;b} la satisfait déjà. donc i²+j²=m²+n²
C2 : Carine ne trouve pas au 2ème tour
Donc a²+b²=c²+d² avec {c,d} vérifiant S1 {a,b} la satisafit déjà, càd c+d=k+l, k²+l²=o²+q²
S2 : Serge ne trouve pas au 2éme tour
a+b=i+j avec {i;j} satisfaisant C2 {a;b} la satisfait déjà. Donc i²+j²=m²+n², m+n=r+s, r²+s²=e²+f²
C3 : Carine ne trouve pas au 3ème tour
Donc a²+b²=c²+d² avec {c,d} vérifiant S2 {a,b} la satisafit déjà, càd c+d=k+l, k²+l²=o²+p², o+p=w+x, w²+x²=y²+z²
S3 : Serge ne trouve pas au 3ème tour
a+b=i+j avec {i;j} satisfaisant C3 {a;b} la satisfait déjà. Donc i²+j²=m²+n², m+n=r+s, r²+s²=e²+f², e+f=g+h, g²+h²=u²+v²
C'4 : Carine trouve (elle a mis le temps)
donc a+b staisafit S3 mais c+d ne la satisfait pas.
a²+b²=c²+d² {a,b} satisfaisant jusqu'au bout, {c,d} jusqu'à C3 mais pas plus loin les éventuelles autres sont au mieux comme {c,d} Idem pour {i,j}
Cela signifie que nous devons déterminer les S'=y+z ne connaissant qu'une décomposition satisfaisant y²+z² peut s'écrire autrement comme somme de deux carrés.
Enfin une bonne nouvelle dans ce problème de telles sommes s' ne sont pas bien nombreuses.
(Remise à zéro des lettres pour l'instant : le stock est épuisé)
1ère remarque : si S"=a+b=c+d avec a²+b²=a'²+b'² et c²+d²=c'²+d'² alors tout nombre de la forme k.S" staisfait aussi cette condition. Preuve : on multiplie les décompositions par k.
Là il vaut mieux connaître les entiers de Gauss.
a²+b²=(a+ib)(a-ib)
a+ib=p1.p2...pn
a-ib=p1*p2*...pn*
où pi sont des premiers chez les entiers de Gauss et * désigne le conjugué.
On peut écrire a²+b²=c²+d² si il existe au moins deux premiers de Gauss(éventuellement le même doublé càd au carré) qui sont de "vrais" complexes : x+iy x et y non nuls et x+iy distinct de 1+i et ses "compagnons" : 1-i, -1+i, -1-i.
En effet, on peut écrire autrement en permuttant ces premiers et leurs conjugués dans la décomposition en produit. Mais pour les premiers de Gauss entiers naturels (modulo i) ils sont multiples (par 1 ou -1) de leurs conjugués et il en est de même de 1+i (par i ou -i) mais ce sont les seuls.
Réglons le cas des "grands" premiers naturels pour la somme.
On cherche sous la forme :
n²+(m-n)²=2n²-2mn+m²
modulo 5 : (on lit congru au lieu de égal)
=2n²+3mn+m²=2(n²+4mn+3m²)=2(n-m)(n-3m)
C'est nul modulo 5 si n=m ou n=3m modulo 5
Donc dès que le nombre dépasse 11 il y a déjà au moins deux normes multiples de 5 (qui généralement conviennent, il suffit d'un autre premier impair congru à 1 modulo 4).
Pour s'assurer, il faut un deuxième 5 :
n=3m+5p (l'autre ne marche pas)
donne norme =0 modulo 25 si p=-m modulo 5.
Donc dès que p sera "assez grand" (environ >75, peut être moins) deux normes seront divisibles par 25, on pourra écrire la somme des carrés autrement.
Après test (jusque p=19 perso, j'ai aucun doute si quelqu'un peut terminer la vérif merci), il n'y a que 2,3,5 et 7 qui ne se décomposent pas en au moins deux sommes a+b avec a²+b²=c²+d². 2 et 3 n'en ont aucun, 5 et 7 en ont un 5²+0²=3²+4².
Leurs multiples :
5)
10=10+0=5+5
15=15+0=10+5
35=35+0=20+15
25
7)
49=21+28=26+23 ; 26²+23²=1205=5.241 241 premier naturel congru à 1 modulo 4
14=8+6=3+11 ; 3²+11²=2.5.13 5 et 13 non premiers de Gauss
21=12+9=19+2 ; 19²+2²=365=5.73 73 premier naturel congru à 1 modulo 4.
3)
9=1+8 1²+8²=65=5.13
27=3+24=4+23 avec 4²+23²=545=5.109
Pour les multiples de 2^. et 3 il suffit de regarder les décompo impaires au fur et à mesure
6 aucun
12 aucun
24=1+23=3+21 1²+23²=530=2.5.53 ; 3²+21²=450=25.?
Multiples de 9 :
18=2+16=1+17 1²+17²=290=2.5.29
Les paires n'ayant aucune décomposition convenable sont : 2,3,6,12
en ayant exactement une sont :5, 7 et 9
En reprenant les notations du début (celui avec les 26 lettres utilisées)
les trois seules paires possibles pour y et z
sont {0,5} {3,4} et {1,8}
"Il n'y a plus qu'à" reprendre chacun d'eux, remonter pour voir les possibilités pour les autres valeurs et trouver {a,b}.
Je pense que je vais attendre le week-end pour décortiquer ton post, parce que là sinon après je vais être beaucoup trop détendu. Ca le ferait pas, je suis au taf, quand même.
Yat : bon week-end
Sinon
deux "solutions" pour y et z se suppriment facilement : {0,5} et {3,4} qui se renvoient mutuellement l'un à l'autre, on ne peut donc pas "remonter".
Comme j'ai changé mes variables, je l'écris en somme :
9=1+8
1²+8²=65=5.13 (=>2 et exactement 2 écritures)=7²+4²
7+4=11=2+9 (le seul satisfaisant)
2²+9²=85=5.17 (2 et seulement 2 écritures)=6²+7²
Donc c+d=13
3 possibilités :
{c,d}={0,13} et {a,b}={5,12}
{c,d}={1,12} et {a,b}={8,9}
{c,d}={2,11} et {a,b}={5,10}
Les trois conviennent.
{8,9} est l'unique solution n'admettant pas des écritures avec zéro : 0²+z²=x²+y².
Décidément, homotopie, tu travailles fort...
Honnêtement, je n'ai pas compris grand'chose de toutes tes explications, ça vole un peu trop haut pour ma petite tête. Cependant, et je m'en excuse presque, je crois que le résultat auquel tu aboutis est faux: 8 et 9 ne peut pas être la solution. Si les deux nombres étaient 8 et 9, Carine connaîtrait la somme des carrés, soit 145. Et comme 145 ne peut être obtenue par aucune autre somme de carrés, Carine devrait pouvoir donner la réponse dès le premier tour.
Je n'ai aucune idée de l'endroit où se situe ton erreur, mais elle semble être en quelque part...
Je vais essayer de trouver le temps ce soir (dans environ 8 heures) de donner le début de mon raisonnement. Espérons que cela aidera...
Le monde se divise en 10 : ceux qui connaissent le code binaire et ceux qui ne le connaissent pas.
Ne cherche pas l'erreur est là : 145=12²+1²=8²+9²
comme retrouver cela :
145=5.29 5 et 29 sont deux premiers naturels congrus à 1 modulo 4 donc chacun produit d'un premier de Gauss et de son conjugué :
5=(2+i)(2-i) 29=(5+2i)(5-2i)
Deux manières de réorganiser cela :
145=[(2+i)(5+2i].[(2-i)(5-2i]=[8+9i][8-9i]=8²+9²
145=[(2+i)(5-2i].[(2-i)(5+2i]=[12+i][12-i]=12²+1²
Cela m'aura permis d'illustrer comment on utilise les entiers de Gauss pour retrouver les décompositions en somme de carrés.
A remarquer que la simple écriture 5.29 permet de savoir qu'il ya deux manières de l'écrire sous forme de somme de carrés.
Simplification d'un point :
tout premier supérieur à 11 (compris) peut être décomposé de deux manières différentes en somme de deux carrés.
On cherche les décompositions N=n²+(m-n)² multiples de 5. Modulo 5, on a :
2n²-2nm+m²=2(n+m)(n-2m) (Il suffit de développer pour vérifier)
n est congru à -m ou 2m modulo 5. m-n est congru à 2m ou -m. n ou bien (m-2n) est congru à-m. On ne compte donc que les nombres n congru à -m modulo 5.
Si m>=10, il y a au moins deux nombres n1 et n2 congrus à -m (donc, ici, non nuls ainsi que m-ni car m est premier distinct de 5). On obtient donc deux fois une norme multiple de 5.
On décompose N en facteurs premiers naturels :
N est le carré de la norme d'un entier de Gauss donc
N=5.2^n.P1.q1^(2m1)...qk^(2mk) où P1 est le produit de premiers congrus à 1 modulo 4, les qj sont des premiers congrus à 3 modulo 4.
Ici, n=0 car N est impair car m est impair.
P1 est distinct de 1, en effet sinon la seule décomposition (à permutation et multiplication par les inversibles 1,-1,i,-i près) est :
[(2+i)q1^(m1)...qk^(mk)][(2-i)q1^(m1)...qk^(mk)]. Autrement dit, m=(2+1)q1^(m1)...qk^(mk)=3q1^( m1)...qk^(mk). Ceci contredit soit m premier, soit m supérieur à 10.
Il existe au moins un premier congru à 1 modulo 4 dans la décomposition en facteurs premiers naturels de N autre que le premier 5. Ceci montre que N s'écrit d'une autre manière sous forme de somme de carrés.
"Problème" de la décomposition en facteurs 0²+c². Ceci ne peut se poser que si P1=5. En effet, on peut toujours éviter de tomber sur un réel ou un imaginaire pur si P1 contient un premier distinct de 5. Si N=5^m avec m>=4, il existe plus de trois décompositions dont au moins deux conviennent. 125=N(10+5i)=N(11+2i) donc les deux écritures possibles conviennent.
Reste le cas P1=5. On a N=5².q1^(2m1)...qk^(2mk), on aboutit à n+(m-n)i=(4+3i)q1^(m1)...qk^(mk) d'où m=7q1^(m1)...qk^(mk) et on conclut comme précédemment.
Je savais que la vérif "à la main" n'était pas utile
Correction de ce qui précède :
j'ai oublié les puissances de 2
Et une solution de plus :
8=1+7
1²+7²=5²+5²
5+5=10=10+0
10²+0²=8²+6²
8+6=14=1+13
1²+13²=7²+11²
Solution (7,11)
suites possibles :
i)(2,16) (8,14)...
ii) (1,17) (11,13)...
Quant à virer le zéro des décompos pour n'avoir qu'une solution est une illusion. En effet, dans ce cas
9=1+8 aboutit à l'unique solution (8,9)
8 s'arrête à 10=5+5
Mais trois nouvelles sommes n'ont plus qu'une décompo possibles : 10, 14 et 15 (on refuse 0 ou on ne le refuse pas, je vous passe les détails montrant qu'il n'y a que cela le plus gros est fait)
10 s'arrête à 8 (c'est le chemin inverse)
15=5+10 "passe par" (8,9) mais donne une autre solution.
Et 14 :
14=1+13 1²+13²=7²+11² 7+11=18, deux possibilités
a) 18=16+2 16²+2²=8²+14² 8+14=22 quatre possibilités
a1) 22=1+21 1²+21²=9²+19²
a2) 22=3+19 3²+19²=9²+17²
a3) 22=4+18 4²+18²=12²+14²
a4) 22=9+13 9²+13²=5²+15²
b) 18=1+17 1²+17²=11²+13² 11+13=1+23 1²+23²=13²+19²...
Donc 5 solutions commençant en 14 : {9,19}{9,17}{12,14}{5,15}{13,1 9}.
0 accepté : 4 solutions
0 refusé : 7 solutions
Finalement je préfère accepter le zéro.
Ce n'est pas fini (cf. les ... non vérifiés) mais peu d'illusion : pour que ces chemins se terminent il faudrait qu'ils reviennent soit sur 9=1+8, soit sur 15=5+10, soit sur 14=1+13 (seules fins possibles) et je ne vois vraiment pas comment il ferait là où je les ai laissé (ceci dit je ne suis pas sûr que ça se montre facilement mais il n'y a que quelques étapes à faire ici). Je n'ai donc presque aucun doute qu'ils passent à une vérif en bonne et due forme (ou alors j'ai fait une erreur avant ce qui est toujours possible).
Promis, je calme le post pour un instant.
Oups, j'avais promis (mais je me suis trompé)
Des "solutions" sont à éliminer.
Par exemple (9,17) (aii) une "voie" l'amène à (3,19) 3+19=22. De là une "voie" (celle allant à 1,13) via (8,14)) est éliminée mais pas les autres celles de (1,21) (4,18) (9,13). Donc ni cette première ni cette dernière ne conviennent.
Idem pour (13,19) (b) arrivé à (1,17) on peut éliminer la "voie" (7,11)-(1,13) mais pas celle (2,16)-(8,14)...
La "solution" (5,10) a une alternative arrive à (11,2) à une bifurcation pour somme =13 avec possibilités la voie (1,12)-(8,9) viable (et longuement viable) et la voie "périssable" (6,7) qui arrive à(1,8) mais en 4 temps donc non encore éliminé là où s'arrête le problème (et maintenant je sais pourquoi)
Si 0 est refusé il n'y a donc qu'une solution : (8,9).
Si 0 est accepté en fait (8,9) pour une raison similaire : une voie est éliminée mais pas toutes; il me semble qu'elle n'est a=lors plus solution de même que ses consoeurs (5,12) et (5,10). Par contre il me semble que (7,11) est bien solution.
Si 0 est accepté, il me semble qu'il n'y a qu'une solution : (7,11).
En effet... Je n'avais pas besoin de tout comprendre ton raisonnement pour m'en apercevoir, il m'aurait suffit d'un peu plus d'attention...Ne cherche pas l'erreur est là : 145=12²+1²=8²+9²
Intéressant! Tu arrives au même résultat que moi mais d'une façon... tellement différente!
Pour ma part, j'ai essayé de trouver les sommes de carrés qui se répétaient (ayant fait le travail manuellement, j'ai commis des erreurs; exemple: 145 m'avait échappé). La figure jointe montre ce que j'avais fait.
Carine ne connaît pas la réponse du premier coup, donc il doit y avoir au moins deux sommes différentes qui donne la même somme de carrés. Sur la droite de la figure, j'ai mis en évidence les "candidats" possibles. Serge ne peut répondre: il a donc une somme qui pourrait donner au moins deux sommes de carrés qui mettent Carine dans l'impossibilité de répondre. Ainsi de suite.
Exemples:
1- Si Carine a 50, elle ne peut savoir si c'est 1 et 7 ou bien 5 et 5. Elle ne peut répondre. Mais Serge peut répondre: s'il a 8 et s'il sait que Carine ne peut répondre car il y a au moins 2 réponses possibles, alors il sait que la somme des carrés est 50. Il donne la réponse!
2- Si Carine avait 145, elle ne pourrait répondre. Mais elle saurait que Serge a soit 13, soit 17 comme somme. Si Serge a 13, il hésite entre une somme des carrés de 125 ou 145. S'il a 17, il hésite entre 145 et 205. Carine sait alors que Serge hésite entre ces valeurs, mais ne peut toujours pas répondre. Sachant que Carine ne peut répondre, Serge sait que la somme des carrés n'est pas 125 car si cela avait été le cas, elle aurait pu répondre. Il sait donc que la somme des carrés est 145 et peut répondre immédiatement.
3- 7 et 11 ont une propriété intéressante. Pour Carine, la somme des carrés est 170. Ce qui signifie que pour elle, la somme doit être de 14 ou 18. C'est agaçant: 14 pourrait donner d'autres sommes de carrés (100 ou 130), tout comme 18 (260 et 290). Il faut donc éliminer ces possibilités.
J'ai l'impression d'être beaucoup moins rigoureux que toi, et je suis heureux d'arriver à la même réponse que toi...
Le monde se divise en 10 : ceux qui connaissent le code binaire et ceux qui ne le connaissent pas.
Bonjour,
j'avais fait le même tableau que SunnySky
sauf que je n'ai pas utilisé le 0 et qu'après j'ai classé les résultat par ordre croissant afin de déterminé les carrés en doubles ceci permet de voir que dans ta liste (3 colonnes de gauches) il manque le 65, 85, 125,....
bonjour,
Matthias, ClaudeH pense que tu as déjà posé ce type de question, pourrais tu nous dire si dans ta solution il faut tenir compte du 0.
Merci
Je suis désolé, homotopie, je ne comprends pas grand chose à tes explications.
Et SunnySky, les tiennes me sont beaucoup plus accessibles, mais là encore, il y a des décompositions que tu zappes pour une raison qui m'échappe, et je ne comprends pas ta conclusion.
En d'autres termes :
Ce qui me pose vraiment problème, c'est qu'en plus de ne pas comprendre les explications, pour moi la solution obtenue ne fonctionne pas.
Alors pour commencer, voilà ce que j'ai compris de votre solution. Si c'est pas bon, merci de me corriger et inutile de lire la suite.
-zéro est un entier naturel
-(7,11) est la solution
En partant du principe que ces deux affirmations sont justes, voici ce que je déduis :
Carine a 170 et parle au rang 7. Ca implique que le silence de Serge au rang 6 lui a donné suffisamment d'informations pour valider une de ses hypothèses. Or ses deux hypothèses sont (13,1) et (11,7), donc si les nombres étaient 13 et 1, Serge aurait parlé au rang 6.
Serge a 14 et parle au rang 6. Le silence de Carine au rang 5 lui a donc permis de valider une hypothèse. Le problème est qu'à ce stade, Serge a trois hypothèses : (8,6), (11,3) et (13,1). Pour que Serge puisse parler dans ces conditions, il faut que dans les cas (8,6) et (11,3), Carine ait parlé au rang 5.
Le cas (8,6) marche bien, on n'a à chaque étape qu'une hypothèse à éliminer avant d'aboutir à la somme de 8 en bout de chaine pour (1,7). Je détaille quand même les étapes, même si manifestement tout le monde les a déjà (paragraphe rébarbatif à zapper si c'est déjà bien clair) :
Carine a 100 au rang 5, ses hypothèses sont (10,0) et (8,6), elle élimine l'hypothèse (10,0) parce que si Serge avait 10 il aurait parlé au rang 4.
Serge a 10 au rang 4, ses hypothèses sont (5,5) et (10,0), il élimine l'hypothèse (5,5) parce que si Carine avait 50 elle aurait parlé au rang 3.
Carine a 50 au rang 3, ses hypothèses sont (5,5) et (7,1), elle élimine l'hypothèse (7,1) parce que si Serge avait 8 il aurait parlé au rang 2.
Serge a 8 au rang 2, sa seule hypothèse est (7,1) parce que les autres décompositions de 8 donnent des sommes de carrés uniques qui auraient permie à Carine de parler au rang 1.
Mon problème, c'est le cas (11,3). Accepter la solution qui aboutit au couple (7,11) implique que dans l'hypothèse ou Carine a 130, elle aurait parlé au rang 5. Alors je continue...
Carine a 130 au rang 5, ses hypothèses sont (11,3) et (9,7), elle élimine l'hypothèse (9,7) parce que si Serge avait 16 il aurait parlé au rang 4.
Serge a 16 au rang 4, ses hypothèses sont (9,7) et (14,2), il élimine l'hypothèse (14,2) parce que si Carine avait 200 elle aurait parlé au rang 3.
Carine a 200 au rang 3, ses hypothèses sont (14,2) et (10,10), elle élimine l'hypothèse (10,10) parce que si Serge avait 20 il aurait parlé au rang 2.
Et là, encore une fois, c'est le drame.
Pourquoi Serge aurait-il bien pu parler au rang 2 avec son 20 ? Ses hypothèses sont (10,10), (15,5) et (20,0). Or (15,5) donne un 250 à Carine, qui n'a aucun élément pour trancher avec (13,9) dès le premier tour, et (20,0) donne un 400 à Carine, qui n'a aucun élément pour trancher avec (16,2) dès le premier tour.
Ma conclusion est que la solution (11,7) ne fonctionne pas.
Pour aller plus loin :
Ma méthode consiste à tracer un graphe dont les noeuds sont des sommes ou des sommes de carrés, et dont les arcs sont des couples d'entiers reliant leur somme et la somme de leurs carrés. On ne fera entrer dans le graphe que les noeuds sommes de carrés qui ont plusieurs décompositions possibles.
Si Carine avait parlé au premier tour, sa somme de carrés ne serait donc pas dans le graphe. Les extrémités du graphe (les noeuds qui n'ont qu'un arc) correspondent donc aux sommes qui auraient permis à Serge de parler au deuxième tour. Le reste est une question de distance : si quelqu'un parle au rang n, ça signifie qu'en parcourant le graphe dans toutes les directions possibles à partir du noeud qui correspond au nombre dont il dispose, après avoir parcouru une distance n-1 il ne reste qu'un trajet qui ne soit pas sorti du graphe.
Or le graphe n'a que 4 extrémités, qui sont les sommes 5, 7, 8 et 9 (soit dit en passant, le graphe n'est pas connexe), et il n'y a aucun noeud qui vérifie cette propriété.
Ma seconde conclusion est qu'en considérant le zéro comme un entier naturel, le problème n'a aucune solution au rang 7. Su coup la seule solution au problème donné (c'est à dire sans l'indication de l'acceptation ou non du zéro) est donc celle proposée par TITI78.
Bonjour..
J'ai lû attentivement toutes les réponses, et remercie tous ceux qui ont participé avec «*brio*» à ce fil..
Je suis également épaté de lire les prouesses mathématiques que certains ont développé, même si quelques réponses dépassent ma compréhension, et je loue le temps qu'ils ont dû consacrer. - Bon stop la pommade..!
Mais, il me semble que la propositions (11,7) ne satisfassent pas l'intégralité du problème initial qui a été posé.
* (11, 7) est le résultat de x² – Sx + P =0
Si on admet (11,7) comme résultats ces chiffres devraient satisfaire les équations:
x+y=18
x²+y²=170
Je n'arrive pas à résoudre cette équation.
Rappel : l'énigme veut que ce soit, la somme des entiers et la «*somme*» de leur carré et non leur produit.
Prière de m'excuser si mes déclarations sont fausses..
Cordialement.
Il faut se remémorer de vieux souvenirs...
y=18-x
x²+(18-x)²=170
2x²-36x+154=0
x²-18x+77=0
discriminant=324-4*1*77=16
x=(18+/-4)/2
donc x=7 ou x=11, avec y=18-x.
On décompose 77 = 7 x 11, et on vérifie 7+11... Foin de discriminant...
Je ne suis pas sur de la question. Peut-être cherchais-tu quelque chose comme
(x+y)² = x²+y²+2xy
d'où x²+y² = S²-2P
ici 18²-154 = 170 ??
Cordialement,
Nous sommes d'accord (oubli d'une branche sur mon brouillon
Je ne l'ai pas exprimé ainsi mais c'est également comme cela que j'ai procédé (avec malheureusement au moins un oubli de branches
Nous sommes d'accord (bon je me suis amusé à le montrer qu'il n'y a que 4 extrémités dans ce cas et 5 dans l'autre mais c'est l'aspect le plus joli du problème, non ?
(8,9) seule solution compatible avec les données du problème.
La raison qui t'échappe est très simple: j'ai été trop vite et j'ai commis des erreurs. Ça explique bien des choses...
Bon, je vais essayer de faire mieux la prochaine fois. Je me suis sans doute attaqué à un problème qui m'apparaissait intéressant (et qui l'est réellement), mais qui demandait plus de temps et de concentration que je ne pouvais lui en accorder. Mais le plaisir de raisonner et d'avancer est toujours là!
Le monde se divise en 10 : ceux qui connaissent le code binaire et ceux qui ne le connaissent pas.
Nous sommes d'accord (oubli d'une branche sur mon brouillonVous me rassurez... je commençais à devenir cinglé en essayant de comprendre vos solutions.
Du coup, tout le monde est d'accord sur la solution de TITI78.
Je ne me suis pas trop attardé sur le problème sans le zéro, mais en ce qui me concerne l'unicité des 4 extrémités était vraiment une conjecture : au delà de 20, toutes les sommes commencent à se décomposer en au moins trois combinaisons valides, faisant partir dans tous les sens, et même les sommes de carrés ont de plus en plus de décompositions valides. Si tu as une démo de ça, elle m'intéresse.bon je me suis amusé à le montrer qu'il n'y a que 4 extrémités dans ce cas et 5 dans l'autre mais c'est l'aspect le plus joli du problème, non ?
question que je me pose : y a-t-il seulement deux composantes connexes infinies ? Je pense que oui mais...
Après, bon, on a nécessairement une séparation des nombre pairs et des nombres impairs, les sommes 5 et 7 sont les seules qui se détachent du lot au début, et comme tout s'emmêle à mesure que les nombres manipulés sont grands, je suppose que ça nous fait trois composantes dont deux infinies. Mais là encore, pour la démo...
1) Désolé pour mes erreurs qui t'ont perturbées.
2) pour la démo elle est déjà donnée
Je la reprends en plus explicitée.
Elle suppose connaître ou admettre le résultat suivant :
1) tout nombre naturel premier congru à 1 modulo 4 est une somme de carrés (il y a aussi 2=1²+1²)
Prop 2 :Un nombre c.c' tel que c et c' sont des sommes de carrés non nuls et distincts admet plusieurs décompositions différentes en sommes de carrés. Si c ou c' sont premiers (sauf 2) la somme vérifie cette condition p ne peut être égal à m² ou 2m².
Quelqu'un qui n'aime pas les preuves peut aller aux exemples.
Preuve : c=a²+b²=(a+ib)(a-ib) c'=(a'+ib')(a'-ib')
c.c'=[(a+ib)(a'+ib')][(a-ib)(a'-ib')]
cc'=[(a+ib)(a'-ib')][(a-ib)(a'+ib')]
Sont-ils distincts ?
Plus précisément
On a (a+ib)(a'+ib')=d+ie
et (a+ib)(a'-ib')=d'+ie'
Distincts signifient paires distinctes et ceci en valeur absolue. Si en permuttant c et d ou/et en changeant de signe de c ou/et d on obtient c',d' on a la même paire.
Or un double changement de signe est la multiplication par -1.
La multiplication par i permutte avec un changement de signe.
Le conjugué change un signe.
On a donc d'+ie'={1,-1,i ou -i}{(d+ie) ou (d-ie)}
Si on a du conjuguer, on a (a-ib)(a'+ib')=d'-ie' on revient au cas où la conjugaison n'est pas utilisée.
Dans ce dernier cas, on a (a+ib)(a'+ib')=inversible.(a+i b)(a'-ib')
d'où a'+ib'= inversible (a'-ib')
Cette dernière égalité n'est possible que si a'=0, b'=0 ou a'=b'
Exemples de recomposition :
5.13=[2+i)(2-i)][(3+2i)(3-2i)]
1) 65=[(2+i)(3+2i)][(2-i)(3-2i)]
=[4+7i].conjugué=4²+7²
2) 65=[(2+i)(3-2i)][(2-i)(3+2i)]
=[8-i].conjugué=8²+1²
Toute autre recombinaison donne l'une ou l'autre.
5²=[(2+i)(2-i)][(2+i)(2-i)]
1) 25=[(2+i)(2+i)].conjugué
=[3+4i].conjugué=3²+4²
2) 65=[(2+i)(2-i)].conjugué
=[5+0i].conjugué=5²+0²
Toute autre recombinaison donne l'une ou l'autre.
5².13 en donnent 3
5^3 en donne 2
5^3.13 en donne 4
Il suffit donc de trouver deux premiers congrus à 1 modulo 4 dans un nombre pour être sûr qu'il s'écrit plusieurs fois comme somme de carrés (non nécessairement distincts et non nécessairement sans zéro)
Désormais, on a un nombre m donné dont on recherche des décompositions m=n+(m-n) qui sont divisibles par deux nombres premiers (non nécessairement distincts, dans ce cas il est au carré) congrus à 1 modulo 4.
Le 5 est le plus fréquent car le plus petit (il n'a pas d'autres particularités), il est donc celui que l'on cherche d'abord.
On a comme condition S=n²+(m-n)²=0 (5)
On aboutit à n=2m ou -m (symétrie entre n et m-n), donc pour toute tranche de 5 on est sur de trouver une paire (n,m-n) tel que la somme S des carrés soient un multiple de 5.
Maintenant, ce nombre peut-il ne contenir que du 5 et d'autres nombres qui ne prêtent pas à la recomposition. Mais cela signifie que S=5.2^d.produits de carrés de premiers congrus à 1 modulo 4. (résultat qui provient du fait que les seuls premiers chez les entiers de Gauss sont, les premiers congrus à 3 modulo 4 et les a+ib avec a²+b² premier (et donc égal à 2 ou congru à 1 modulo 4).
Un cas pratique : m premier impair, donc la paire (n,m-n) est constituée d'un pair et d'un impair donc S est impair (d=0).
n+i(m-n)=(2+i).produits de premiers congrus à 3 modulo 4 (seule décomposition possible).{1,-1,i ou -i}
Et de ceci on en déduit que m=3.produit de premiers.
m étant premier ce produit de premier est en fait égal à 1 et m=3(=1+2 et 1²+2², bref le "géniteur" de 5).
Il y a donc (sauf pour 2 et 3) un autre premier congru à 1 modulo 4 et on peut faire des décompositions.
5 et 7 n'ont qu'une telle décompo qui donne une somme de carrés multiples de 5 et d'un autre..
A partir de 11, il y en a au moins deux.
Tous les nombres premiers p supérieurs à 11 admettent au moins deux décompositions p=a+b avec a²+b²=c²+d²
En examinant de plus près, on montre également que ces deux décompositions (a,b et c,d) peuvent être choisies sans zéro et avec deux nombres distincts. Le cas zéro est présent dnas un post précédent, le cas du doublon (donc solution multiple de 1+i) se fait sur le même tonneau (un chouia plus délicat).
Pourquoi s'être contenté des premiers, et les autres ?
Propriété, si S'=kS alors le nombre de décompo ... de S' est au moins égal à celui de S.
S=a+b a²+b²=c²+d² donne
S'=ka+kb (ka)²+(kb)²=(kc)²+(kd)²
Preuve triviale mais résultat intéressant.
Il n'y a plus qu'à se préoccuper des multiples de 2,3,5 et 7 (et que d'eux)
5 offre déjà une décompo possible, ils peuvent se traiter à part.
5k=5m+5n donne trois décompo en somme de carrés
N((2+i)(2+i)(m+in))
N((2+i)(2+i)(m-in))
N((2+i)(2-i)(m+in))
Il y a au moins deux paires {m,n} possibles dès 10.
Si on se préoccupe des exclusions de zéro ou/et de nombres identiques dans la décompo
Les cas particuliers sont m=0 ou n=0 et m=n.
Dès 25, on est tranquille.
10 2 décompo, une avec zéro, une avec doublon
15 2 décompo dont une avec zéro
20 3 décompo dont une avec zéro et une avec doublon
Puissance de 7 et multiples de 7
7 en a un (avec zéro)
49 on a 49=3+46 3²+46²=25.89 donc 3 décompo sans zéro et sans doublon
14 (chez les impairs)
1+13 1²+13²=10.17 OK sans 0 sans doublon (sans-sans)
11+3 11²+3²=10.13 OK (sans-sans)
chez les pairs 2(3+4) vient de 7
21=2+19 2²+19²=365=5.73 OK (sans-sans)
21=7+14 7²+14²=25.49 (et ça rate, 21 n'est pas premier onc l'accident était possible)
21=17+4 17²+4²=305=5.61 OK (sans-sans)
Remarque 13²=169 donc pour les sommes de carrés inférieures (et on peut majorer facilement) il est inutile de chercher (et même de vérifier) ailleurs que les sommes de carrés multiples de 5.
Les produits par 2 ou 3 ne peuvent pas produire de nouvelles décompo car 2 et 3 n'offrent pas de décompo utilisables.
Avec ça il n'y a pas grand chose à vérifier.
Puissance de 3 :
3=0+3 non
3=1+2 1²+2²=5 non
9=1+8 1²+8²=65 Ok (sans-sans)
27=4+23 4²+23²=5.109 OK (sans-sans)
27=3(1+8)=3+24 vu
Puissances de 2 :
2=0+2 non
2=1+1 1²+1²=2 non
4=1+3 1²+3²=10=2.5 non
8=1+7 1²+7²=50=5.10 Ok mais avec doublon
16=1+15 1²+15²=226=2.113 non
(remarque plus grande somme possible du 2 il y en a toujours en exemplaire unique : impair²+impair²; 113<169 donc toujours recherche unique sur multiple de 5)
16=7+9 7²+9²=130=10.13 OK (sans-sans)
+16=2(1+7)=2+14
32=9+23 9²+23²=610=10.61 OK (sans-sans)
Produit 2,3
6 (<13) aucune vérif
12 : idem
24=13+11 13²+11²=290=10.29 OK (sans-sans
24=23+1 23²+1²=530=10.53 OK (sans-sans)
18=1+17 1²+17²=290=10.29 OK(sans-sans)
18=11+7 11²+7²=170=10.17 OK (sans-sans)
Fini
extrémités
toutes décompo acceptées : 5,7,8,9
0 refusé, doublon accepté : 8,9,10,15
0 accepté doublon refusé : 5,7,9,10,16
0 refusé doublon refusé : 9,15,16,20
Et il me semble que seul le cas 0 refusé doublon accepté donne une solution (unique).
Y a pas de mal... j'ai toute la journée pour rattraper mon taf en retard de lundi, mardi et mercrediCa y est, j'ai compris... je m'étais attardé sur la structure du graphe, les boucles internes et tout ça, j'avais complêtement zappé qu'une extrémité était simplement une somme qui ne se décompose qu'en une combinaison valide.
En fait, je me suis franchement emmelé les pinceaux entre les 4 extrémités et les trois composantes connexes
En tout cas, merci pour ces explications détaillées
Je pense que j'ai fait l'erreur inverse, je me suis tellement concentré sur les extrémités que j'ai oublié le graphe et ses diverses branchesje m'étais attardé sur la structure du graphe, les boucles internes et tout ça, j'avais complêtement zappé qu'une extrémité était simplement une somme qui ne se décompose qu'en une combinaison valide.
En fait, je me suis franchement emmelé les pinceaux entre les 4 extrémités et les trois composantes connexes
En tout cas, merci pour ces explications détaillées
Je pense avoir retrouvé mon erreur sur le 14. Cas 0 accepté j'ai deux décompos, je m'arrête là sans les chercher toutes. Je reprends sur le cas 0 refusé j'en élimine une et le 14 n'a plus qu'une décompo, oubliant que je ne l'ai pas décortiqué.
Sinon je pense qu'il est possible de montrer qu'il n'y a que deux composantes connexes infinies.
Elle se baserait sur la remarque suivante : pour une norme N (somme de carrés) donnée, la plus petite des sommes a+b (avec a²+b²=N) est celle pour laquelle (a,b) est le plus proche des axes de coordonnées. Pour une somme donnée S, la plus petite des normes c²+d² (avec c+d=S) est celle pour laquelle (c,d) est la plus proche des bissectrices (y=x et y=-x).
Il semble donc que l'on puisse définir une ligne de plus grande pente :
à partir d'une somme S0, on prend la norme N0, ayant au moins deux expressions la plus proche, la plus petite possible.
à partir de N0, on prend la somme S1 la plus petite possible ayant au moins deux liens... on montre que S1<S0
à partir de S1 ->N1 avec N1<N0...
Pour être sûr de ces passages successifs il faudrait améliorer significativement le résultat que j'ai montré mais ça me semble possible (il faut évidemment prendre S et N suffisamment grand)
On aboutit au fait qu'en partant d'une somme (et donc d'une norme) on peut aboutir à une somme inférieure à une certaine borne. Puis vérifier que les sommes inférieures à cette borne sont dans une même composante (en séparant cas pair et cas impair évidemment)
Et hop un truc de plus à explorer... plus tard
PS : félicitations à TITI78
