Maratona de problemas - Dia 3

Prosseguindo...

Peroba neles

(OBM 2007) Um número de quatro dígitos é dito peroba se possui pelo menos dois dígitos vizinhos com a mesma paridade. Quantos números perobas existem?

Problemas com dígitos são clássicos. Há vários tipos de números que satisfazem essa condição, como:

par-par-par-par
par-par-par-ímpar
par-par-ímpar-par
... etc.

Fica evidente que é muito mais fácil encontrar quantos números que não são peroba existem e subtrair de 9000, a quantidade de números com 4 dígitos. Assim, temos:

par-ímpar-par-ímpar
ímpar-par-ímpar-par

A partir daí é só usar o princípio fundamental da contagem, tomando o cuidado de notar que, para o primeiro caso, não podemos utilizar 0 na primeira casa. Assim:

par-ímpar-par-ímpar: 4 * 5 * 5 *5 = 500 números
ímpar-par-ímpar-par: 5 * 5 * 5 * 5 = 625 números

Nossa resposta é, portanto, 9000 - 1125 = 7875 números.

Quanto é f(2005)?

(OBM 2005) Suponha que, para quaisquer valores reais de x e y, f(x + f(y)) = x + f(f(y)). Sabendo que f(2) = 8, calcule f(2005).

Problemas com funções também são bem usuais, e novamente estamos diante de recursividade. Começamos com um caso pequeno: quanto é f(8)? Se quiser pode até substituir y por 2 e x por 0 de modo que fique f(0 + f(2)) = f(8), mas já adianto que não dará certo. E se substituirmos f(y) por 2? Assim, como f(y) deve ser 2, x deve ser 6:

f(6 + 2) = 6 + f(2)

f(8) = 8 + 6

f(8) = 14

Olha só que interessante. Concordam que agora poderíamos usar o mesmo truque para calcular o valor da função para... 10, por exemplo? Basta fazer f(y) = 8 e tomar 2 como x. Assim, se quisermos calcular um dado valor, escolhemos um menor e aí vemos o que acontece. Que valor é esse? Oras, pode ser 2 mesmo.

f(2003 + 2) = 2003 + f(2)
f(2005) = 2011

Poderíamos também generalizar a função para facilitar as coisas. Primeiro calculamos f(0), cujo valor é 6, e depois fazemos f(y) = 0:

f(x + 0) = x + f(6)
f(x) = x + 12 

Por um lado é uma solução alternativa mais interessante pois nos permite calcular mais rapidamente, mas primeiro é preciso descobrir f(0) e f(6), o que consome tempo desnecessariamente.

Resolvendo equações

(OBM 2010)Quantos são os pares (x, y) de inteiros positivos tais que x² - y² = 2^2010?

Fatoração é tudo na vida. Podemos reescrever a equação como:

(x + y)(x - y) = 2^2010

Precisamos ter os dois fatores como potências de 2, de modo que:

2^a * 2^b = 2^2010

Sendo que a + b = 2010.  Assim:

x + y = 2^a
x - y = 2^b

Resolve-se o sistema e tem-se x = 2^(b-1) - 2^(a - 1) e y = 2^(b - 1) + 2^(a - 1). Queremos soluções inteiras, então precisamos ter a >= 1. Logo, os possíveis pares (a, b) são (1, 2009), (2, 2008),...(1004, 1006). Temos portanto 1004 soluções.