Ecco un esercizio del test francese per selezionare la squadra delle OIM. Se non capite, posso fare una traduzione.
Exercice 1 :
Soit $ a $ un entier naturel.
On note $ a' $ le nombre dont l'écriture en base 10 est l'inverse de celle de $ a $.
Par exemple, si $ a = 4320 $, alors $ a'= 0234 = 234 $.
On définit la suite $ (a_n)_{n\in \mathbb{N*}} $ par son premier terme, $ a_1 $ naturel non nul, et la relation: $ a_{i+1}=a_i + a'_i $ .
$ a_7 $ peut-il être premier?
France TST 2007 numero 1
Allora...
Tesi: $ a_7 $ sarà sempre divisibile per 11.
Dimostriamo:
Lemma 1: Se nella successione vi è un termine $ a_n $ con un numero pari di cifre allora $ a_{n+1} $ sarà divisibile per 11.
Infatti le cifre di posto pari di $ a_n $ diventano le cifre di posto dispari di $ a'_n $ e viceversa. Detta $ S_d $ la somma delle cifre di posto dispari di $ a_n $ e detta $ S_p $ la somma delle cifre di posto pari di $ a_n $ avremo che $ S_d $ è la somma delle cifre di posto pari di $ a'_n $ e $ S_p $ la somma delle cifre di posto dispari di $ a'_n $. Quindi la somma delle cifre di posto pari di $ a_n+a'_n $ sarà pari a $ S_p + S_d $ e la somma delle cifre di posto dispari di $ a_n+a'_n $ sarà pari a $ S_d+S_p $. Quindi, per il noto criterio di divisibilità, avremo che $ a_{n+1} $ sarà divisibile per 11.
Lemma 2: Se un termine della successione $ a_n $ è divisibile per 11, allora tutti i termini che lo seguono saranno divisibili per 11.
Se $ a_n $ è divisibile per 11, anche $ a'_n $ lo sarà e quindi anche $ a_n+a'_n=a_{n+1} $.
Lemma 3: La prima cifra di $ a_{n+1} $ sarà pari alla somma tra la prima e l'ultima cifra di $ a_n $.
Banalissimo, serve solo a fare un po' d'ordine scriverlo.
Ora se tra $ a_1 $ e $ a_5 $ vi è un termine con un numero pari di cifre, allora la tesi è dimostrata. Se invece tutti i termini tra $ a_1 $ e $ a_5 $ hanno un numero dispari di cifre, esse avranno lo stesso numero di cifre, in quanto un termine non può essere 10 volte il termine precedente.
Detta A la prima cifra di $ a_1 $ e B l'ultima, la prima e l'ultima cifra di $ a_2 $ saranno uguali. Chiamiamola C. La prima e l'ultima cifra di $ a_3 $ saranno uguali a $ D=2*C $; la prima e l'ultima cifra di $ a_4 $ saranno uguali a $ E=2*D=4*C $;la prima e l'ultima cifra di $ a_5 $ saranno uguali a $ F=2*E=4*D=8*C $.
Ora la somma tra la prima e l'ultima cifra di $ a_5 $ sarà uguale a $ 2*F=16*C $. Ora, poichè 16*C non può mai essere minore di 10, avremo che $ a_6 $ ha un numero pari di cifre e per il lemma 1, $ a_7 $ sarà divisibile per 11.
Scusatemi per la lunghezza e per la probabile difficoltà della sol dovuta alla mia incapacità nello scrivere...
Tesi: $ a_7 $ sarà sempre divisibile per 11.
Dimostriamo:
Lemma 1: Se nella successione vi è un termine $ a_n $ con un numero pari di cifre allora $ a_{n+1} $ sarà divisibile per 11.
Infatti le cifre di posto pari di $ a_n $ diventano le cifre di posto dispari di $ a'_n $ e viceversa. Detta $ S_d $ la somma delle cifre di posto dispari di $ a_n $ e detta $ S_p $ la somma delle cifre di posto pari di $ a_n $ avremo che $ S_d $ è la somma delle cifre di posto pari di $ a'_n $ e $ S_p $ la somma delle cifre di posto dispari di $ a'_n $. Quindi la somma delle cifre di posto pari di $ a_n+a'_n $ sarà pari a $ S_p + S_d $ e la somma delle cifre di posto dispari di $ a_n+a'_n $ sarà pari a $ S_d+S_p $. Quindi, per il noto criterio di divisibilità, avremo che $ a_{n+1} $ sarà divisibile per 11.
Lemma 2: Se un termine della successione $ a_n $ è divisibile per 11, allora tutti i termini che lo seguono saranno divisibili per 11.
Se $ a_n $ è divisibile per 11, anche $ a'_n $ lo sarà e quindi anche $ a_n+a'_n=a_{n+1} $.
Lemma 3: La prima cifra di $ a_{n+1} $ sarà pari alla somma tra la prima e l'ultima cifra di $ a_n $.
Banalissimo, serve solo a fare un po' d'ordine scriverlo.
Ora se tra $ a_1 $ e $ a_5 $ vi è un termine con un numero pari di cifre, allora la tesi è dimostrata. Se invece tutti i termini tra $ a_1 $ e $ a_5 $ hanno un numero dispari di cifre, esse avranno lo stesso numero di cifre, in quanto un termine non può essere 10 volte il termine precedente.
Detta A la prima cifra di $ a_1 $ e B l'ultima, la prima e l'ultima cifra di $ a_2 $ saranno uguali. Chiamiamola C. La prima e l'ultima cifra di $ a_3 $ saranno uguali a $ D=2*C $; la prima e l'ultima cifra di $ a_4 $ saranno uguali a $ E=2*D=4*C $;la prima e l'ultima cifra di $ a_5 $ saranno uguali a $ F=2*E=4*D=8*C $.
Ora la somma tra la prima e l'ultima cifra di $ a_5 $ sarà uguale a $ 2*F=16*C $. Ora, poichè 16*C non può mai essere minore di 10, avremo che $ a_6 $ ha un numero pari di cifre e per il lemma 1, $ a_7 $ sarà divisibile per 11.
Scusatemi per la lunghezza e per la probabile difficoltà della sol dovuta alla mia incapacità nello scrivere...