conticini su numeri <10^(n+1)

[jordan]

AMC12/2001. Quanti sono i numeri con al massimo n cifre che sono multipli di 3 o di 4 ma non di 5?

Own. Quanti sono i numeri con al massimo n cifre che sono multipli di 3 e che non hanno come cifre il 4 e lo 0?

[Iuppiter]

Provo a rispondere al primo:

$ \lfloor\ 10^n/3\rfloor\ + \lfloor\ 10^n/4\rfloor\ - \lfloor\ 10^n/15\rfloor\ - \lfloor\ 10^n/20\rfloor\ + 2\lfloor\ 10^n/60\rfloor\ $

Spero di non dire eresie...

[CoNVeRGe.]

Provo a rispondere al primo:

$ \lfloor\ 10^n/3\rfloor\ + \lfloor\ 10^n/4\rfloor\ - \lfloor\ 10^n/15\rfloor\ - \lfloor\ 10^n/20\rfloor\ + 2\lfloor\ 10^n/60\rfloor\ $

Spero di non dire eresie...

Il numero dei numeri in cui trovare la soluzione è $ \displaystyle 10^{n+1} - 1 $ e non $ \displaystyle 10^n $

[Iuppiter]

Mmmmm...non mi è ben chiaro.
Il $ -1 $ messo alla fine va bene, ma perchè dovrebbe essere $ 10^{n+1} $ e non $ 10^{n} $ ?
Ad esempio con n=3 devo considerare i numeri di 3 cifre (o meno) che sono 999, cioè $ 10^3 -1 $

[CoNVeRGe.]

Certo mi son fatto confondere dal titolo! E' stato jordan a sbagliare allora

[Iuppiter]

Ok...quindi la soluzione è quella che ho scritto io solo cha va sostituito $ 10^n $ con $ 10^n -1 $?

[CoNVeRGe.]

Non credo, 12 lo conti due volte

[jordan]

Certo mi son fatto confondere dal titolo! E' stato jordan a sbagliare allora

1- $ 10^n < 10^{n+1} $ in ogni caso, quindi non c'è nulla di sbagliato
2- Se allora io mi butto da un fosso ti ci butti pure te?
3- L'ultima osservazione di Converge è giusta, adesso scrivete decentemente il risultato, e, soprattutto, provate a risolvere l'altro..

@Iuppiter: no comment [...]
@iademarco: il primo esercizio è andato.
@Kn: why?

[Iuppiter]

2- Se allora io mi butto da un fosso ti ci butti pure te?

Beh... io si... tanto da un fosso dove vuoi buttarti?

[iademarco]

Il risultato giusto al primo dovrebbe essere questo:
$ \lfloor\ 10^n/3\rfloor\ + \lfloor\ 10^n/4\rfloor\ - \lfloor\ 10^n/15\rfloor\ - \lfloor\ 10^n/20\rfloor\ + \lfloor\ 10^n/60\rfloor\ - \lfloor\ 10^n/12\rfloor\ $

Il numero dei numeri in cui trovare la soluzione è $ \displaystyle 10^{n+1} - 1 $ e non $ \displaystyle 10^n $

Il $ 10^n $ non da fastidio a nessuno, poichè per n=1 il 10 non viene contato, per n>1, il $ 10^n $non viene contato poichè multipli di 20

[kn]

L'own dovrebbe essere $ \displaystyle~\frac{8^{n+1}-1}{21}+\frac{1+(-1)^{\left\lfloor\frac{r}{3}\right\rfloor}\left\lfloor2-\frac{r-1}{3}+\left\lfloor \frac{r-1}{3}\right\rfloor\right\rfloor}{3} $, con r il resto della divisione tra n e 6 (per non mettere troppi floor)

[jordan]

Own. Quanti sono i numeri con al massimo n cifre che sono multipli di 3 e che non hanno come cifre il 4 e lo 0?

Sia $ j \in \mathbb{Z} $ un intero tale che $ 1 \le j \le n $. Definiamo la funzione $ f_j(x)=(x+x^2+x^3+x^5+x^6+x^7+x^8+x^9)^j $. Possiamo osservare che il coefficiente del monomio di grado $ 3y \le 9j $ conta esattamente quanti sono i multipli di $ 3 $ con somma delle cifre $ 3y $ i quali non hanno il $ 4 $ e lo $ 0 $ nella loro rappresentazione decimale. Esisteranno degli $ \{a_{j,i}\}_{0 \le i \le j} \in \mathbb{N} $ tali che $ \displaystyle f_j(x)=\sum_{i=0}^{9j}{a_{i,j}x^i} $. Per cui siamo interessati a trovare $ \displaystyle \sum_{j=1}^n{\sum_{i=0}^{3j}{a_{3i,j}} $. Possiamo affermare anche che dati $ (a,b,c) \in (\mathbb{Z})^3 $ tali che $ c \in \mathbb{P}:=\{2,3,5,...\} $ e $ (a,c)=1 $ e definita la funzione $ g(x)=ax+b $ allora esiste una bigezione tra $ \{0,1,2,\ldots,c-1\} $ e $ \{g(0),g(1),g(2),\ldots,g(c-1)\} $, infatti, se così non fosse, esisterebbero $ 0 \le \alpha < \beta \le c-1 \text{ con } (\alpha,\beta) \in \mathbb{N}^2 $ tali che $ g(\alpha)=g(\beta) $, ma allora $ a(\alpha-\beta)=0 $ in $ \mathbb{Z}/c\mathbb{Z} $, il che è assurdo per ipotesi. E' vero inoltre che se $ \epsilon $ è una delle $ \varphi(c) $ radici $ c $-esime primitive dell'unità allora $ \displaystyle \sum_{i=0}^{c-1}{\epsilon^i}=0 $. Per cui, assegnata un'arbitraria funzione $ p(x)=x^h $, con $ (h,c)=1 $ avremo $ \displaystyle \sum_{i=0}^{c-1}{p(\epsilon^i)}=\sum_{i=0}^{c-1}{\epsilon^i}=0 $. Applichiamo quanto detto al nostro caso, $ c=3 $.
Avremo direttamente che $ \displaystyle \sum_{j=1}^n{\sum_{i=0}^{3j}{a_{3i,j}}=\frac{1}{3} \sum_{j=1}^n{f_j(1)+f_j(\epsilon)+f_j(\epsilon^2)} $ $ \displaystyle =\frac{1}{3}\sum_{j=1}^n{8^j+(1+\epsilon)^j+(1+\epsilon^2)^j $, dove $ \epsilon $ è qui una radice cubica primitiva dell'unità.
Da qui son solo conti, infatti $ \displaystyle \frac{1}{3}\sum_{j=1}^n{8^j+(1+\epsilon)^j+(1+\epsilon^2)^j= \frac{1}{3} \cdot ( 8 \frac{8^n-1}{7}+ \sum_{j=1}^n{ (-\epsilon)^j+(-\epsilon^2)^j}) $ $ \displaystyle = \frac{1}{3} \cdot ( 8 \frac{8^n-1}{7}-\epsilon \frac{1-(-\epsilon)^n}{1+\epsilon}-\epsilon^2 \frac{1-(-\epsilon^2)^n}{1+\epsilon^2})= $
$ \displaystyle =\frac{1}{3} \cdot ( 8 \frac{8^n-1}{7}+\frac{1-(-\epsilon)^n}{\epsilon}+\epsilon(1-(-\epsilon^2)^n) $. Adesso questo numero sarà senz'altro intero, e possiamo notare che i due fattori in cui compaiono le radici cubiche hanno periodo esattamente pari a $ 6 $, per cui lo avrà anche il risultato.