6-Um numero natural e dito alternante se dois digitos consecutivos sao de paridades diferentes. (Como um exemplo, temos 1, 2, 12567825650167.)
Determine todos os numeros naturais que nao dividem nenhum numero alternante.
Resposta: todos os multiplos de 20 e apenas esses .
Vamos dizer que x e elegante se ele aparece em alguma fatoraçao (nao necessariamente em primos) de algum alternante.
/*Este problema e bastante parecido com um que o Shine resolveu ha dois anos no treinamento para a OBM (algo sobre numeros esburacados). Essa e a segunda vez que um problema muito parecido com algum banco anterior cai em uma IMO (algo parecido ocorreu com o problema 3 da IMO da China e o problema 4 da IMO da Romenia). */
LEMA 0 : se x e deselegante entao Kx tambem sera.
LEMA 1 : se Kx e elegante entao x tambem sera.
LEMA 1 : se MDC (10,x)=1 entao x e elegante.
PROVA: basta escrever um alternado da forma a seguir:
1010101010101.....0101010101
(calma, isso e base 10 e nao 2!).
E so aplicar Casa dos Pombos ou o Teorema de Euler-Fermat!
LEMA 2 : toda potencia de 5 e elegante.
PROVA: vamos fazer casos pequenos.
5 e alternante
5^2=25 e alternante
5^3=125 e alternante (puxa, quanta sorte!).
Agora vamos caçar um alternante para o 5^4=625 (a sorte acabou!).
A ideia e escrever 10^3*a+5^3*1=5^4*b, ou equivalentemente 2^3*a+1=5b, que e uma equaçao diofantina soluvel. ache um a de acordo com a paridade que te interesse. Isto sempre da certo pois
0=5
1=4
2=3
se olharmos mod 5.
Podemos construir indutivamente os nossos alternantes (e com uma boa facilidade! Da ate para botar num computador! Quando eu aprender C eu libero um programinha...). O processo e parecido.
Analogamente demonstra-se o
LEMA 2' :as potencias de 2 tambem sao elegantes.
Agora vamos fatorar n (nosso candidato a numero deselegante).
Suponha que 20 nao divida n.
E claro que devemos ter MDC (10,n) > 1.
Entao n=2^a * 5^b * q, com MDC (10,q) =1.
Se a>1e b>0, absurdo!
Se a<2 e b<2, entao n tem um multiplo alternante que acaba em um zero (se por exemplo n=2q faça 5n=10q, e se Xq=101010..101, entao 10Xq sera alternante).
E os outros casos? Se n acabar em muitos zeros, n nao sera alternante. Mas ai n dividira 20 se tiver dois zeros no final.
Vamos pensar ... Sera que 2q e elegante? Sim, oras! E so pegar o 2020202020202....202. logo e possivel, usando os lemas anteriores, fazer (2^n)*q elegante. E o mesmo vale para 5. E fim!