k|gcd(n,f(n))

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

k|gcd(n,f(n))

Messaggio da jordan » 20 set 2009, 22:39

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)).
The only goal of science is the honor of the human spirit.

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 20 set 2009, 23:52

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 $.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
Davide90
Messaggi: 200
Iscritto il: 12 mag 2008, 20:05
Località: Padova / Modena
Contatta:

Messaggio da Davide90 » 21 set 2009, 09:30

FeddyStra ha scritto:
  • $ (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....
"[L'universo] è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche; [...] senza questi è un aggirarsi vanamente per un oscuro laberinto." Galileo Galilei, Il saggiatore, 1623
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]

g(n)
Messaggi: 109
Iscritto il: 14 ott 2007, 19:24
Località: Codroipo, il paese più anagrammato d'Italia

Messaggio da g(n) » 21 set 2009, 11:14

Hint: pigeonhole!

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 21 set 2009, 13:35

Davide90 ha scritto:
FeddyStra ha scritto:
  • $ (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) ha scritto:Hint: pigeonhole!
Il mio voleva essere solo un hint per la soluzione. Inoltre, la dimostrazione è molto semplice, come suggerito da g(n).
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 21 set 2009, 15:14

FeddyStra ha scritto: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.. :roll:
The only goal of science is the honor of the human spirit.

Avatar utente
Davide90
Messaggi: 200
Iscritto il: 12 mag 2008, 20:05
Località: Padova / Modena
Contatta:

Messaggio da Davide90 » 21 set 2009, 15:15

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? :roll:
"[L'universo] è scritto in lingua matematica, e i caratteri son triangoli, cerchi, ed altre figure geometriche; [...] senza questi è un aggirarsi vanamente per un oscuro laberinto." Galileo Galilei, Il saggiatore, 1623
[tex] e^{i\theta}=\cos \theta +i \sin \theta[/tex]

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 21 set 2009, 15:37

Davide90 ha scritto: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? :roll:
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.
jordan ha scritto:Hai saltato i due casi piu importanti.. :roll:
Non voglio mica rubare il divertimento agli altri! :)
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 21 set 2009, 15:55

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...
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 21 set 2009, 16:51

(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 :o

@Feddy: non avevo inteso che con "alcuni" intendevi "non tutti" :lol:
The only goal of science is the honor of the human spirit.

Rispondi