Solution au problème de novembre 2007

Le problème:
	Démontrez que pour tout n, on peut partitionner les entiers 1, 2, 3, ..., 2n-1, 2n en paires {a1, b1}, {a2, b2}, ... , {an, bn} telles que ai + bi est premier pour tout i.

Réponses correctes:

Nous avons reçu des solutions correctes de Bojan Basic (Serbie) Wolfgang Kais (Allemagne) Gérard Billion (France) Jeremy Lam (Grande Bretagne) Lou Cairoli (États-Unis) Jacques Mertzeisen (France) John Campbell (Alberta) Viktor Pačnik  (Slovénie) Adrien Delcour (Belgique) Mark Pilloff (États-Unis) Philippe Fondanaiche (France) Ananda Raidu (Inde) Alenka Gabrovec (Slovénie) John T. Robinson (États-Unis) Xavier Hecquet (France) Heri Setiyawan (Indonésie) Pierre Bornsztein (France) Luis Fabricio Tano (internet) Jean-Luc Luyet (Suisse)

La solution:

Toutes les solutions utilisaient le "Postulat de Bertrand'':
Pour tout entier n, il existe un nombre premier p entre n et 2n.

L'appellation "postulat'' est demeurée bien qu'il ait été démontré par Tchebytcheff en 1850. Wikipédia http://fr.wikipedia.org/wiki/D%C3%A9monstration_du_postulat_de_Bertrand
donne la démonstration simple obtenue plus tard par Paul Erdös.

Solution. Nous reproduisons la solution de Pierre Bornsztein

"On va raisonner par récurrence (forte) sur n.

Pour n = 1, la conclusion est évidente.

Soit n >= 2 fixé et supposons que l'on puisse effectuer un tel couplage pour {1,...,2k} où k = 1,...,n-1.
D'après le Postulat de Bertrand, démontré par Tchebytcheff, il existe un nombre premier p entre 2n et 4n. Puisque p > 2 est impair, il existe un entier a dans {1,...,2n-1} tel que p = a + 2n.
On forme alors tous les couples (a,2n), (a+1, 2n-1),..., ( (p-1)/2 , (p+1)/2 ). Ces couples vérifient la propriété désirée.

Si a = 1, c'est fini, on a trouvé un couplage adéquat de {1,...,2n}.
Si a > 1, il convient de remarquer que a est nécessairement impair. On achève alors la construction du couplage en utilisant un tel couplage sur {1,...,a-1}, qui existe d'après l'hypothèse de récurrence.
Ainsi, dans tous les cas, on a trouvé un couplage adéquat sur {1,...,2n}, ce qui achève la preuve.''

Commentaire: Xavier Hecquet note "Assez déçu de devoir passer par un théorème pour y arriver… Je persiste cependant mes recherches pour trouver un autre moyen.'' Y parviendra-t-il? En fait, notre problème du mois est presque équivalent au Postulat de Bertrand. En effet, tout nombre pair m = 2n doit être jumelé à un nombre a < 2n tel que m+a est un premier entre m et 2m. De même, tout nombre impair m=2n-1 doit être jumelé à un nombre a < 2n-1 tel que m + a est un premier entre m et 2m, à moins que m ne soit forcé d'être jumelé à m + 1 = 2n, et les autres paires soient {1, 2n-2}, {2, 2n-3}, ..., {n-1, n}. Dans ce cas, m = 2n-1 est un nombre premier tel que 2m + 1 est également premier. De tels premiers sont appelés "premiers de Sophie Germain''. On ne sait pas encore si il existe une infinité de premiers de Sophie Germain. Donc, si les recherches de Hecquet sont fructueuses, il obtiendra une démonstration alternative du Postulat de Bertrand, qui est valide pour tous les nombres sauf les premiers de Sophie Germain.

Post-Scriptum

Les postes canadiennes nous ont finalement livré la jolie carte postale de Jean-Luc Luyet de Suisse. Luyet n'utilise pas le postulat de Bertrand, mais plutôt la conjecture de Goldbach:

Tout nombre pair supérieur à 2 est la somme de deux nombres premiers.

Il note que si 4n n'est pas un contre-exemple à cette conjecture, alors 4n est la somme
de deux nombres premiers, dont le plus grand est de la forme 2n+k. Il forme ainsi les couples {k, 2n}, {k+1, 2n-1}, ... et complète sa partition en utilisant une récurrence,
comme nos autres correspondants.

Contrairement au postulat de Bertrand, la conjecture de Goldbach formulée en 1742 demeure non-résolue jusqu'à ce jour. C'est en fait un des problèmes ouverts les plus célèbres de la théorie des nombres. En soi, un argument qui s'appuie sur une conjecture non-résolue n'est pas une démonstration. Par contre, relier une célèbre conjecture à notre modeste problème du mois, ça c'est un geste vraiment sympathique, tout comme la carte!