OBM 2019 - Nível 2 - P1

PROBLEMA 1.

Um número de $8$ dígitos é dito robusto se cumprir ambas condições a seguir:
(i) Nenhum dos seus algarismos é $0$.
(ii) A diferença entre dois algarismos consecutivos é $4$ ou $5$.

Responda às perguntas a seguir:
(a) Quantos são os números robustos?
(b) Um número robusto é dito super-robusto se todos os seus algarismos são distintos. Calcule a soma de todos
os números super-robustos.

SOLUÇÃO.

(a) Afirmamos que há $1152$ números robustos.

Acrescentaremos algarismos até formarmos um número robusto.
Basta notarmos que podemos escolher livremente o primeiro algarismo e, do segundo em diante, temos $2$ opções a cada algarismo (se o $5$ é o dígito anterior, podemos optar por $1$ ou $9$ e, para os demais, basta escolhermos se a diferença é $4$ ou $5$).
Segue que há $9(2^7)=1152$ números robustos, como desejado.

(b) Afirmamos que a soma desejada é $999999990$.

Demonstração $1$.

Notemos primeiramente que há apenas $2$ opções de vizinhos para cada algarismo, como vimos em (a), então podemos colocá-los como vértices em um polígono de $9$ lados, de modo que sejam vizinhos aos dígitos possíveis num número super-robusto.

 

Então, para formarmos um número super-robusto, basta escolhermos um vértice para ser o primeiro algarismo e um sentido (hórário ou anti-horário), já que um número super-robusto é unicamente determinado pelos primeiro e segundo algarismo, devido ao fato de que há apenas $2$ opções de vizinho para cada dígito.
Assim, entre todos os números super-robustos, cada algarismo aparece em cada casa exatamente $2$ vezes: para o algarismo $A$ estar numa casa $x$ ($2\leq x \leq 8$), devemos ter um algarismo $B$ com $x-2$ vértices entre $A$ e $B$ em um dos dois sentidos. Isso ocorre $2$ vezes. Para o caso $x=1$, é fácil ver que isso só acontece $2$ vezes: basta escolhermos o algarismo e um dos $2$ sentidos, horário ou anti-horário, e temos um único número super-robusto para cada.
Dessa forma, a soma desejada é dada por:
$2(10^7+10^6+10^5+10^4+10^3+10^2+10^1+10^0)(1+2+3+4+5+6+7+8+9)=999999990$,
como desejado. $\blacksquare$

Demonstração $2$.

Notemos que podemos escolher qualquer algarismo como o primeiro e, como há apenas $2$ opções de vizinhos para cada algarismo (como vimos em (a)), podemos escolher o segundo algarismo entre $2$ opções e os demais dígitos estão unicamente determinados (pois os $8$ dígitos são distintos): há $2(9)=18$ números super-robustos.

Como há poucos números super-robustos, podemos listá-los:

• $15948372$;
• $16273849$;
• $26159483$;
• $27384951$;
• $37261594$;
• $38495162$;
• $48372615$;
• $49516273$;
• $51627384$;
• $59483726$;
• $62738495$;
• $61594837$;
• $73849516$;
• $72615948$;
• $84951627$;
• $83726159$;
• $94837261$;
• $95162738$.

Notemos que, entre todos os números super-robustos, cada algarismo aparece $2$ vezes em cada casa. Então, a soma desejada é dada por:

$2(10^7+10^6+10^5+10^4+10^3+10^2+10^1+10^0)(1+2+3+4+5+6+7+8+9)=999999990$,
como desejado. $\blacksquare$