somma cifre in base b

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Febo
Messaggi: 47
Iscritto il: 20 set 2007, 15:08

somma cifre in base b

Messaggio da Febo » 24 set 2007, 21:55

Siano a,b,n interi positivi tali che: $ b^n-1|a $

Poniamo $ a=\displaystyle\sum_{i=0}^k a_ib^i $ dove $ 0\le a_i<b $

Dimostrare che: $ \displaystyle\sum_{i=0}^k a_i \ge n(b-1) $

Buona fortuna...
Fondatore dell'associazione "Non uno di meno", per lo sterminio massiccio dei nani e affini.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 23 ott 2007, 15:46

Io l'ho fatto cosi':

Notazione: Dato un intero non negativo $ n $, indico con $ s(n) $ la somma delle cifre in base $ b $ di $ n $.

Lemma: Siano $ x $, $ y $, $ z $ interi positivi t.c. $ z = x - y $. Allora

$ $s(z) = s(x) - s(y) + (b-1)r $,

dove $ r $ e' il numero di riporti che si effettuano nel calcolare la sottrazione $ x - y $ .


Dim.: Ovvia, dall'algoritmo di sottrazione in colonna. []

Soluzione
Sappiamo che $ a $ e' un multiplo di $ b^n - 1 $, ossia che esiste un intero positivo $ k $ t.c. $ a = k \left( b^n - 1 \right) $.

Wlog, posso supporre $ b \nmid k $, dato che eliminare gli zeri in coda da $ a $ non cambia la somma delle cifre.

Applico il Lemma con $ x = k b^n $, $ y = k $, $ z = a $. Se dimostro che questa sottrazione ha almeno $ n $ riporti, ho vinto. Ma questo e' abbastanza ovvio, dato che le ultime $ n $ cifre di $ x $ sono zeri, e la cifra delle unita' di $ y $ e' diversa da zero. []
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Rispondi