Palmadas a terceros- parte 2

Este post continúa el acertijo "Palmadas a terceros", que empieza AQUÍ.

Formulado de otra manera, lo que se nos pregunta es cuántos números hay entre 1 y 10n que sean múltiplos de 3 o que acaben por 3, pero no ambas. Podríamos hallar cuántos múltiplos de 3 hay y cuántos hay que acaben por 3 y sumar las dos cantidades. Pero, entonces, estaríamos contando también los que cumplen las dos condiciones. Debemos restarlos de nuestro resultado. Pero, ¡cuidado!, los habíamos sumado dos veces (una vez junto con los múltiplos y otra porque acaban por 3). Así, la operación que debemos hacer es:

(Múltiplos de 3) + (Acaban por 3) - 2*(Cumplen ambas condiciones)

Analicemos ahora cada una de esas tres cantidades para ver cómo las podemos expresar. En primer lugar, ¿cuántos números entre 1 y 10n son múltiplos de 3? Entre 1 y 10, hay 3; entre 1 y 20, hay 6; entre 1 y 30, hay 10. En general, entre 1 y 10n, hay ⌊10n/3⌋, es decir, la parte entera de la división 10n/3. Por ejemplo, para n = 3, hay ⌊30/3⌋ = ⌊10⌋ = 10. Y para n = 4, ⌊40/3⌋ = ⌊13.33⌋ = 13.

¿Cuántos números terminan por 3 entre 1 y 10n? Ésta es fácil: exactamente n, uno para cada una de las decenas. Por ejemplo, entre 1 y 30, hay 3: 3, 13 y 23.

Solo nos queda contestar a la pregunta "¿Cuántos números son múltiplos de 3 y terminan por 3?" No hay muchos, la secuencia comienza 3, 33, 63, 93,... Es decir, a partir del 3, se va sumando 30 cada vez. En otras palabras, cuando n es 1, 2 ó 3, hay solamente un número que lo cumple, el 3; cuando n es 4, 5 ó 6, hay 2, el 3 y el 33, etc. Hay varias formas de expresar esto en función de n. Una de ellas es ⌊(n-1)/3⌋ + 1. Por ejemplo, cuando n = 4, hay ⌊(4-1)/3⌋ + 1 = ⌊1⌋ + 1 = 1 + 1 = 2. Y cuando n = 5, hay ⌊(5-1)/3⌋ + 1 = ⌊1.33⌋ + 1 = 1 + 1 = 2.

Por lo tanto, juntando las tres fórmulas, llegamos a que la solución del acertijo es:

⌊10n/3⌋ + n - 2*(⌊(n-1)/3⌋ + 1)

En los ejemplos propuestos en el enunciado, cuando n = 5, 10 y 53, las soluciones particulares son 17, 35 y 193, respectivamente.

No te pierdas el siguiente post para ver otra manera de llegar a una fórmula que también es válida.