Febbraio 98

[simone256]

Vi pongo questo problema dimostrativo della gara provinciale del 98, anche in vista di una preparazione per chi è interessato!

Dato un numero intero positivo $ M $ la cui scrittura decimale è $ a_n a_{n-1} ... a_0 $ (cioè $ M $ è uguale a $ 10^na_n+...+10a_1+a_0 $) con $ 0 \le a_0, ..., a_n \le 9 $, sia $ f(M) = a_n + 2a_{n-1} + 2^2a_{n-2} + ... + 2^na_0 $ (si intende che se $ M=a_0 $, $ f(M)=a_0 $).
1. Si determini l'insieme $ X $ di tutti gli interi positivi per cui $ f(M) = M $.
2. Si dimostri che, per ogni intero positivo $ M $, la successione $ M $, $ f(M) $, $ f(f(M)) $, $ f(f(f(M))) $, $ ... $ contiene un elemento di $ X $.

Sinceramente spero in qualcosa di più semplice alla gara visto che ce ne dovrebbero essere 3 così più altri 14 da fare in tre ore... E per scrivere una bella soluzione lineare per questo ci ho messo quasi un'ora.

[Gi.]

Qualche idea lampo, poi provo a svolgerlo bene domani.

Innanzitutto "giriamo" i termini di $f(M)$ per comodità:

$f(M)=2^na_0+...+2_{an-1}+a_n$

$M=10^na_n+...+10a_1+a_0$

Proviamo qualche caso:

$n=0$ (M ad una sola cifra)

$M=a_0$
$f(M)=a_0$

Banalmente abbiamo $M=f(M) \forall a_0$,con $0<a_0\le9$.

$n=1$ (M a due cifre)

$M=10a_1+a_0$

$f(M)=2a_0+a_1$

vogliamo che queste due espressioni siano uguali, per cui

$10a_1+a_0=2a_0+a_1$

$9a_1-a_0=0$

banalmente $a_1=1$ e $a_0=9$, per cui $ M=19 $

$n=2$ (M a tre cifre)

$M=10^2a_2+10a_1+a_0$
$f(M)=2^2a_0+2a_1+a_2$

per cui arriviamo a

$99a_2+8a_1-3a_0=0$

$a_2$ non puo' essere uguale a 0, banalmente perché altrimenti non siamo nel caso $n=2$ (il numero avrebbe due cifre e non tre), riscriviamo come

$3(33a_2-a_0)+8a_1=0$

Sempre positivo, non ci sono soluzioni.
Adesso all' aumentare di $n$ aumentano i valori dei numeri, ad esempio il caso $n=3$ porta a

$999a_3+98a_2+6a_1-7a_0=0$

volendo possiamo fare lo stesso lavoro di prima

$3(333a_3+2a_1)+7(14a_2-a_0)=0$

Sempre positivo, per cui nessuna soluzione.
A questo punto i numeri continuano a crescere e intuitivamente possiamo affermare che non vi sono altre soluzioni oltre a quelle trovate. Per cui l' insieme é $X= (0,1,2,3,4,5,6,7,8,9,19 )$ (ho messo le tonde perché non riesco a mettere le graffe).

Il punto 2 lo tento domani.

[simone256]

Esatto! I valori sono quelli!
(escluso lo $ 0 $ che non è positivo )

[ma_go]

giusto per essere un po' puntigliosi: i valori sono quelli, ma la dimostrazione è incompleta. è chiara l'idea ed è chiaro dove vuoi andare a parare, ma quello che hai scritto non è da punteggio pieno. (e infatti hai detto che "domani proverai a svolgerlo per bene"...)

[Drago96]

L'idea che doveva venire ti è più o meno venuta; il problema ora è dimostrare che per n abbastanza grandi (in realtà si scopre che sono abbastanza piccoli) vale $M>f(M)$
Come fare? Bisogna vedere i valori limite di M e di f(M), anche con cifre diverse, e ottenere le solite disuguaglianze larghissime di TdN...
Per il punto 2 basta sfruttare il fatto che la sequenza delle f(M) sia decrescente, facendo attenzione ai casi di uguaglianza...

[Gi.]

Per il punto due credo di aver capito: la successione è decrescente, ma essendo nei naturali non può decrescere oltre lo 0, quindi prima o poi incontrerà un numero $ k $ appartenente ad $ X $ per il quale la successione continua ad assumere il valore $ k $ ad ogni iterazione.

Per il punto uno, il caso limite (cioè quello in cui $ f(M) $ e $ M $ sono maggiori) è quello in cui $ a_i=9 $ $ \forall i\ge 0 $, in questo caso

$ f(M)=9(2^n+2^{n-1}+...+2+1) $

quella dentro parentesi è una serie geometrica, per cui

$ f(M)=9(2^{n+1}-1) $

che per ogni $ n \ge 2 $ risulta minore di $ M $.

[Drago96]

In realtà il "caso limite" che hai fatto tu è uno solo, cioè, hai massimizzato le cifre...
Io invece intendevo analizzare i casi limite di $M$ e $f(M)$ separatamente: se il più piccolo valore che può assumere $M$ è più grande del massimo valore di $f(M)$ sei a posto

[Gi.]

Giusto.
Il caso limite di $ M $ è quando tutti i suoi $ a_i $ sono uguali a 0, tranne $ a_n $ che vale 1, per cui in sostanza rimane $ 10^n $ che risulta maggiore del caso limite di $ f(M) $ per ogni $ n>1 $.