Problema de los cocos – Solución

Estilo Ken

Es armar un pedacito de Python:

def is_solution(n):
    for i in range(5):
        if n % 5 != 1:
            return False
        n = 4 * (n // 5)
    return n % 5 == 1
 
for n in xrange(100000):
    if is_solution(n):
        print n

Imprimiendo la salida:

15621
31246
46871
62496
78121
93746
Estilo tradicional

Vamos en sentido inverso al de la división. El número de cocos antes de la ultima división debe ser de la forma 5N + 1: 1, 6, 11, …

Cuando el último en despertarse, al que llamaremos E, dividió la cantidad dejó un múltiplo de 4. Así que sabemos que la cantidad debe tener la forma 20N + 16: 16, 36, 56, …

Antes de que E vencontrara la pila había entonces una cantidad de la forma 25N + 21: 21, 46, 71, …

Ahora, como esa cantidad fue dejada por D, también debía ser un múltiplo de 4. Eso implica que su forma debe ser 100N + 96: 96, 196, 296, …

Y así seguimos:

Antes de que D la encontrara, 125N + 121: 121, 246, 371, …

Debe ser múltiplo de 4, 500N + 496: 496, 996, 1496, …

Antes de que C la encontrara, 625N + 621: 625, 1246, 1871, …

Debe ser múltiplo de 4, 2500N + 2496: 2496, 4996, 7496, …

Antes de que B la encontrara, 3125N + 3121: 3125, 6246, 9371, …

Debe ser múltiplo de 4, 12500N + 12496: 12496, 24996, 37496, …

Antes de que A la encontrara, 15625N + 15621: 15621, 31246, 46871, …

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s