Números bonitos, números feos

Publicado en El País en diciembre de 2012: http://sociedad.elpais.com/sociedad/2012/12/13/actualidad/1355418532_921805.html

Nota: Se ha publicado un libro con la recopilación de los 40 problemas de la saga Desafíos matemáticos. Más información aquí.
 

Desde el año 2011 en la Lotería Navidad se sortean los premios entre los cien mil números que van del 00000 al 99999 (en los décimos los números siempre se escriben con cinco cifras). Aunque todos los números tienen exactamente las mismas posibilidades de resultar premiados, con frecuencia se habla de números bonitos y números feos. Como es una valoración estética, que un número sea bonito o feo depende de los gustos de cada uno.

En este caso un número de lotería nos parecerá bonito si cumple exactamente una, y solamente una, de estas tres condiciones:

a) es divisible entre 5,
b) da resto 2 al dividirlo entre 7,
c) la suma de sus cifras es divisible entre 9.

Por ejemplo el 00037 es bonito porque cumple la condición b pero no las otras dos; sin embargo, el 00324 es feo, ya que cumple las condiciones b y c. De igual forma, podríamos decir que el 00041 y el 00450 son horribles. El primero, porque no cumple ninguna de las tres condiciones; y el segundo, porque es un exagerado y cumple las tres.

El desafío que se propone es decidir cuántos de los números que participan en el sorteo de Lotería de Navidad (recordad, del 00000 al 99999) son bonitos según el criterio expresado anteriormente.

OBSERVACIONES IMPORTANTES.
Puesto que es muy sencillo resolver el desafío con un ordenador (y por supuesto podáis usarlo para inspiraros), la solución que enviéis debe incluir un razonamiento y además hay que utilizar sólo herramientas que estuviesen a disposición de los ciudadanos que asistieron al primer sorteo de lotería celebrado en Cádiz el 4 de marzo de 1812, hace ahora 200 años. Haremos, eso sí, una excepción: no debéis enviarnos las soluciones escritas con pluma de ganso sino por correo electrónico.

El cafè dels matemàtics

Són 3 matemàtics que entren en un bar i el cambrer els pregunta:

- Tots voleu un cafè?

Sorprès per la pregunta, el primer respon:

-No ho sé.

El segon també contesta:

-No ho sé.

Amb rotunditat, el tercer respon:

-Sí

The St. Petersburg paradox

Extracted from wikipedia: http://en.wikipedia.org/wiki/St._Petersburg_paradox,
from the book El libro de las Matemáticas of C. Pickover: http://divulgamat2.ehu.es/divulgamat15/index.php?option=com_content&view=article&id=11733:el-libro-de-las-matematicas&catid=53:libros-de-divulgaciatemca&directory=67, 
and from the article The St. Petersburg Paradox: http://plato.stanford.edu/archives/fall2004/entries/paradox-stpetersburg/.

In 1713, Nicolas Bernoulli, a member of the most famous mathematical family of the history (the Bernoullis), proposed the following problem:

Imagine a game of chance for a single player in which at each stage a coin is tossed. The pot starts at 1 dollar and is doubled every time a head appears. The first time a tail appears, the game ends and the player wins whatever is in the pot. Thus, the player wins $1 if the tail appears in the first toss, $2 if the tail appears in the second toss, $4 if the tail appears in the third toss, and, in general, $2^(k-1) if the tail appears in the k-th toss.

The question is: what would be a fair price to pay for entering the game?

Rational people would enter the game if the expected win is bigger than the price paid to enter the game. In this case, the expected win is:

E = 1/2*1 + 1/4*2 + 1/8*4 + 1/16*8 + ... = 1/2 + 1/2 + 1/2 + 1/2 + ... = infinite

So, if we follow the usual treatment of this kins of problems we would have to play the game at any price if offered the opportunity!

However, some studies showed that many people would pay more than $20. The paradox here is the discrepancy between what people seem willing to pay to enter the game and the infinite expected value suggested by the above analysis.

For more information follow the links in the top of this post, to the Wikipedia, to the book or to the article.

Feu la prova

Publicat al suplement es-Estils de vida de La Vanguardia el 2 de juliol de 2012

 José María Letona, director de l'Escola de Pensament Matemàtic Miguel de Guzmán, proposa de posar a prova el nostre raonament matemàtic amb cinc problemes, alguns de clàssics i d'altres no tant.

1. En qualsevol torneig de tennis, el nombre de participants sempre permet que puguin aparellar-se en qualsevol ronda. Aquest nombre (8,16,34,64, etcètera) és dels que els matemàtics anomenen "potències de 2" i amb ells calcular el nombre de partits que hi haurà al torneig és molt fàcil. Per exemple: amb 16 participants, a la primera ronda hi haurà 8 partits; 4 a la segona; 2 a les semifinals i després 1, la final. En total, 15 partits. Amb 32 participants, hi haurà aquests 15 més els 16 priers. És a dir, 31 partits. En tots dos casos hi ha un partit menys que el nombre de jugadors. Si el nombre de participants no és d'aquesta mena (potència de 2), en algunes rondes hi hauria un nombre imparell de jugadors. Una opció raonable per evitar aquest problema és, en aquests casos, triar un jugador que, per sorteig, passa a la ronda següent. Així, per exemple, amb 13 jugadors passarien a la ronda següent l'escollit més els 6 guanyadors dels 12 partits restants. D'aquests set jugadors, per sorteig, se n'elegeix un que passa a la següent ronda amb els tres guanyadors dels partits restants. Aquests 4 ja juguen com sempre, i el nombre total de partits seria, llavors: 6+3+2+1=12. També un de menys! I amb 2.013 jugadors també deu ser un de menys? I amb qualsevol número?
2. Cadascun dels 1.000 veïns de Matematilandia té un armariet com els dels instituts i el dia de les festes populars munten un joc ben curiós. Va el més jove i obre tots els armariets. El següent els tanca de dos en dos: és a dir, va als armaris 2, 4, 6, 8... i els tanca. El següent va de tres en tres: és a dir, va als armaris 3, 6, 9, 12... i els obre o els tanca segons siguin tancats o oberts, respectivament. El següent, de quatre en quatre, fa el mateix: obrir o tancar. El veí número 500 només va als armariets números 500 i 1.000 i els obre o tanca segons siguin tancats o oberts. I a partir d'ell, els veïns número 501, 502, 503... fins al 1.000 només van a un armari: el que indica el seu número i fan el mateix: obrir-lo o tancar-lo segons el trobin tancat o obert, respectivament. Al final del joc, per tant, alguns armariets estaran oberts i d'altres, tancats. La pregunta al visitant és clara. Sense esperar que s'acabi el joc, sabríeu calcular el número de l'últim aramari que quedarà obert?
3. Dos caçadors es perden en meitat de la caça. Un porta 5 llonguets i l'altre 3. Es troben amb un tercer caçador que no porta res de menjar però sí 8 monedes, i acorden repartir-se els 8 llonguets entre tots tres, a parts iguals, i les 8 monedes entre els dos que aporten el pa. Com s'ha de fer, perquè sigui just, el repartiment de les 8 monedes? *
4. Trieu els 6 números que vulgueu entre els 10 primers. Oi que sempre n'hi ha entre els escollits un que és múltiple d'un altre? I si escollíssiu 17 números entre l'1, 2, 3..., 32 seria segur que n'hi hauria un que seria múltiple d'un altre? I si n'escollíssiu 2.000 entre l'1, 2, 3..., 3.998? I si trieu la meitat més un entre 1,2,3..., 2n?
5. En Pere troba 40 errades en un treball i la Marga, independentment, en troba 33, de les quals 24 són compartides amb en Pere. Quantes errades, aproximadament, se'ls han escapat entre tots dos? Però, si no sabem el nombre d'errades de la feina, com esbrinarem el nombre d'errades que no han detectat (aproximadament)? Es pot fer! 

* Aquest problema el recordeu? És el dels 3 excursionistes, que vaig publicar aquí: http://ferproblemes.blogspot.com/2008/01/els-tres-excursionistes.html

Dynamic programming - The Fibonacci numbers example

Extracted from slides of Chandra Chekuri about Dynamic programming

In this post we will find an introduction to dynamic programming, using as a example a classic problem. In the second part there is a cost analysis of the proposed algorithms in relation with the input size.


Fibonacci numbers are defined by the recurrence

F(0) = 0, F(1) = 1, and F(n) = F(n-1)+F(n-2) for n >=2

The first idea when we want to compute the Fibonacci number for a given n is to use a recursive algorithm like the following:

int fibonacci(int n) {

  if n == 0 return 0;

  if n == 1 return 1;

  return fibonacci(n-1) + fibonacci(n-2);

}

The running time of this algorithm is the following:  
If T(n) is the number of additions of fibonacci(n), then T(n) = T(n-1)+T(n-2) + 1, with T(0) = T(1) = 0, roughly the same as fibonacci(n).

The algorithm does exponential in n additions: T(n) = k^n.

Can we do better?

An iterative solution is the following:

int fibonacci(int n) {

  if n == 0 return 0;

  if n == 1 return 1;

  F[0] = 0; F[1] = 1;

  for (int i = 2; i <= n; i++) {

    F[i] = F[i-1] + F[i-2];

  }

  return F[n];

}

The running time of the algorithm is O(n) additions.

What is the difference?

• Recursion algorithm is computing the same numbers again and again.
• Iterative algorithm is storing computed values and building bottom-up the final value. It uses memoization.

Dynamic programming consists in finding a recursion that can be effectively/efficiently memoized.

Leads to a polynomial time algorithm if the number of sub-problems is polynomial in input size.

And now an important question.

Is the iterative algorithm a polynomial time algorithm? Does it take O(n) time?

Let's examine it:

• Input is n, and hence input size is Θ(log n).
• Output is fibonacci(n), and output size is Θ(n). Why? Because of the size of the numbers being added.
• Hence output size is exponential in input size so no polynomial time algorithm is possible!
• Running time of the iterative algorithm: Θ(n) additions, but the number sizes are O(n) bits long! Hence total time is O(n^2), in fact Θ(n^2).
• Running time of the recursive algorithm: O(k^n), doubly exponential in input size!

Els angles d'un triangle sumen 180 graus

La demostració és senzilla i elegant.

Suposem un triangle amb vèrtexs ABC com, per exemple, el de la figura.
Allarguem tots els costats, i tracem una paral·lela a AB que passi per C.

L'angle a és igual a A, i l'angle b és igual a B, per tal com hem traçat la recta paral·lela.

I l'angle c és igual a C, ja que c i C són dos angles oposats en dues rectes que es tallen, la recta que passa per AC i la recta que passa per BC, i per tant són iguals.

Per tant, a+b+c sumen 180 graus, és a dir, A+B+C sumen 180 graus.

La distància d'edició

La distància d'edició entre dues paraules es defineix com el mínim número de canvis de lletres (addicions, eliminacions o substitucions) que s'ha de fer a una paraula per obtenir l'altra.

Serveix per a poder determinar el grau de semblança entre dues paraules.

• Aquí trobareu la definició de la distància d'edició, anomenada també distància Levenshtein: http://en.wikipedia.org/wiki/Levenshtein_distance
• Aquí trobareu una interessant calculadora online que calcula i detalla els passos seguits per trobar la distància entre dues paraules: http://www.miislita.com/searchito/levenshtein-edit-distance.html