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 - 16-11-2022 13:55:23

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

paires orphelinrs

Un peu de maths, pour changer smile

Pour deux entiers (a,b) strictement positifs, on peut générer deux autres paires (a,a+b) et (a+b,b).
En répétant l'opération, on peut générer beaucoup beaucoup de paires (une infinité en fait).

Comme dans la vraie vie, deux paires sont de la même famille si elles ont un ancêtre commun.
Par exemple les paires (31,14), (39,25) ou (46,27) sont de la même famille : elles peuvent descendre de la paire (3,8)

> (3,8) --> (3,11) --> (3,14) --> (17,14) --> (31,14)
> (3,8) --> (3,11) --> (14,11) --> (14,25) --> (39,25)
> (3,8) --> (11,8) --> (19,8) --> (19,27) --> (46,27)

Les questions sont les suivantes :

1. Existe-t-il des paires orphelines (i.e. qui ne sont de la famille d'aucune autre paire) ? Si non : prouvez-le. Si oui : lesquelles ? (et prouvez-le aussi ^^)
2. En dehors des éventuels orphelins, quelle est la probabilité que deux paires soient de la même famille ?

Bon courage !

  • |
  • Répondre

#0 Pub

 #2 - 16-11-2022 15:18:39

ptitours63
Habitué de Prise2Tete
Enigmes résolues : 49
Messages : 30

Paires orhpelines

Bonjour,
Toutes les paires me semblent avoir des ancêtres sauf celles de la forme (x , x).
a+b est forcément différent de a et b si ce sont des entiers strictement positifs.

Le plus vieil ancêtre commun de deux paires est de la forme (p , p) où p est le plus grand commun diviseur (PGCD) de a et b.

Calculer la probabilité que deux paires soient de la même famille revient alors alors à calculer la probabilité que deux paires de nombres aient le même PGCD.

On sait, grâce au problème de Bâle résolu par Euler, que la probabilité que deux nombres aient k comme PGCD est égale à :

Pk = 6 / (PI^2 x k^2)

La probabilité recherchée est donc la somme des Pk^2, soit :

(36/ PI^4) x somme(1/k^4)

Or, grâce à Fourier et Parseval, on peut calculer cette somme, qui est égale à

Somme(1/k^4) = PI^4 / 90

Ce qui nous donne une probabilité de 36/90, soit 40%.

Pas sûr d’avoir été très clair…merci pour l’exercice !

 #3 - 16-11-2022 18:04:03

aunryz
Professionnel de Prise2Tete
Enigmes résolues : 17
Messages : 372

paires orohelines

(Si je ne me suis pas planté comme d'hab. (sourire)²)
...

Pour les paires orphelines ...
Pour revenir vers un élément générateur on utilise la technique qui correspond à la recherche du PGCD des deux nombres.
Il est la valeur commune trouvée par la méthode des soustractions successives.
(représentation géométrique
http://www.prise2tete.fr/upload/aunryz-RCPGCDJPG.jpg
ici revenir de (15,24) ... (3,3))

Si (a,b) est tel que PGCD(a,b) = c alors toutes les paires qui sont dans le même cas "sont familles avec" comme on dit en Lorraine.
donc (il n'y aurait) pas de paires orphelines

Donc (?)
Pour la probabilité que deux paires ne soient pas de la même famille :
je propose 6/π²
?


Du fagot des Nombreux

 #4 - 17-11-2022 00:51:14

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

paires orpgelines

ptitours c'est très clair (en tout cas pour moi)... et bravo !

aunryz: et pourtant, si (quoique ton raisonnement soit correct, en lisant bien l'énoncé tu verras peut-être ce qui coince). Et pour le calcul de la probabilité, je veux bien un développement (pareil ça aidera)

 #5 - 17-11-2022 10:46:05

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

Paires orphelins

Salut,
Entend t-on la famille au sens large (éventuellement intergénérationnelle) ou obligatoirement de même génération (comme dans l'exemple donné) ?
(je ne suis d'ailleurs pas certain que cela change le raisonnement)
Bonne journée.

 #6 - 17-11-2022 10:58:09

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

paireq orphelines

ah non ça c'est un hasard, donc je précise pour tout le monde : un ancêtre commun mais pas nécessairement de même niveau

J'aurais pu ajouter (31,45) ou (11,19) aux exemples

 #7 - 17-11-2022 13:01:40

aunryz
Professionnel de Prise2Tete
Enigmes résolues : 17
Messages : 372

Paires orrphelines

Pour la probabilité, tu n'avais pas demandé dans ton énoncé que l'on justifie sa réponse (sourire)²
(un coup que tu m'as fait je crois (sourire)²² avec un "oui") *
_________

Il y a maintenant ... en prenant du recul, un truc qui me chiffonne
Une paire peut toujours en générer une autre
elle est donc de la famille de cette paire qu'elle génère.

Il n'existe donc pas de paire qui n'est "de la famille d'aucune autre paire"

Faut-il comprendre que tu entends
(Je me dis que ptitours63 a certainement compris ce qui m'échappe là)
"qui n'est générée par aucune paire ?"

à ce compte c'est le cas des paires du type (a,a)
puisque l'antécédant est nécessairement soit
(a, a-a) soit (a-a,a) exclus par ton énoncé. (a et b non nuls)

Merci de ta patience (sourire)²


___
*en rapport avec la probabilité de deux nombres d'être premiers entre eux


Du fagot des Nombreux

 #8 - 17-11-2022 14:00:38

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

paires orphzlines

La première réponse est bonne cette fois-ci. Mais je suis toujours en désaccord avec la seconde - mais ok avec celle de ptitours, après on peut se tromper tous les deux (d'où le développement demandé)

 #9 - 21-11-2022 14:47:04

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

Paaires orphelines

Hello ! voici donc les réponses, qui sont les mêmes que celles de ptitours63

A la première question (et bonne réponse d'aunryz aussi sur celle-là) : toute paire (a,b) avec a≠b admet un parent :
* soit a<b et donc le parent était (a,b-a)
* soit a>b et donc le parent était (a-b,b)
(les autres cas donnent des nombres négatifs qui ne sont pas autorisés)
De ce parent, on peut générer une autre paire, soit (b,b-a) soit (a-b,a) suivant les cas, qui sont différentes par construction de la paire initiale : elles sont donc de la même famille.

Si a=b par contre, la paire n'admet pas de parent : ça serait éventuellement (0,b) ou (a,0) si les nombres nuls étaient autorisés, mais ça n'est pas le cas...
Or, comme le précise l'énoncé, "deux paires sont de la même famille si elles ont un ancêtre commun". Les paires qui n'ont pas de parents n'ont a fortiori pas d’ancêtre.

On en déduit que les "paires orphelines" sont celles de la forme (a,a), bien qu'elles soient elles-mêmes les ancêtres d'une infinité d'autres paires.

Pourquoi cette ambiguïté ? Pour aider à mettre le doigt sur quelque chose : le plus haut ancêtre d'une paire quelconque (a,b) est (g,g) où g=pgcd(a,b)
Démonstration en quelques lignes :
- tous les nombres sont des multiples de g par combinaison linéaire de deux entiers
- chaque parent admet un terme plus petit que ses descendants directs
- en remontant le fil, on a donc une suite d'entier décroissante, majorée par 0 exclu et multiple de g, donc majorée par g
--> on arrive à une absurdité via l'argument de descente infinie...
... sauf si on admet que la descente s'arrête, c'est-à-dire que la paire n'a pas de parent. Et comme expliqué ci-dessus, celles qui n'ont pas de parents sont de la forme (n,n), où n est un multiple de g.
Et pour conclure cette démonstration, on ajoute que si n>g, alors a et b seraient eux-mêmes des multiples de n, et donc on aurait un diviseur commun à a et b supérieur à leur pgcd, ce qui serait absurde.

Conclusion : toute paire (a,b) est rattachée à un unique arbre dont la "racine" serait (g,g) avec g=pgcd(a,b)

Ce résultat est utile pour répondre à la seconde question.

La probabilité que a et b aient pour pgcd le nombre k est [latex]P(pgcd(a,b) = k)=\frac{1}{k^2.\zeta(2)}[/latex]

Si vous ne connaissez pas la fonction Zeta, c'est pas hyper grave (elle va sauter 😉)

La probabilité que 2 paires soient rattachées au même arbre de racine (k,k) est donc la probabilité que chacune des paires le soit, autrement dit que le pgcd de chacune des paires soit k
[TeX]P(pgcd(a,b) = k)*P(pgcd(c,d) = k)=\frac{1}{k^4.\zeta(2)^2}[/TeX]
La probabilité totale est donc la somme de tout ça, pour toute valeur de k
[TeX]P=\sum_k\frac{1}{k^4.\zeta(2)^2} = \frac{\zeta(4)}{\zeta(2)^2}[/TeX]
Et pour finir, on peut remplacer la fonction Zeta par sa valeur exacte, qui est connue pour les deux cas particuliers 2 et 4
[TeX]\zeta(2) = \frac{\pi^2}{6}\\
\zeta(4) = \frac{\pi^4}{90}\\
P = \frac{36}{90} = 0.4[/TeX]
Au final donc 40% de chance pour deux paires d'être de la même famille 😊

 #10 - 21-11-2022 16:43:53

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

Paires orpheliens

Petite remarque supplémentaire, j'ai fait tourner une petite simulation, sur des entiers aléatoires inférieurs 2^63, et 100 millions de tests. Ca converge 😊

Total : 40007191 / 100000000

 #11 - 28-11-2022 01:00:22

Zindy
Passionné de Prise2Tete
Enigmes résolues : 48
Messages : 96

Paires orphelinees

Wouahou, très joli problème, et très jolie solution. Grâce à vous, je découvre que la fonction Zeta a un rapport avec les PGCD. Si seulement ça pouvait nous aider à trouver tous les zéros de la fonction Zeta !...

Merci Scarta pour l'énigme de haut vol, et les découvertes (pour moi) que cela a engendrées.

 #12 - 28-11-2022 09:56:19

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

Paires orpheline

Merci Zindy
A la base le problème était le suivant : est-il possible, à partir d'une paire donnée (a,b), d'arriver à la paire donnée (c,d). C'était un exercice de programmation.
Et pour la petite histoire, c'est un exercice qui est tout sauf simple : il y a la mauvaise méthode, la plutôt bonne et l'optimale

 

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 : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
21-12-2011 Enigmes Mathématiques
P2T
Timbré par perceval
09-06-2008 Enigmes Mathématiques
P2T
Optimisation level 2 par golgot59
20-10-2014 Enigmes Mathématiques
P2T
16-07-2010 Enigmes Mathématiques
P2T
Le chiffre 17 ... par NassClub
11-02-2011 Enigmes Mathématiques
P2T
Gâteau 74 par Vasimolo
03-04-2014 Enigmes Mathématiques
18-12-2010 Enigmes Mathématiques
P2T
Tesseract par dhrm77
12-07-2012 Enigmes Mathématiques
P2T
L'hotel de l'infini par supercab
04-11-2010 Enigmes Mathématiques

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