numeri che differiscono di 2

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Luke99
Messaggi: 12
Iscritto il: 12 giu 2015, 13:11

numeri che differiscono di 2

Messaggio da Luke99 »

Sia $ S $ l'insieme dei numeri naturali $ n $ verificanti le seguenti proprietá:
$ n $ ha 1000 cifre tutte dispari
Due qualsiasi cifre consecutive di $ n $ differiscono di + o -$ 2 $
Quanti sono gli elementi di $ S $ ?
Ilgatto
Messaggi: 38
Iscritto il: 24 ott 2017, 16:36

Re: numeri che differiscono di 2

Messaggio da Ilgatto »

Inizio considerando le cifre come coordinate di un oggetto, ricordando le condizioni su $n$: partendo dalla cifra più significativa considero una tabella con $1$ riga e $5$ colonne, se la cifra è $1$ allora l'oggetto è nella prima colonna, se è $3$ nella seconda ecc. Posso fare queste osservazioni:
  • Se considero $2$ cifre successive, esse indicheranno come coordinate due caselle adiacenti;
  • Il numero $n$ può essere definito come un percorso di $999$ passi nella tabella;
  • La cardinalità di $S$ è il numero di possibili percorsi differenti di $999$ passi, considerando un passo come il passaggio da una casella a una adiacente.
Numeriamo le $5$ caselle con i numeri da $1$ a $5$ (con grande fantasia) da sinistra a destra. Ora definiamo $f(a,b)$ il numero di percorsi nella nostra tabella composti da $b$ passi partendo dalla casella $a$. Ricaviamo semplicemente che, per $b>1$:
$f(1,b)=f(2,b-1)$
$f(2,b)=f(1,b-1)+f(3,b-1)$
$f(3,b)=f(2,b-1)+f(4,b-1)$
$f(4,b)=f(3,b-1)+f(5,b-1)$
$f(5,b)=f(4,b-1)$
E, ponendo $b=1$ otteniamo:
$f(1,1)=1$
$f(2,1)=2$
$f(3,1)=2$
$f(4,1)=2$
$f(5,1)=1$
La cardinalità di $S$ è quindi:
$$|S|= f(1,999)+f(2,999)+f(3,999)+f(4,999)+f(5,999)$$
Siccome non voglio fare tutti i conti a mano, provo solo a vedere come cresce il numero di percorsi in funzione del numero di passi e della casella di partenza. Costruisco una tabella in cui la riga equivale al numero di passi da fare e la colonna alla posizione di partenza. Ogni casella corrisponde quindi a $f(a,b)$ dove $a$ è la colonna e $b$ la riga. Se la sviluppo a mano con le formule dette sopra, noto che ogni $2$ passi il numero triplica, cioè che $f(a,b)=3f(a,b-2)$. Sembra comodo per risolvere il problema, quindi dimostriamolo costruendo parte della tabella:
$$|x|y|y|y|x|$$
$$|y|y+x|2y|y+x|y|$$
$$|y+x|3y|2x+2y|3y|y+x|$$
Scusate l'orrida grafica, ma non saprei come fare...
Comunque notiamo che mettendo il caso in cui le righe scritte siano le prime $3$, viene $x=1$ e $y=2$, da cui in particolare $y=2x$. A questo punto si nota che gli elementi della terza riga altro non sono che quelli della prima moltiplicati per $3$. Si può quindi continuare la tabella con $x=3$ e $y=6$ e così via. Notiamo quindi che la riga segnata con $k$,con $k$ che è un numero dispari, allora le sue caselle saranno:
$$|3^{\frac{k-1}{2}}|2*3^{\frac{k-1}{2}}|2*3^{\frac{k-1}{2}}|2*3^{\frac{k-1}{2}}|3^{\frac{k-1}{2}}|$$
Per $k=999$ avremo quindi:
$$|3^{499}|2*3^{499}|2*3^{499}|2*3^{499}|3^{499}|$$
Da cui si ricava che:
$|S|=8*3^{499}$
Spero non ci siano errori
Luke99
Messaggi: 12
Iscritto il: 12 giu 2015, 13:11

Re: numeri che differiscono di 2

Messaggio da Luke99 »

Tutto chiaro grazie, ero arrivato anche io a dire della tabella 5x1 ma non al fatto che triplicasse
Rispondi