\( \newcommand{\combin}[2]{{}^{#1}C_{#2} } \newcommand{\cmod}[3]{#1 \equiv #2\left(\bmod {}{#3}\right)} \newcommand{\mdc}[2]{\left( {#1},{#2}\right)} \newcommand{\mmc}[2]{\left[ {#1},{#2}\right]} \newcommand{\cis}{\mathop{\rm cis}} \newcommand{\sen}{\mathop{\rm sen}} \newcommand{\tg}{\mathop{\rm tg}} \newcommand{\cotg}{\mathop{\rm cotg}} \newcommand{\cosec}{\mathop{\rm cosec}} \newcommand{\cotgh}{\mathop{\rm cotgh}} \newcommand{\cosech}{\mathop{\rm cosech}} \newcommand{\sech}{\mathop{\rm sech}} \newcommand{\sh}{\mathop{\rm sh}} \newcommand{\ch}{\mathop{\rm ch}} \newcommand{\th}{\mathop{\rm th}} \newcommand{\senEL}[1]{\mathop{\rm sen}^{#1}} \newcommand{\tgEL}[1]{\mathop{\rm tg}^{#1}} \newcommand{\cotgEL}[1]{\mathop{\rm cotg}^{#1}} \newcommand{\cosecEL}{\mathop{\rm cosec}^{#1}} \newcommand{\shEL}[1]{\mathop{\rm sh^{#1}}} \newcommand{\chEL}[1]{\mathop{\rm ch^{#1}}} \newcommand{\thEL}[1]{\mathop{\rm th^{#1}}} \newcommand{\cotghEL}[1]{\mathop{\rm cotgh^{#1}}} \newcommand{\cosechEL}[1]{\mathop{\rm cosech^{#1}}} \newcommand{\sechEL}[1]{\mathop{\rm sech^{#1}}} \newcommand{\senq}{\senEL{2}} \newcommand{\tgq}{\tgEL{2}} \newcommand{\cotgq}{\cotgEL{2}} \newcommand{\cosecq}{\cosecEL{2}} \newcommand{\cotghq}{\cotghEL{2}} \newcommand{\cosechq}{\cosechEL{2}} \newcommand{\sechq}{\sechEL{2}} \newcommand{\shq}{\shEL{2}} \newcommand{\chq}{\chEL{2}} \newcommand{\arctg}{\mathop{\rm arctg}} \newcommand{\arcsen}{\mathop{\rm arcsen}} \newcommand{\argsh}{\mathop{\rm argsh}} \newcommand{\argch}{\mathop{\rm argch}} \newcommand{\vect}[1]{\overrightarrow{#1}} \newcommand{\tr}[1]{ \textnormal{Tr}\left({#1}\right)} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\H}{\mathbb{H}} \newcommand{\vect}[1]{\overrightarrow{#1}} \newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)} \)

07/09/2017

Contando divisíveis por 11

Problema
Considere todos os números naturais com quinze algarismos que são constituídos apenas por $3$ e/ou $8$ (por exemplo $333333338888888$ ou $333333333333333$)
Quantos destes números são divisíveis por $11$?

210

Proposta de resolução (por Carlos Paulo A. Freitas)
Seja \[N=\overline{a_{15}a_{14}a_{13}...a_{3}a_{2}a_{1}}\] O número $N$ é divisível por $11$ sse o módulo da diferença entre a soma dos algarismos de ordem impar e a soma dos algarismos de ordem par é um múltiplo de $11$.
Por outras palavras, no nosso caso, se \[ \left|S_i-S_p\right|=\dot {11} \] onde $S_i=a_1+a_3+a_5+a_7+a_9+a_{11}+a_{13}+a_{15}$ (uma soma com oito parcelas)
e $S_p=a_2+a_4+a_6+a_8+a_{10}+a_{12}+a_{14}$ (uma soma com sete parcelas)

Nas condições do enunciado, o valor mínimo para $S_i$ obtem-se quando cada uma das oito parcelas desta soma vale $3$ e o valor máximo quando cada uma delas vale $8$.
Assim sendo: \[ 3\times 8\leq S_i \leq 8\times 8 \] Ou seja \[ 24\leq S_i \leq 64 \] Procede-se da mesma forma para $S_p$, ou seja, o valor mínimo para $S_p$ obtem-se quando cada uma das sete parcelas desta soma vale $3$ e o valor máximo quando cada uma delas vale $8$ . ( Digam lá que copy-paste não dá jeito a escrever Matemática )
Assim sendo: \[ 3\times 7\leq S_p \leq 8\times 7 \] Ou seja \[ 21\leq S_p \leq 56 \] O valor seguinte possível para $S_p$ é $26$ que corresponde a substituir um $3$ por um $8$ (observe-se que $21-3+8=26$)
O seguinte é $31$, pela mesma razão...
Vemos assim que $S_p=21+5n$ com $n\in \left\{0,1,2,3,4,5,6,7\right\}$ onde $n$ é o número de algarismos $8$ na soma dos algarismos de ordem par.
Ou seja, os possíveis valores para $S_p$ são $21,26,31,36,41,46,51,56$.
Da mesma forma $S_i=24+5n$ com $n\in \left\{0,1,2,3,4,5,6,7,8\right\}$ onde $n$ é o número de algarismos $8$ na soma dos algarismos de ordem impar.
Então, os possíveis valores para $S_p$ são $24,29,34,39,44,49,54,59,64$.

Se $S_p=21$, para que $S_i-S_p$ seja múltiplo de $11$, o único valor possível para $S_i$ de entre os valores disponíveis é $54$
(pois $54-21=33=3\times 11$)

As fórmulas que dão os $S_p$ e os $S_i$ são de progressões aritméticas de razão $5$.
Então, partindo do par ordenado $(S_p,S_i)=(21,54)$ conseguem-se obter mais dois pares:

\[(26,59) \text{ e } (31,64)\]

Como $64$ é o valor máximo possível para $S_i$, para obter mais pares vamos repetir o processo, mas desta vez começando pelo valor mais baixo possível para $S_i$

Se $S_i=24$, o único valor possível para $S_p$ é $46$.
E tal como anteriormente, partindo deste par ordenado de somas $(S_p,S_i)=(46,24)$ obtêm-se mais duas:

\[(51,29) \text{ e } (56,34)\]
. Como $56$ é o valor máximo possível para $S_p$, obtivemos todos os pares possíveis de somas $(S_p,S_i)$.

Só falta calcular quantos números correspondem a cada par de somas, e somar
$(S_p,S_i)$Número de 8s em ordem parNúmero de 8s em ordem imparTotal de números
$(21,54)$06$\combin{7}{0}\times \combin{8}{6}=\combin{8}{2}=\frac{8\times7}{2}=4\times7=28$
$(26,59)$17$\combin{7}{1}\times \combin{8}{7}=7\times8=56$
$(31,64)$28$\combin{7}{2}\times \combin{8}{8}=\frac{7\times6}{2}\times1=7\times 3=21$
$(46,24)$50$\combin{7}{5}\times \combin{8}{0}=\combin{7}{2}\times \combin{8}{8}=21$
$(51,29)$61$\combin{7}{6}\times \combin{8}{1}=\combin{7}{1}\times \combin{8}{7}=56$
$(56,34)$72$\combin{7}{7}\times \combin{8}{2}=\combin{7}{0}\times \combin{8}{6}=28$
Total=$2\times (28+56+21)=2\times105=210$
Nota do autor:
As contagens conseguem ser feitas sem ser necessário recorrer a combinatória...
Problema colocado originalmente no projecto Delfos. (ok... é melhor não resolver muitos problemas deles aqui..)

Sem comentários:

Enviar um comentário