Successione simpatica

[MathematicalMind]

Tratto da una recente gara olimpica.

Sia $a_n$ una successione definita da $a_{10}=10$ e $a_n=100a_{n-1}+n$ per ogni $n\geq11$. Trovare il più grande $n\leq100$ per cui $a_n$ è divisibile per $99$.

[axpgn]

$n=89$

[MathematicalMind]

La risposta è esatta, ma per una soluzione completa serve la dimostrazione

[axpgn]

Mica l'hai chiesto .. ... appena ho un po' di tempo ...

[axpgn]

Vediamo se così ti piace ...

Divisibile per $99$ vuol dire divisibile sia per $9$ che per $11$.,
Ogni $a_n$ non è altro che la "scrittura in fila su un'unica riga" di tutti gli interi fino a $n$ (per la divisibilità $100$ è come il $97$).
Il primo $a_n$ divisibile per nove è $a_(17)$; la somma di nove interi consecutivi è divisibile per nove perciò anche $a_(26)$ lo è e cosi via fino a $a_(98)$; anche $a_(18)$ lo è dato che aggiungiamo le cifre $1$ e $8$, e per lo stesso discorso di prima lo sono anche $a_(27)$ via via fino a $a_(99)$.
Il primo $a_n$ divisibile per undici è $a_(12)$; dato che $100-=1 mod 11$ e che $n-=r mod 11$ dove $r$ è il resto della divisione di $n$ per undici allora $100n-=r mod 11$; da ciò si deduce che un numero composto mettendo in fila undici interi consecutivi è divisibile per undici dato che sarebbe la somma di tutti i resti (da zero a dieci) ovvero $55$; di conseguenza anche $a_(23)$ è divisibile per undici e cosi via fino a $a_(89)$; si nota poi che anche $a_(20)$ è divisibile per undici e per lo stesso ragionamento precedente si arriva a $a_(97)$
Il maggiore in comune è $a_(89)$

Cordialmente, Alex

[MathematicalMind]

Un po' bizzarra, ma buona

[veciorik]

$a_n-a_{n-1} = 99 a_{n-1} + n$

Le seguenti sono equivalenze modulo 99:

$a_n-a_{n-1} \equiv n$
$a_n-a_{10} \equiv \sum_{11}^{n} i$
$a_n \equiv \sum_{10}^{n} i \equiv ((n+10)(n-9))/2 $
$a_n \equiv n+10 \qquad \text{se} \quad n \quad \text{dispari}$
$a_n \equiv n- \ \ 9 \qquad \text{se} \quad n \quad \text{pari}$

$max(n+10 \le 100+10) \equiv 99 \qquad \Rightarrow \qquad n+10 =99 \qquad \Rightarrow \qquad n=89 \quad \text{dispari}$

[MathematicalMind]

"veciorik":

$a_n \equiv \sum_{10}^{n} i \equiv ((n+10)(n-9))/2 $
$a_n \equiv n+10 \qquad \text{se} \quad n \quad \text{dispari}$
$a_n \equiv n- \ \ 9 \qquad \text{se} \quad n \quad \text{pari}$

Fin qui era ottima, ma questo non mi torna... $n=53$ per esempio?

[veciorik]

Provo ad esser più rigoroso, sperando di riuscirci:

Riparto da $ \quad a_n \equiv ((n+10)(n-9))/2 \quad $ per trovare il [hl]massimo[/hl] $ n \le 100 \ $ tale che $ \quad a_n \equiv 99$

Pongo $ \quad k=n+10 \quad \Rightarrow \quad n-9=k-19 $

Cerco $ \quad k \le 110 \quad $ tale che $ \quad k(k-19) \equiv 99 \quad $ trascurando il divisore $ \ 2 \ $ ché uno dei fattori è sicuramente pari

Poiché $ \quad 99=11*3*3 \quad $ scendo da $ \quad k=110 \quad $ cercando multipli di $11$ e/o di $9$

Salto i multipli di $ \ 3 \ $ non multipli di $ \ 9 \ $ perché $ \ k \quad $ e $ \quad k-19 \ $ non possono essere entrambi multipli di $ \ 3 $

Scarto $ \ k=110 \ $ e $ \ k=108 \quad $ e mi fermo a $ \quad k=99 \quad $ che soddisfa i requisiti

Ergo [hl]$ \quad n=k-10=89 $[/hl]

[MathematicalMind]

Volendo proprio mettere i puntini sulle i sarebbe da escludere il caso $99$ divide $k-19$ ma qui non si verifica e tutto sommato è una dimostrazione che va bene.
PS: ma perché \mid non produce la barretta verticale di "divide"?

[veciorik]

"MathematicalMind":Volendo proprio mettere i puntini sulle i sarebbe da escludere il caso \(99 \mid k-19\) ma qui non si verifica e tutto sommato è una dimostrazione che va bene.

Non capisco: il caso è escluso implicitamente dalla condizione $ k \le 110 $ ossia $ k-19 \le 91 $

[veciorik]

"MathematicalMind":PS: ma perché \mid non produce la barretta verticale di "divide"?

Con i $ non funziona, non so perché, chiediamolo a Stan, ma puoi scrivere

[bgcolor=#BFFFFF]\( ... \mid ... )\[/bgcolor]

[MathematicalMind]

"veciorik":[quote="MathematicalMind"]Volendo proprio mettere i puntini sulle i sarebbe da escludere il caso \(99 \mid k-19\) ma qui non si verifica e tutto sommato è una dimostrazione che va bene.

Non capisco: il caso è escluso implicitamente dalla condizione $ k \le 110 $ ossia $ k-19 \le 91 $[/quote]
A parte il caso $k=19$ che tuttavia non si arriva ad esaminare, è una cosa che per essere precisi andrebbe detta per giustificare la validità del tuo processo di cercare $k$ multiplo di $9$ o di $11$.

[Erasmus_First]

"MathematicalMind":Sia $a_n$ una successione definita da $a_{10}=10$ e $a_n=100a_{n-1}+n$ per ogni $n\geq11$. Trovare il più grande $n\leq100$ per cui $a_n$ è divisibile per $99$.

Datemi pure del "pignolo": ma la "restrizione" «per ogni $n≥11$» è in più (ed era meglio dire tout-court «per ogni n»).
[Di questa sequenza rlevante è il fatto che è $a_9=0$ e che per $n < 9$ i termini della sequenza ${a_n}$ sono negativi, maggiori di -1/10 e crescenti al calare di $n$ (e che $a_n$ tende a 0 al tendere di $n$ a $-∞$].
------------
Se moltiplico per 100 un numero intero qualunque, il resto della divisione per $99$ non cambia.
Chamo $R_n$ il resto della divisione di $a_n$ per 99.
La successione degli $R_n$ ha la legge di ricorrenza seguente:
$R_10 = 10$;
$R_n = (R_(n-1) + n$) mod $99$.

Essendo $a_10 = 10$ si ha dunque:
$R_10 = 10$;
$R_11 = 10 + 11 = 21$;
$R_12 = 10 + 11 + 12 = 33$;
$R_13 = 10 + 11 + 12 + 13 = 46$;
...
E per $n > 13$:
$(R_n = 10 + 11 + ... + n)$ mod $99 = ((n-9)(n+10))/2$ mod $99$.
Se $n$ è dispari $(n-9)/2$ è intero; e allora l'altro fattore $n+10$ può essere maggiore di 98 .
In particolare è proprio $n+10 = 99$ per [size=110]n = 89[/size]

Per $89 < n ≤100$ non si sono altre possibilità [perché se un fattore è divisibile per 11 l'altro fattore NON è divisibile per 9; e se un fattore è divisibile per 9, l'altro fattore NON è divisibile per 11].

Eventuali altri $n$ per i quali $((n-9)(n+10))/2$ è divisibile per 99 sono senz'altro minori di 89.
Di $n$ mnori di 101 e tali $((n-9)(n+10))/2$ sia divisibile per 99 che i pare che ci sia slno $45$.
Per $n=45$ si ha: $((n-9)(n+12))/2 =(36·55)/2 =18·55 = 10·99$.
_______

[orsoulx]

"Erasmus_First":Datemi pure del "pignolo"

Fin qui concordo. Su quanto affermi dopo ho qualche consistente dubbio.
La restrizione, credo, compaia per ottenere, al variare di $ 10<=n<=99 $ stringhe di cifre formate dalla giustapposizione dei numeri da $10$ a $ n $: alle olimpiadi di matematica ci si diverte anche così!
E, se non ho sbagliato qualcosa, i termini della sequenza sono positivi per $n<-1$ e il termine generico tende a $+oo$ al tendere di $n$ a $-oo$.
Perché $ n=53 $ non ti piace?
Ciao

[Erasmus_First]

"orsoulx":[...] se non ho sbagliato qualcosa, i termini della sequenza sono positivi per $n<-1$ e il termine generico tende a $+oo$ al tendere di $n$ a $-oo$.

Sì: è così!
Come altre volte (*) hai ragione tu (ed ho sbagliato io).
[ot](*) Stavo per dire "come sempre" ... ma poi mi sono ricordato di quando mi hai corretto dove avevo detto che nei quiz del tipo di quello allora in questione eri infallibile.[/ot]

"orsoulx":Perché $n=53$ non ti piace?

Forse perché è passato un po' di tempo forse perché sono "rintontito" ... qui non ti capisco!
Da dove si capisce che non mi piace $n = 53$?
Ma ormai non ha più importanza.
Ciao, ciao
_______