Solution de mai 2009 - Centrale des maths

Notre solution combine des idées de tous nos correspondants. Nous ne pouvons commencer avec a₁= 1, parce qu'il n'y aurait alors aucune façon de choisir a₂ en respectant la condition (ii). Posons plutôt a₁= 2, et utilisons la stratégie suivante:

Stratégie 1: Si a₁, a₂, ..., a_n sont déjà choisis, posons s_n = a₁ + a₂ + ... + a_n, et choisissons pour a_n+1 le plus petit diviseur de s_n qui n'est pas encore choisi.

Les premières valeurs de a_n sont données dans la table ci-haut. Pour n > 1 nous avons s_n > a₁, a₂, ..., a_n, donc il existe toujours un choix possible pour a_n+1, soit s_n (au pire). Clairement, une suite construite de telle manière respecte la condition (ii), mais la condition (i) pose problème. Nos correspondants ont repéré cette suite dans l'Encyclopédie en ligne des suites de nombres entiers http://www.research.att.com/~njas/sequences/index.html?language=french , où il est conjecturé que cette suite contient tous les nombres entiers. A moins de démontrer la conjecture, il est donc impossible de poursuivre indéfiniment avec la Stratégie 1.

Stratégie 2: Si a₁, a₂, ..., a_n sont déjà choisis, et l'entier N tarde à paraître, au point d'en inquiéter certains. Alors nous nous assurons d'abord d'avoir une somme s_n qui n'est pas une puissance de 2, quitte à utiliser la Stratégie 1 pour une étape supplémentaire si besoin est. Ensuite, nous commençons à donner aux nouveaux termes la forme a_k+1 = s_k jusqu'à ce qu'il soit possible d'atteindre un multiple de N en ajoutant des puissances de 2.

La première étape est donc de s'occuper de la situation particulière où s_n = 2^k. Notons qu'alors, il doit exister une puissance de 2 inférieure à 2^k qui n'est pas utilisée, car autrement nous aurions

qui impliquerait n = k+1 et un deuxième terme égal à 1, contradiction. Par conséquent, la Stratégie 1 donne un nouveau terme 2ⁱ tel que i < k, et la somme suivante 2^k + 2ⁱ n'est pas une puissance de 2.

Nous pouvons donc supposer que s_nn'est pas une puissance de 2, et nous nous appliquons à étendre la suite pour pouvoir y insérer N. Nous posons a_n+1 = s_n donc s_n+1 = 2s_n, puis a_n+2 = 2s_n et s_n+2 = 4s_n, et nous continuons à donner aux nouveaux termes la forme a_n+j = 2^j-1s_n pour obtenir to s_n+j = 2^js_n, jusqu'à ce que 2^j soit assez grand. Pour clarifier le sens que nous donnons à ``assez grand'', nous examinerons la suite des puissances de 2 modulo N.

Pour tout entier i, notons b_i le reste de la division de 2ⁱ par N. Puisqu'il n'existe qu'un nombre fini de restes possibles, il existe deux entiers i, k tels que b_i+k = b_i. Nous avons b_i+k+1 = b_i+1, b_i+k+2 = b_i+2, et la suite continue indéfiniment à faire le tour des termes b_i, b_i+1, ...,b_i+k-1. Nous avons alors b_i + b_i+1 + ... + b_i+k-1 ≡ 0 (mod N), puisqu'avec t = b_i + b_i+1 + ... + b_i+k-1, nous obtenons

2t = 2b_i + 2b_i+1 + ... + 2b_i+k-1 ≡ b_i+1 + b_i+2 + ... + b_i ≡ t (mod N)

donc t ≡ 0 (mod N).

Par ailleurs, s_n peut être représenté comme somme de puissances distinctes de 2, donc pour tout j > i, 2^js_n est congru modulo N à une somme de termes parmi b_i, b_i+1, ...,b_i+k-1. L'identité 2b_m ≡ b_m+1 (mod N) permet de simplifier la somme jusqu'à l'obtention d'une somme de termes distincts parmi b_i, b_i+1, ...,b_i+k-1 qui est congrue modulo N à 2^js_n. Notons b_m(1), ..., b_m(r) les termes parmi b_i, b_i+1, ...,b_i+k-1 qui ne sont pas utilisés dans cette somme. Si j est assez grand, nous pouvons choisir une suite décroissante 2^j > 2^e(1) > ... > 2^e(r) telle que 2^e(p) ≡ b_m(p) (mod N), et 2^e(1), ..., 2^e(r) n'apparaissent pas dans la suite a₁, a₂, ..., a_n. Puisque s_nn'est pas une puissance de 2, 2^e(1), ..., 2^e(r) ne font pas partie des termes suivants a_n+1 = s_n, ..., a_n+j = 2^j-1s_n. Donc nous pouvons poser a_n+j+1 = 2^e(1) , s_n+j+1 = 2^e(2)q₁, a_n+j+2 = 2^e(2) , s_n+j+1 = 2^e(3)q₂, ..., jusqu'à a_n+j+_r = 2^e(r). Nous avons alors

s_n+j+r = 2^js_n + 2^e(1) + ... + 2^e(r) ≡ 0 (mod N).

Nous pouvons donc choisir a_n+j+r+1 = N.