Euler 34

El problema 34 del proyecto Euler dice lo siguiente:

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Me pareció que podía ser divertido hacer algo en Python para resolverlo y he aquí el resultado:

import math
def igual_fact(num):

suma = 0

for i in str(num):

suma += math.factorial(int(i))

if suma == num:

return True

else:

return False

suma = 0
for i in range(1,3*10**6):

if igual_fact(i):
suma += i

print(suma – 3)

 

Aquí tenéis el enlace: https://repl.it/IUPV/1

Por cierto, el resultado es: 40730


 

Factorización en números primos

Acabo de terminar un pequeño código en Python para factorizar un número en factores primos y quería compartirlo aquí con vosotros. Lo copio a continuación:

def factor(num):

lista =[]

for i in range(2,int(num)+1):
if prime(i):
if num%i==0:
c =1
while num%i**c==0:
c +=1
lista.append((i,c-1))

return lista

def prime(num):
if num == 2:
return True
c = 0
for i in range(2,int(num**0.5)+1):
if num%i==0:
c +=1
return False

if c == 0:
return True
num = int(input(“Introduce el número: “))
print(factor(num))

Os dejo el enlace aquí: https://repl.it/INY1/7

 

Proyecto Euler.

En adelante voy a publicar, de una manera nada regular, seguramente, soluciones a problemas extraídos de Project Euler . Se trata de un sitio en el que se pueden encontrar interesantísimos problemas, habitualmente de carácter matemático, para resolver mediante algún lenguaje de programación.

En esta ocasión se trata del problema número 63:

The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

Para abordar este problema es conveniente hacer previamente un pequeño análisis matemático.

Si hablamos de números de n dígitos, entonces estamos en el intervalo que va de { 10 }^{ n-1 }\quad a\quad { 10 }^{ n }, excluyendo el extremo superior, ya que, como es obvio,  { 10 }^{ n } tiene n+1 cifras. Así que tenemos que sacr información de la siguiente inecuación: { 10 }^{ n-1 }\le { x }^{ n }<\quad { 10 }^{ n }.

Lo anterior nos lleva a   { 10 }^{ \frac { n-1 }{ n }  }\le { x }\le \quad 9, sin más que tomar raíces. Ahora fijémonos en la siguiente imagen:

funcioncifras

Se trata de la gráfica de la función f(x) = 10^((n-1)/n) que, como veis, es estrictamente creciente y cuando n vale 22 toma un valor superior a 9, lo cual nos permite restringirnos a exponentes que van de 1 a 21.

El programa en Python para implementar todo esto es bien sencillo. Lo copio aquí:

cont = 0
# Un bucle para el exponente: de 1 a 21.
for n in range(1,22):
#Para cada exponente un bucle entre los valores permitidos.
for j in range(int(10**(1-1/n)+1),10):
print (j,n,j**n)
cont +=1

print (“El número de cifras es: “,cont)

Aquí os dejo el enlace: https://repl.it/HxAr/7

Si ejecutáis el programa obtenéis:

2 1 2
3 1 3
4 1 4
5 1 5
6 1 6
7 1 7
8 1 8
9 1 9
4 2 16
5 2 25
6 2 36
7 2 49
8 2 64
9 2 81
5 3 125
6 3 216
7 3 343
8 3 512
9 3 729
6 4 1296
7 4 2401
8 4 4096
9 4 6561
7 5 16807
8 5 32768
9 5 59049
7 6 117649
8 6 262144
9 6 531441
8 7 2097152
9 7 4782969
8 8 16777216
9 8 43046721
8 9 134217728
9 9 387420489
8 10 1073741824
9 10 3486784401
9 11 31381059609
9 12 282429536481
9 13 2541865828329
9 14 22876792454961
9 15 205891132094649
9 16 1853020188851841
9 17 16677181699666569
9 18 150094635296999121
9 19 1350851717672992089
9 20 12157665459056928801
9 21 109418989131512359209
El número de cifras es: 48
___________________________________________________________________________
Se entiende que, por ejemplo, la última fila hay que leerla así:
9^21 = 109418989131512359209

Nota: En realidad, la solución correcta es 49, ya que
el programa anterior no incluye 1^1=1!!!!

Carrera de caballos aleatorios!!!

Feliz por haber acertado el riddler de la semana pasada, me acerco al hipódromo más cercano y me devano los sesos para resolver el último “acertijo” que nos propone el amigo Oliver y que dice lo siguiente:

The Kentucky Derby is on Saturday, and a field of 20 horses is slated to run “the fastest two minutes in sports” in pursuit of the right to be draped with a blanket of roses. But let’s consider, instead, the Lucky Derby, where things are a little more bizarre:

The bugle sounds, and 20 horses make their way to the starting gate for the first annual Lucky Derby. These horses, all trained at the mysterious Riddler Stables, are special. Each second, every Riddler-trained horse takes one step. Each step is exactly one meter long. But what these horses exhibit in precision, they lack in sense of direction. Most of the time, their steps are forward (toward the finish line) but the rest of the time they are backward (away from the finish line). As an avid fan of the Lucky Derby, you’ve done exhaustive research on these 20 competitors. You know that Horse One goes forward 52 percent of the time, Horse Two 54 percent of the time, Horse Three 56 percent, and so on, up to the favorite filly, Horse Twenty, who steps forward 90 percent of the time. The horses’ steps are taken independently of one another, and the finish line is 200 meters from the starting gate.

Handicap this race and place your bets! In other words, what are the odds (a percentage is fine) that each horse wins?

Primero me planteé la idea de resolverlo con lápiz y papel, pero finalmente, tras haber llegado a la conclusión de que la cosa podía ser bastante ardua, me decidí a utilizar Montecarlo, con Python. Como siempre, os adjunto el enlace para que podáis verlo y modificarlo a placer: https://repl.it/Hjg4/8.

Los resultados vienen dados en la siguiente lista, de la cual he borrado los primeros 13 resultados, ya que son cero. Es el resultado de 100000 simulaciones, así que supongo que el resultado es muy cercano al real. Observad que el caballo 20 tiene una probabilidad de un 71% de ganar la carrera, el 19, apenas un 22% and so on:

0.0009578085340740386, 0.016282745079258656, 0.1264307264977731, 0.893635362291078, 5.2650735118049905, 22.259470331880657, 71.43814951391217

Actualización: Otro acierto en el riddler.

Bolitas de colorines.

El último Riddler nos propone un interesante problema de probabilidad. He aquí lo que dice:

You play a game with four balls: One ball is red, one is blue, one is green and one is yellow. They are placed in a box. You draw a ball out of the box at random and note its color. Without replacing the first ball, you draw a second ball and then paint it to match the color of the first. Replace both balls, and repeat the process. The game ends when all four balls have become the same color. What is the expected number of turns to finish the game?

 

Así que partimos de una urna con cuatro bolas de distintos colores: RBGY. Es evidente que en el primer paso nos vamos a encontrar con alguna de las siguientes disposiciones:

RRGY, BBGY,  GGRB o cualquier otra distribución en la que aparecen dos bolas del mismo color y otras dos de distinto color. Es decir, que con probabilidad 1 pasamos de una disposición en la que hay cuatro colores a otra en la que hay tres.

Supongamos ahora que estamos en una de dichas situaciones, por ejemplo: RRBY. ¿A qué estados (y con qué probabilidades) podemos pasar en el siguiente paso del proceso?

Está claro que nunca volverá a haber cuatro colores otra vez. Tampoco vamos a llegar, en un paso, a una urna con un solo color. Sólo hay dos posibilidades, a saber: pasar a una disposición en la que sigue habiendo tres colores o a una en la que hay 2 colores.

Veamos, en el paso 2 tenemos la siguiente distribución: RRBY. para pasar a un estado con, otra vez, tres colores, tiene que ocurrir que saquemos primero R y luego R o bien primero B y luego R o bien primero Y y luego R. Cada una de estas posibilidades ocurre con probabilidad (2/4)(1/3), lo cual da un total de 1/2.

Al pasar de un estado tipo RRBY a uno con dos colores voy a distinguir dos casos que me parecen esencialmente distintos. Me explico, hay dos maneras de tener dos colores en la urna:

      a) RRBB o GGRR o YYRR, etc… (Dos pares de bolas con el mismo color cada par)

      b) RRRB o GGGR o YYYR, etc… (Tres bolas con el mismo color y otra con distinto)

Al caso a lo voy a denotar como estado 2(2,2) y al b como 2(3,1). Ya, ya, sé que es una notación horripilante, pero no me apetece romperme demasiado el caletre…

Es fácil calcular que la probabilidad de pasar de un estado 3 (tres colores) a uno de tipo 2(2,2) es 1/3 mientras que la de pasar a uno de tipo 2(3,1) es 1/6.

Un poco de paciencia que estamos terminando!!!

Imaginemos ahora que estamos en un estado tipo 2(2,2). ¿Qué puede pasar? Pues que volvamos a caer en el mismo estado o que pasemos a uno de tipo 2(3,1). Las probabilidades respectivas son 1/3 y 2/3.

Se acerca el final!!!

Ahora tenemos una urna con tres bolas del mismo color y una de distinto, es decir que estamos en un estado tipo 2(3,1). De aquí podríamos: volver al mismo estado, ir a 2(2,2) o llegar a una urna con un solo color, con lo cual se habría terminado el jueguecillo. Las probabilidades correspondientes son 1/2, 1/4 y 1/4 respectivamente.

Espero que el anterior galimatías quede un poco más claro con el siguiente esquema:

2017-04-29 12.26.52

Un poco más de notación: E(i) = “Número esperado de pasos para terminar el juego, partiendo del estado i”, donde i puede tomar los valores 1, 2(2,2), 2(3,1), 3,4 o 1. 

Lo que nos piden es calcular E(4), es decir, el número esperado de pasos para llegar a una urna con un solo color, partiendo de una urna con bolas de cuatro colores distintos.

Digamos ahora que estamos en el estado 3. ¿Cuánto vale E(3)? No lo sé, pero sí sé que se tiene que cumplir la siguiente relación: E(3)=1+E(3)/2+E(2(2,2))+E(2(3,1)). Quien no esté convencido que mire el esquema anterior. Repitiendo el mismo razonamiento llegamos al siguiente sistema:

2017-04-29 12.36.24

Echo mano ahora de Wolfram para resolverlo: 

2017-04-29 12.50.18

Lo que nos interesa es x que, como se puede comprobar, tiene un valor de 19/2.

Mentiría si dijese que estoy completamente convencido de que he llegado al resultado correcto, pero ha sido divertido…

Actualización: Vaya, vaya, parece que he metido la pata. En el esquema que detalla las probailidades de paso de un estado a otro hay que intercambiar un par de probabilidades. Ahora queda así:2017-04-29 12.26.52

Con lo que el sistema correspondiente es:

2017-04-29 22.52.51

Lo mando a Wolfram:

Screenshot_2017-04-29-22-59-25

Así que la respuesta correcta es E(1)=9.

 

 

Hagan juego!!!

Hace unos días, navegando por youtube, me encontré con un interesante problema de probabilidad que, al parecer, cayó en un examen de oposiciones de matemáticas para secundaria en Cataluña, en el 2000. Si queréis ver el vídeo, pulsad aquí.

Este es, más o menos, el enunciado:

Tres personas A, B, C, tiran sucesivamente, por este orden, un dado. Gana la primera que saque un seis. ¿Cuál es la probabilidad de ganar de cada una de ellas?

Si veis el vídeo comprobaréis que el autor resuelve el problema utilizando series, lo cual es estupendo, pero a mí se me ha ocurrido otra manera que quería compartir aquí.

Veamos, la probabilidad de que gane A la partida se puede calcular determinando la probabilidad de que gane en la primera tirada o que no lo haga ni A ni B ni C, multiplicando esta última por la probabilidad de que A gane la partida, ya que la situación vuelve a ser idéntica a la inicial. Es decir: P\left( A \right) =\frac { 1 }{ 6 } +{ \left( \frac { 5 }{ 6 }  \right)  }^{ 3 }P\left( A \right)

Razonando de manera análoga: P\left( B \right) =\frac { 5 }{ 6 } \frac { 1 }{ 6 } +{ \left( \frac { 5 }{ 6 }  \right)  }^{ 3 }P\left( B \right)

y

P\left( C \right) ={ \left( \frac { 5 }{ 6 }  \right)  }^{ 2 }\frac { 1 }{ 6 } +{ \left( \frac { 5 }{ 6 }  \right)  }^{ 3 }P\left( C \right) 

 

Ahora es fácil despejar de cada ecuación las probabilidades buscadas:

P(A)=\frac { { 6 }^{ 2 } }{ { 6 }^{ 3 }-{ 5 }^{ 3 } } =\frac { 36 }{ 91 } ,

P(B)=\frac { 5\times 6 }{ { 6 }^{ 3 }-{ 5 }^{ 3 } } =\frac { 30 }{ 91 }  ,

P(C)=\frac { { 5 }^{ 2 } }{ { 6 }^{ 3 }-{ 5 }^{ 3 } } =\frac { 25 }{ 91 }  .

 

Espero que os haya resultado interesante.

¿Quedamos para un picnic?

Oliver Roeder, el encargado del Riddler de FiveThirtyEight, nos propone el siguiente e interesante problema de probabilidad:

On a lovely spring day, you and I agree to meet for a lunch picnic at the fountain in the center of our favorite park. We agree that we’ll each arrive sometime from noon and 1 p.m., and that whoever arrives first will wait up to 15 minutes for the other. If the other person doesn’t show by then, the first person will abandon the plans and spend the day with a more punctual friend. If we both arrive at the fountain at an independently random time between noon and 1, what are the chances our picnic actually happens?

Se me ha ocurrido resolverlo gráficamente, aunque me imagino que también se podría hacer utilizando probabilidad condicionada.

La idea es que, si llamamos x e y al momento en que llega cada uno, el problema se reduce a calcular el área formada por los puntos, situados en el cuadrado unidad, que cumplen la condición:                                                                     |x-y|<=1/4.

Y como, a veces, sólo a veces, una imagen vale más que mil palabras:

2017-04-02 22.22.21

Así que podríamos calcular la probabilidad pedida restándole a 1 el área de los dos triángulos rectángulos, idénticos, de las esquinas:

1-(3/4)^2=0.4375

Si a alguien le interesa el fichero de Desmos que he utilizado para hacer la gráfica, aquí lo tiene.

Actualización: la solución es correcta!!!!