Potenze di due
Dimostrare che $forall k in NN \quad EE n in NN \quad | \quad 2^n \mbox{ ha esattamente }k \mbox{ cifre uguali a nove}$.
[Ci ho provato per giorni ma non ne vengo a capo!
]
Ciao
[Ci ho provato per giorni ma non ne vengo a capo!
]Ciao
Risposte
Io ho provato per induzione; la base è OK ma il passo induttivo non riesco a risolverlo. 
Avevo visto il problema (ha quasi un mese 'sto post), ma non mi sembra facile per niente - o almeno non intuitivo. Pensavo di partire dalle ripetizioni delle cifre nelle potenze di due in base decimale.
La cifra meno significativa non è mai 9 - è sempre ciclicamente 2-4-8-6... La seconda ha ciclo 1-3-6-2-5-1-2-4-9-9-8-6-3-7-4-8-7-5-0-0 (almeno un nove c'è). E' possibile calcolare quante sono e anche quali, e credo si possa dimostrare che c'è sempre almeno un nove.
Già qui mi sembrava rognoso, e dovremmo poi dimostrare che è sempre possibile trovare un ciclo con esattamente 'k' nove. E quindi forse la strada non è questa...
La cifra meno significativa non è mai 9 - è sempre ciclicamente 2-4-8-6... La seconda ha ciclo 1-3-6-2-5-1-2-4-9-9-8-6-3-7-4-8-7-5-0-0 (almeno un nove c'è). E' possibile calcolare quante sono e anche quali, e credo si possa dimostrare che c'è sempre almeno un nove.
Già qui mi sembrava rognoso, e dovremmo poi dimostrare che è sempre possibile trovare un ciclo con esattamente 'k' nove. E quindi forse la strada non è questa...
Basandomi sulla tua idea di vedere i cicli delle cifre, ho scoperto (empiricamente) una interessantissima proprietà:
la prima cifra fa 2486 e quindi un ciclo di lunghezza 4
la seconda cifra fa quello che hai scritto tu e quindi un ciclo di lunghezza 20=4*5
la terza cifra fa un ciclo di lunghezza 100=20*5
la quarta cifra fa un ciclo di lunghezza 500=100*5
la quinta cifra idem 2500=500*5
Non ho verificato oltre, ma sembra troppo preciso per essere casuale!
Ora, c'è da vedere come questo possa servire a dimostrare l'esercizio, ma comunque questa cosa è un fatto noto?? (sto pensando a come si può dimostrare...)
la prima cifra fa 2486 e quindi un ciclo di lunghezza 4
la seconda cifra fa quello che hai scritto tu e quindi un ciclo di lunghezza 20=4*5
la terza cifra fa un ciclo di lunghezza 100=20*5
la quarta cifra fa un ciclo di lunghezza 500=100*5
la quinta cifra idem 2500=500*5
Non ho verificato oltre, ma sembra troppo preciso per essere casuale!
Ora, c'è da vedere come questo possa servire a dimostrare l'esercizio, ma comunque questa cosa è un fatto noto?? (sto pensando a come si può dimostrare...)
"gygabyte017":
Non ho verificato oltre, ma sembra troppo preciso per essere casuale!
Ora, c'è da vedere come questo possa servire a dimostrare l'esercizio, ma comunque questa cosa è un fatto noto??
Certo che è noto e non casuale
. E lo puoi anche dimostrare, se ti va di farlo.Il difficile si fa adesso, se proseguiamo su questa strada. Forse dovremmo cercare una base di induzione (ma la vedo dura).
Questo implica che non è possibile combinare tra loro tutti gli elementi tra due ordini decimali, cosa che sarebbe stata possibile se facendo la divisione tra il numero di cifre di un ordine decimale e quello delle cifre dell'ordine decimale inferiore, ci sarebbe stato un resto che non divide perfettamente il divisore (eccetto 1 chiaramente).
"gygabyte017":
Basandomi sulla tua idea di vedere i cicli delle cifre, ho scoperto (empiricamente) una interessantissima proprietà:
la prima cifra fa un ciclo di lunghezza $4$
la seconda cifra fa quello che hai scritto tu e quindi un ciclo di lunghezza $20=4*5$
la terza cifra fa un ciclo di lunghezza $100=20*5$
la quarta cifra fa un ciclo di lunghezza $500=100*5$
la quinta cifra idem $2500=500*5$
Si può anche vedere così (per avere un po' più ordine):
- La prima cifra fa un ciclo di lunghezza $4=4*1$ che si può scrivere come $4*5^0$
- La seconda cifra fa un ciclo di lunghezza $20=4*5=4*5^1$
- La terza cifra fa un ciclo di lunghezza $100=4*5^2$
- La terza cifra fa un ciclo di lunghezza $500=4*5^3$
- La quarta cifra fa un ciclo di lunghezza $2500=4*5^4$
Quindi la proprietà da dimostrare potrebbe essere questa:
La $n$-esima cifra fa un ciclo di lunghezza $4*5^(n-1)$
Resta "solo" da dimostrarla (magari per induzione visto che la base è già dimostrata). Ora ci provo anch'io
Tutto giusto, ma non vorrei l'idea (che ho proposto io :\) ci portasse in un vicolo cieco.
Dimostrare quanto è lungo il ciclo è facile; ma il problema rimane:
- c'è un nove, almeno un nove, almeno $x$ nove (cifra) sempre in ogni ciclo?
- è sempre possibile "combinare" i cicli di modo da avere esattamente $k$ nove (e deve valere $forall k in NN$)?
Forse per la seconda ipotesi si può fare qualcosa. Ma finora non ho trovato dimostrazione per la prima...
Dimostrare quanto è lungo il ciclo è facile; ma il problema rimane:
- c'è un nove, almeno un nove, almeno $x$ nove (cifra) sempre in ogni ciclo?
- è sempre possibile "combinare" i cicli di modo da avere esattamente $k$ nove (e deve valere $forall k in NN$)?
Forse per la seconda ipotesi si può fare qualcosa. Ma finora non ho trovato dimostrazione per la prima...
In teoria sarebbe sufficiente dimostrare la seconda. Il problema è che non è possibile associare ad un ciclo, tutti gli elementi di un altro ciclo, quindi le cose si complicano.
Non credo sia una cosa immediatissima.
Basta guardare le prime potenze di [tex]$2$[/tex] (qui fino a [tex]$2^{33}$[/tex]): un solo [tex]$9$[/tex] si presenta in [tex]$2^{12}$[/tex]; tre soli [tex]$9$[/tex] si presentano in [tex]$2^{32}$[/tex] ma soli due [tex]$9$[/tex] si presentano dopo, cioè in [tex]$2^{34}$[/tex] (e la prima potenza con soli tre [tex]$9$[/tex] dopo [tex]$2^{34}$[/tex] è [tex]$2^{49}$[/tex]); cinque soli [tex]$9$[/tex] stanno in [tex]$2^{54}$[/tex] ma quattro [tex]$9$[/tex] vengono solo in [tex]$2^{83}$[/tex]...
Insomma, almeno ad una prima ingenua occhiata, non sembra una struttura molto adatta ad una dimostrazione per induzione.
Forse ci vuole qualche trucco aritmetico, tipo qualche conto modulo qualcosa... Oppure una rappresentazione in una base diversa...
Ma sono idee da profano.
@gygabyte017: Giusto per curiosità, dove l'hai preso il problema?
Basta guardare le prime potenze di [tex]$2$[/tex] (qui fino a [tex]$2^{33}$[/tex]): un solo [tex]$9$[/tex] si presenta in [tex]$2^{12}$[/tex]; tre soli [tex]$9$[/tex] si presentano in [tex]$2^{32}$[/tex] ma soli due [tex]$9$[/tex] si presentano dopo, cioè in [tex]$2^{34}$[/tex] (e la prima potenza con soli tre [tex]$9$[/tex] dopo [tex]$2^{34}$[/tex] è [tex]$2^{49}$[/tex]); cinque soli [tex]$9$[/tex] stanno in [tex]$2^{54}$[/tex] ma quattro [tex]$9$[/tex] vengono solo in [tex]$2^{83}$[/tex]...
Insomma, almeno ad una prima ingenua occhiata, non sembra una struttura molto adatta ad una dimostrazione per induzione.
Forse ci vuole qualche trucco aritmetico, tipo qualche conto modulo qualcosa... Oppure una rappresentazione in una base diversa...
Ma sono idee da profano.
@gygabyte017: Giusto per curiosità, dove l'hai preso il problema?
"gugo82":
Insomma, almeno ad una prima ingenua occhiata, non sembra una struttura molto adatta ad una dimostrazione per induzione.
Forse ci vuole qualche trucco aritmetico, tipo qualche conto modulo qualcosa...
Il "modulo qualcosa" ci permette di trovare le cifre '9' all'interno dei cicli
E' l'unica cosa che mi era venuta in mente... cercare una dimostrazione per induzione non sul numero ma semmai sulle cifre (e/o sull'esponente); più che ci penso, più mi sembra terribilmente complicato - ma forse mi manca l'idea, tutto qua.
A 'sto punto sono curioso anche io di sapere da dove viene questo problema: è una invenzione della mente contorta dell'autore (scherzo, eh?
), o che altro?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo