k|gcd(n,f(n))

[jordan]

Per ogni intero positivo n, sia f(n) l'intero positivo scritto al contrario, cioè letto da destra verso sinistra (e.g. f(10020)=2001 e f(123)=321).
Problema. Trovare tutti gli interi positivi k tali che esistono infiniti interi positivi n che soddisfano k|gcd(n,f(n)).

[FeddyStra]

Sia $ \overline{n} $ il numero che si ottiene rovesciando $ n $. Distinguiamo alcuni casi:

• $ k=1 $. No comment.
• $ k=2^a $. $ \displaystyle n = \overline{k}\underbrace{00\dots00}_{\ge a}k $.
• $ k=5^a $. $ \displaystyle n = \overline{k}\underbrace{00\dots00}_{\ge a}k $.
• $ 10 \mid k $. Non è possibile perchè $ 10 \nmid \overline{n} $ per ogni $ n $.
• $ (k,10)=1 $. Esistono infiniti multipli di $ k $ formati da sole cifre $ 1 $.

[Davide90]

• $ (k,10)=1 $. Esistono infiniti multipli di $ k $ formati da sole cifre $ 1 $.

Il resto della dimostrazione è ok, ma questo fatto come si dimostra? In gara non credo che si possa lasciare senza spiegazione....

[g(n)]

Hint: pigeonhole!

[FeddyStra]

• $ (k,10)=1 $. Esistono infiniti multipli di $ k $ formati da sole cifre $ 1 $.

Il resto della dimostrazione è ok, ma questo fatto come si dimostra? In gara non credo che si possa lasciare senza spiegazione....

Hint: pigeonhole!

Il mio voleva essere solo un hint per la soluzione. Inoltre, la dimostrazione è molto semplice, come suggerito da g(n).

[jordan]

Sia $ \overline{n} $ il numero che si ottiene rovesciando $ n $. Distinguiamo alcuni casi:

• $ k=1 $. No comment.
• $ k=2^a $. $ \displaystyle n = \overline{k}\underbrace{00\dots00}_{\ge a}k $.
• $ k=5^a $. $ \displaystyle n = \overline{k}\underbrace{00\dots00}_{\ge a}k $.
• $ 10 \mid k $. Non è possibile perchè $ 10 \nmid \overline{n} $ per ogni $ n $.
• $ (k,10)=1 $. Esistono infiniti multipli di $ k $ formati da sole cifre $ 1 $.

Hai saltato i due casi piu importanti..

[Davide90]

Forse ho capito: indichiamo i numeri $ n $ costituiti da $ j $ cifre "uno" con $ a_j $ . Dunque $ a_j=\dfrac{10^{j+1}-1}{9} $ .
Allora (se non sto prendendo un abbaglio, su questi argomenti non sono troppo ferrato), se prendiamo k numeri consecutivi $ a_j $ , essi cosituiscono una classe di resto modulo k, poichè$ 10 \nmid k $, quindi esiste uno di essi che è multiplo di k.
È giusto?

[FeddyStra]

Forse ho capito: indichiamo i numeri $ n $ costituiti da $ j $ cifre "uno" con $ a_j $ . Dunque $ a_j=\dfrac{10^{j+1}-1}{9} $ .
Allora (se non sto prendendo un abbaglio, su questi argomenti non sono troppo ferrato), se prendiamo k numeri consecutivi $ a_j $ , essi cosituiscono una classe di resto modulo k, poichè$ 10 \nmid k $, quindi esiste uno di essi che è multiplo di k.
È giusto?

Più o meno. Prendine $ k+1 $. Per pigeonole due di essi sono congrui fra loro. Se li sottrai ottieni un numero fatto da un po' di cifre $ 1 $ e terminante con alcuni $ 0 $. Visto che $ (10,k)=1 $, gli zeri finali li puoi togliere.

Hai saltato i due casi piu importanti..

Non voglio mica rubare il divertimento agli altri!

[kn]

O anche: preso l'inverso di $ \displaystyle~10\pmod k $ (che chiamiamo $ \displaystyle~r $) è facile mostrare che ci sono infiniti polinomi che hanno $ \displaystyle~10 $ e $ \displaystyle~r $ come radici $ \displaystyle~\pmod k $ e i coefficienti compresi tra $ \displaystyle~0 $ e $ \displaystyle~9 $ (a parte quello direttivo che deve essere tra $ \displaystyle~1 $ e $ \displaystyle~9 $). Sostituendo $ \displaystyle~x=10 $ abbiamo un numero buono, infatti il numero al contrario non è altro che il nostro polinomio rovesciato valutato in $ \displaystyle~10 $, ma questo ammette $ \displaystyle~\pmod k $ gli inversi delle radici del nostro polinomio (fra cui $ \displaystyle~r $).

Per i casi non considerati da Freddy ci devo ancora pensare...

[jordan]

(n,10)=1 allora n| (10^(φ(9n))-1) /9, senonchè il pigenhole è più efficiente (in termini di numeri di cifre), e comunque ne sono sufficienti k, non k+1

@Feddy: non avevo inteso che con "alcuni" intendevi "non tutti"