OliForum Matematico

Sia S l'insieme dei numeri naturali n con le seguenti proprietà:
-n ha 1000 cifre tutte dispari
- due qualsiasi cifre consecutive di n differiscono di $ \pm 2 $
Determinare il numero di elementi di S.

Chiaramente questo problema viene dalla gara a premi 2007 di Parma, e dopo non averlo considerato per mesi l'ho risolto ieri mattina in pulman; la soluzione è abbastanza figa e nemmeno troppo difficile

dovrebbe essere così:
all'inizio ci sono 5 combinazioni
quindi si moltiplica per 2 e gli si sottrae 2(in caso siano 9 o 1)
e si fa lo stesso per 999 volte

scusate ma nn lo so scrivere in simboli

non va...ad esempio la terza cifra potrebbe essere 9 sia che la prima sia 5 sia che sia 9


Azz ho usato + volte la parola sia che tutte le altre messe assieme...

e ho calcolato anke quella!!!!!!!
all'inizio $ 5 $
dopo c'è $ 2*5-2 $
quindi $ 2(2*5-2)-2 $ cioè $ 5*2^2-6 $
e così via per 999 volte!

mmm... per dirla in parole povere, nella tua soluzione per ogni cifra finale ci sono due possibili cifre finali al secondo passo, escludendo ovviamente l'11 e il -1, quindi ne togli 2. Il problema è che al terzo passo le combinazioni che finiscono con 9 o 1 non sono più due, ma quattro. Infatti hai: 579;979;131;531. Sherlock intendeva questo. Quindi fino a $ 5\cdot2^2-6 $ va tutto bene, ma il passaggio dopo sarà $ 2(5\cdot2^2-6)-4 $ e non $ 2(5\cdot2^2-6)-2 $

notando che la sequenza è -2,-4,-6 etc posso scrivere la formula
(4*2^(n-1))-(2^(n-2))-(2*2^(n-3))-(3*2^(n-4))-(4*2^(n-5))-...((n-2)*2)
dove $ n $ è il numero delle cifre
(qualcuno lo scriva in latex, perkè nn ne sono capace)

exodd ha scritto:notando che la sequenza è -2,-4,-6 etc posso scrivere la formula
(4*2^(n-1))-(2^(n-2))-(2*2^(n-3))-(3*2^(n-4))-(4*2^(n-5))-...((n-2)*2)
dove $ n $ è il numero delle cifre
(qualcuno lo scriva in latex, perkè nn ne sono capace)

c'è una dimostrazione per quell' "etc"?
Perchè non sono stato a sviluppare i conti ma non mi pare venga così

hint:

provate a non cosiderare cifre singole...

in effetti, è vero
credevo venisse -2,-4,-6,-8,-10,-12, ma nn è così...

Non è che mi piaccia risolvere i miei stessi problemi però visto che nessuno se lo tange più metto l'idea...

Sia $ ~f_k $ il numero di interi aventi k cifre, godenti delle proprietà 2 e 3 dell'ipotesi e terminanti per 1 o 9; $ ~g_k $ di queli terminanti per 3 o 7 e $ ~h_k $ di quelli terminanti per 5.
non è difficile vedere che valgono le seguenti ricorsioni:

$ f_k=g_{k-1} $ poichè l'1 si ottiene solo dal 3 e il 9 dal 7
$ g_k=f_{k-1}+2h_{k-1} $ piochè il 3 lo si ottiene dall'1 e dal 5 ed il 7 dal 5 e dal 9
$ h_k=g_{k-1} $ poichè il 5 lo si ottiene o dal 3 o dal 7

di conseguenza $ g_k=3g_k-2 $

a questo punto abbiamo

$ f_{1000}=h_{1000}=3^{499}g_1 $

$ g_{1000}=3^{499}g_2 $

e valutando a mano $ ~g_1 $ e $ ~g_2 $ abbiamo finito