Congruências e equações Diofantinas

Bem, no meu 3º encontro do PIC eu apresentei um seminário sobre congruências modulares e equações diofantinas lineares. E publicarei o documento aqui também:

Número com 17 algarismos

Escolhe-se um número de $$17$$ algarismos, e inverte-se a ordem de seus algarismos, formando um novo número. Estes dois números são somados. Mostre que a soma contém pelo menos um algarismo par.

Chamaremos esse número de $$\mathbf{N}$$. Então, escrevendo os algarismos de $$\mathbf{N}$$, temos algo assim:
\[\Large a b c d e f g h i h g f e d c b a\]
Vou utilizar uma notação como a seguir:

•  $$\stackrel{\leftarrow}{a}$$: significa que a soma que originou o algarismo a foi maior que 10. Sendo assim, existe um "vai-um" do algarismo a para o da esquerda.
•  $$\stackrel{\star}{a}$$: significa que a soma que originou o algarismo a resultou em um número par.

Farei uma afirmação de que "Nenhum algarismo de $$\mathbf{N}$$ é par", que é equivalente a dizer "Todos os algarismos de $$\mathbf{N}$$ são ímpares" . Essa será a afirmação principal.
Sendo assim, vou tentar chegar a uma contradição, provando que a afirmação acima é falsa.

Como $$i$$ é formado por duas parcelas iguais, então originalmente deve ser par. Usando a minha notação:
\[ a b c d e f g h \stackrel{\star}{i} h g f e d c b a \]
Portanto, para a afirmação inicial ser verdadeira, deve existir um "vai-um" do $$h$$. Usando a notação:
\[a b c d e f g $\stackrel{\leftarrow}{h} \stackrel{\star}{i} \stackrel{\leftarrow}{h}$ g f e d c b a \]
Por conseguinte, $$g$$ deve ser originalmente par.
\[a b c d e f $\stackrel{\star}{g} \stackrel{\leftarrow}{h} \stackrel{\star}{i} \stackrel{\leftarrow}{h} \stackrel{\star}{g}$ f e d c b a\]
Isso faz com que $$f$$ tenha que mandar um "vai-um" para que $$g$$ seja ímpar.
\[a b c d e $\stackrel{\leftarrow}{f} \stackrel{\star}{g} \stackrel{\leftarrow}{h} \stackrel{\star}{i} \stackrel{\leftarrow}{h} \stackrel{\star}{g} \stackrel{\leftarrow}{f}$ e d c b a\]

Continuando no raciocínio acima, deduzimos que e era originalmente par, fazendo com que d mande um "vai-um", o que por sua vez, faz com que c seja originalmente par, o que faz com que b mande um "vai-um". Chegamos a uma notação assim:
\[ \stackrel{\star}{a} \stackrel{\leftarrow}{b}\stackrel{\star}{c} \stackrel{\leftarrow}{d} \stackrel{\star}{e} \stackrel{\leftarrow}{f} \stackrel{\star}{g} \stackrel{\leftarrow}{h} \stackrel{\star}{i} \stackrel{\leftarrow}{h} \stackrel{\star}{g} \stackrel{\leftarrow}{f} \stackrel{\star}{e} \stackrel{\leftarrow}{d} \stackrel{\star}{c} \stackrel{\leftarrow}{b} \stackrel{\star}{a}\]

Mas isso faz com que a seja originalmente par.
\[ \stackrel{\star}{a} \stackrel{\leftarrow}{b}\stackrel{\star}{c} \stackrel{\leftarrow}{d} \stackrel{\star}{e} \stackrel{\leftarrow}{f} \stackrel{\star}{g} \stackrel{\leftarrow}{h} \stackrel{\star}{i} \stackrel{\leftarrow}{h} \stackrel{\star}{g} \stackrel{\leftarrow}{f} \stackrel{\star}{e} \stackrel{\leftarrow}{d} \stackrel{\star}{c} \stackrel{\leftarrow}{b} \stackrel{\star}{a}\]

Mas então chegamos a um absurdo, já que não há nenhum algarismo à direita do a que representa o algarismo das unidades para mandar um "vai-um". Portanto, a afirmação principal, "Nenhum algarismo de $$\mathbf{N}$$ é par" é falsa.
Então, devemos ter no pelo menos um algarismo par em $$\mathbf{N}$$ $$ \square$$

Problema com cores

O problema é o seguinte:

Qual é o número de maneiras de colorir $$n$$ objetos com três cores, se cada cor tem que ser usada pelo menos uma vez?

Bem, a solução criada por mim foi a seguinte:
Vou considerar que são objetos iguais, ou seja, não importa qual objeto foi pintado com determinada cor, mas sim quantos objetos foram pintados com aquela com. Seja $$k_i$$ o número de objetos pintados com a cor $$i$$ para $$i \in \{1,2,3\}$$.
Então, temos que saber quantas são as soluções inteiras positivas da equação:
\[ k_1 + k_2 + k_3 = n \]

Escrevemos $$n$$ como a soma de $$n$$ "uns", como a seguir:
\[\underbrace{1+1+1+1+1+1+\dots +1+1+1+1}_{n} = n\]

Se usarmos 2 barras para separar esses 1's, teremos algo como:
\[\underbrace{1+1+1+1}_{4} |\overbrace{+1+1+\dots +1}^{n-7} |\underbrace{ +1+1+1}_{3}\]

Que corresponde a solução $$(k_1, k_2, k_3) = (4,n-7,3)$$
Observamos que existem $$n-1$$ sinais de $$``+"$$, nos quais podemos colocar as barras na frente, e obtermos uma solução.
Então, basta escolhermos $$2$$ entre $$n-1$$ sinais de $$``+"$$ para colocar-mos as barras, que pode ser feito de $$\displaystyle \binom{n-1}{2}$$ maneiras , ou seja,
\[\dfrac{(n-1)!}{2!(n-3)!} = \dfrac{(n-1)(n-2)}{2}\]

Problema modular: 9x99x999...

Esse problema tem um enunciado bem simples:

Determine o resto da divisão de $$9\times 99\times 999\times \dots \times \underbrace{99\dots9}_{999\:\:\: \text{noves}} $$ por $$ 1000 $$.

Bem, para resolver, usamos os seguintes  teoremas:

• $$ a \equiv r \pmod{b} \Rightarrow a-r = nr \: , n \in \mathbb{Z} $$;
• $$ a \equiv r \pmod{b} \Rightarrow na \equiv nb \pmod{b} $$;

O primeiro teorema diz que $$ 999 \equiv -1 \pmod{1000} $$, já que $$ 999 - (-1) = 1\cdot 1000$$.
Como observamos, depois do 2º termo, todas as parcelas deixam resto 999 quando divididas por 1000, já que podemos escrever o n-ésimo termo assim:
\[ 1000\cdot \overbrace{99\dots 99}^{n \: \text{noves}} + 999 \]
Então, transformamos a equação do enunciado em:
\[ 9\times 99\times \underbrace{999\times 999\times \cdots \times 999\times 999 }_{997 \: \: \text{parcelas}} \]
\[ 9 \cdot 99 \cdot (-1)^{997} \]
\[ -891 \]
Isso equivale a dizer que o resto daquela expressão gigante por $$1000$$ é igual a $$109$$, já que
\[109 \equiv -891 \pmod{1000} \Rightarrow 109 - (-891) = 1000\cdot 1\]

Bem, o começo

Vou usar esse espaço para postar problemas de caráter olímpico, suas  resoluções e os truques mais usados para resolvê-los.
Bem, desde 2005 eu venho resolvendo problemas olímpicos, mas ultimamente eu passei a ter uma visão mais ampla sobre isso. Primeiro, por que no começo, eu apenas fazia  a OBMEP. Mas desde o ano passado, eu começei a fazer a ORM/SC e a OBM. E ainda mais agora, fazendo o PIC, que é o programa de iniciação científica da OBMEP, onde são tratados assuntos relacionados com a matemática olímpica.
Mas, por que chamo de Matemática Olímpica ? Pois trata-se de uma abordagem diferente da Matemática comum, aquela da escola. Na escola, apenas fazemos exercícios repetitivos, cansativos. Isso não faz nós progredirmos em nada quanto ao raciocínio empregado pra resolver os problemas. E é nessa questão que a Matemática Olímpica se diferencia. Ela faz você pensar. Não basta apenas a solução (quando a solução existe), mas o caminho que você fez até chegar na solução.
É com esse espírito que começo hoje a escrever aqui.
Até a próxima, com o primeiro problema.