L'urne - solution

Dans une urne se trouvent un certain nombre de boules blanches et un certain nombre de boules noires.
On prend deux boules au hasard, la probabilité qu'elles soient toutes deux blanches est de p/q
Combien y a t-il de boules dans l'urne ?

( b(b-1)/2 ) / ( n(n-1)/2 ) = p/q ou encore : q·b(b-1) = p·n(n-1)
En posant v = 2b - 1 et u = 2n - 1 :
q(v² - 1) = p(u² - 1), u et v impairs. Soit :

p·u² - q·v² = -(q - p), avec u et v impairs
Nous supposerons la fraction p/q réduite, c'est à dire p et q premiers entre eux.

(u,v) = (±1,±1) est une solution évidente qui donne :
(n,b) = (1,1) sans intérêt, aucune façon de choisir deux boules parmi lesquelles aucune façon d'en avoir deux blanches !
(n,b) = (1,0) idem, et (0,0) non plus, (0,1) ne veut rien dire (une boule blanche dans un lot de zéro boules)

Ayant éliminé ces "solutions", il faut en chercher d'autres.
Divers cas se présentent selon les valeurs de p et q

p et q sont deux carrés

En changeant de notation : (p·u)² - (q·v)² = -(q² - p²) soit (p·u + q·v)(p·u - q·v) = -K
Il y a alors au plus un nombre fini de solutions, obtenues en recensant les diviseurs de K
Par exemple p = 1, q = 100, (u + 10v)(u - 10v) = -99 = -1·99 = -3·33 = -9·11,
et la seule solution convenable, outre (1,1), est u = 49, v = 5. C'est à dire n = 25, b = 3

p et q pas tous deux des carrés

Si (u,v) est une solution, (X·u + q·Y v, p·Y·u + X·v) aussi avec X² - p·q·Y² = 1
p·q ne peut pas être un carré puisque p et q premiers entre eux, et p et q pas tous deux des carrés.
L'équation de Pell X² - p·q·Y² = 1 a alors une infinité de solutions distinctes,
et il y a ainsi un nombre infini de solutions obtenues à partir de la solution (±1,1)

Il peut y avoir d'autres points de départ donnant aussi d'autres familles infinies de solutions.
Quoi qu'il en soit le nombre de ces solutions fondamentales est fini.
On obtient alors toutes les solutions récursivement en utilisant la solution fondamentale (P,Q) de
X² - p·q·Y² = 1 sur chacune des solutions fondamentales de p u² - q v² = -(q - p), soit :

u_n+1 = P·u_n + q·Q·v_n
v_n+1 = p·Q u_n + P·v_n
avec (P,Q) solution fondamentale de X² - p·q·Y² = 1

Reste à trouver toutes ces solutions fondamentales.
On en connait déja une (et même peut être deux) : (±1,1)

p=1, q pas un carré

On obtient une équation de Pell généralisée u² - q·v² = -(q - 1) = -K
Ses solutions fondamentales peuvent être obtenues par tâtonnement, ou par des méthodes générales comme l'algorithme LMM.

Par exemple q = 10 : u² - 10v² = -9.
La solution fondamentale de u² - 10v² = 1 est (19, 6), obtenue par tâtonnement ou par l'algorithme PQA
Les solutions fondamentales de u² - 10v² = -9 sont (u,v) = (±1,1) et (9,3), obtenues en essayant toutes les valeurs de v entre 1 et 6×√(|-9|/(2×(19-1))) = 3
ce qui donne les 3 familles de solutions :
(-1,1) (41,13) (1559,493) ... soit (n,b) = (0,1) (21,7) (780,247) ...
(1,1) (79,25) (3001,949) ... soit (n,b) = (1,1) (40,13) (1501,475) ...
(9,3) (351,111) (13329,4215) ... soit (n,b) = (5,2) (176,56) (6665,2108) ...
Les solutions remises dans l'ordre sont donc : (5,2) (21,7) (40,13) (176,56) (780,247) (1501,475) ...

Autre exemple q = 1000, u² - 1000v² = -999
La solution fondamentale de u² - 1000v² = 1 est (39480499, 1248483), avec PQA, car le tâtonnement...
Les solutions primitives de u² - 1000v² = -999 sont :
(±1,1) (±251,8) (±2751,87) (±42501,1344), avec LMM, ou le generic solver de Dario Alpern
Mais il faut u et v impairs. La solution (±251,8) ne convient pas.
u_n+1 = P u_n + q·Q v_n avec P impair, q pair conserve la parité de u impaire
v_n+1 = Q u_n + P v_n avec P, Q, u impairs donne une fois sur deux un nombre v impair.
Le même phénomène se produit avec les autres points de départ.
Il faut donc garder une solution sur deux, c'est à dire les relations de récurence (u_n+2, v_n+2) = (u_n, v_n)o(P, Q)o(P, Q) :
u_n+2 = (P² + q·Q²)u_n + 2q·P·Q·v_n = 3117419602578001 u_n + 98581463666034000 v_n
v_n+2 = 2P·Q·u_n + (P² + q·Q²)v_n = 98581463666034 u_n + 3117419602578001 v_n
La plus petite solution est donc (u,v) = (2751,87), ce qui conduit à (n,b) = (1376,44)
Les suivantes sont :
(u,v) = (-42501,1344)o(P,Q) = (464001, 14673) soit (n, b) = (232001, 7337)
(u,v) = (-251,8)o(P,Q) = (78258751, 2474759) soit (n, b) = (39129376, 1237380)
(u,v) = (251,8)o(P,Q) = (19897469249, 629213225) soit (n, b) = (9948734625, 314606613)
(u,v) = (42501,1344)o(P,Q) = (3355921839999, 106123566639)
(u,v) = (-2751,87)o(P,Q)² = (566012252877249, 17898879026553)
(u,v) = (-1,1)o(P,Q)² = (95464044063455999, 3018838138911967)
(u,v) = (1,1)o(P,Q)² = (101698883268612001, 3216001066244035)
(u,v) = (2751,87)o(P,Q)² = (17152608665637038751, 542413111969545621)...
etc...

Nota : q = 2 est le problème des soeurs Durand.
Le problème est aussi équivallent à : trouver deux nombres triangulaires dans le rapport q.

Cas général p≠1, p et q pas tous deux des carrés

p·u² - q·v² = -(q - p) = -K, avec u et v impairs
Effectuons le changement de variables u = m·v - K·w
(p·m² - q)v² - 2·m·p·K·v·w + p·K²·w² = -K
En choisisant m tel que (p·m² - q) soit multiple de K, on peut tout diviser par -K et obtenir une équation
A·v² + B·v·w + C·w² = 1 Dont les solutions sont parmi les réduites de t, racine de A·t² + B·t + C = 0

On recommence en divisant K par un de ses facteurs carrés r² s'il en a, et résoudre
p·u'² - q·v'² = -K/r² donnant les solutions v = r·v', u = r·u' de p (r·u')² - q (r·v')² = -K

Exemple p/q = 3/7, soit 3u² - 7v² = -4
Cherchons m tel que 3m² - 7 multiple de 4, c'est à dire m = 1 et 3.
pour m = 1 cela donne l'équation :
(3-7)v² - 2·3·4 v w + 3·4²w² = -4 soit v² + 6v w - 12w² = 1 et la solution v = 1, w = 0 soit u = 1
pour m = 3 cela donne l'équation :
(27-7)v² - 2·3·3·4 v w + 3·4²w² = -4 soit -5v² + 18v w - 12w² = 1 et la solution v = 1, w = 1 soit u = -1

Comme K est divisible par 2², cherchons les solutions de 3u'² - 7v'² = -1 ou 7v'² - 3u'² = 1
Celles-ci sont parmi les réduites de t, solution de 7t² - 3 = 0, c'est à dire de t = (√21)/7
Ces réduites sont 0/1, 1/1, 1/2, 2/3,... ce qui donne u' = 2, v' = 3 et donc u = 4, v = 6
et finalement les solutions fondamentales : (1, 1) (-1, 1) (4, 6)
La solution fondamentale de X² - 21Y² = 1 est (55,12)
Donc si (u,v) est solution, (55u + 84v, 36u + 55v) aussi
Pour en revenir au problème, il faut u et v impairs.
Les familles commençant à (±1, 1) ne donnent que des nombres impairs.
La famille commençant par (4, 6) ne donne que des nombres pairs et finalement la plus petite solution valable est
le successeur de (-1, 1) : u = 84-55 = 29 et v = 55 - 36 = 19 soit n = 15, b = 10 .
Les suivantes sont : (u,v) = (139, 91) (3191, 2089)... soit (n,b) = (70, 46) (1596, 1045)...