OBM 2016 - Nível 2 - P1

Problema 1

a) Considere todos os números formados usando os quatro algarismos $1$, $2$, $3$ e $4$. Formamos a seguinte expressão numérica $S_4 = 4321-4312+4231-4213+...+1243-1234$, na qual os números são listados da esquerda para a direita do maior para o menor, e os sinais $+$ e $-$ alternam-se até o final. Calcule o valor de $S_4$.

b) De modo análogo, tomamos todos os números de nove algarismos distintos e não nulos e formamos a expressão numérica $S_9 = 987654321-987654312+987654231-...-123456789$, na qual os números são listados da esquerda para a direita do maior para o menor, e os sinais $+$ e $-$ alternam-se até o final. Calcule o valor de $S_9$.

Solução por Caio Hermano:

Para calcularmos o valor da expressão em ambas situações vamos utilizar o fato que entre dois números consecutivos (com um sinal negativo entre eles) a única diferença é a permutação dos dois últimos algarismos, que possibilita a menor diferença possível (alterar as centenas, por exemplo, não seria a melhor opção se ainda podemos alterar apenas as dezenas e unidades, que possibilitam um menor acréscimo) requerida para a ordenação dos números.

Defina $S_n$ da mesma forma que $S_4$ e $S_9$, sendo $n$ natural e menor ou igual a $9$.

Analisando esse fato veja que o valor total de $S_n$ é justamente dado por essas diferenças, logo ao contá-las encontramos a resposta do problema. Vamos fixar os dígitos não permutados e analisar apenas os dois últimos dígitos: suponha que o menor seja $a$ e o maior $a+j$, então ao trocarmos ambos de lugar, a única diferença entre os números será justamente a diferença resultante da permutação, pois o restante vai “se anular”, assim basta calcularmos:

$[10 \cdot (a+j) + a]- [10 \cdot a + (a+j)] = 10 \cdot j - j = 9 \cdot j$

Se a diferença entre os dígitos permutados for $j$, então acrescentamos $9j$ ao valor total, porém, veja que fixando os algarismos não permutados, a quantidade $k$ de vezes que isso acontece é justamente $n-j$:

Permutação dos dígitos cuja diferença é $j$: $1$ e $j+1$, $2$ e $j+2$, ... , $k$ e $j+k$, mas $n$ é o maior dígito possível, logo $j+k = n \Rightarrow k = n-j$, justamente o que queremos provar.

Por fim, basta "acrescentarmos" a quantidade de vezes que cada pequena diferença, resultante da permutação dos dois últimos dígitos, ocorre: \((n-2)\), de fato, esse valor resulta da quantidade de maneiras existentes de permutar os $(n-2)$ primeiros dígitos, que durante nossos cálculos estavam fixos.

Assim:

$S_n = (n-2)!\cdot[(n-1) \times (9 \cdot 1) + (n-2) \times (9 \cdot 2) + (n-3) \times (9 \cdot 3) + ... + (n-(n-1)) \times (9 \cdot (n-1))]$.

O que nos possibilita encontrar a resposta de ambos itens:

(a) $S_4 = 2! \cdot [(4-1) \times (9 \cdot 1) + (4-2) \times (9 \cdot 2) + (4-3) \times (9 \cdot 3)] = 2! \cdot 90 = 180$.

(b) $S_9 = 7! \cdot [(9-1) \times (9 \cdot 1) + (9-2) \times (9 \cdot 2) + ... + (1) \times (9 \cdot 8)] = 7! \cdot[72 + 126 + 162 + 180 + 180 + 162 + 126 + 72] = 7! \cdot 1080 = 5443200$.