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
  

19 - Quadrats que sumen xifres grans

L'enunciat del dinovè problema era aquest:


http://www.elpais.com/videos/sociedad/Cuadrados/suman/grandes/cifras/elpepusoc/20110721elpepusoc_2/Ves

I la solució la següent:

http://www.elpais.com/articulo/sociedad/unica/suma/posible/elpepusoc/20110726elpepusoc_21/Tes

18 - D'un costat a l'altre

L'enunciahttp://www.blogger.com/img/blank.gift del divuitè problema era el següent:

http://www.elpais.com/videos/sociedad/lado/elpepusoc/20110714elpepusoc_1/Ves/


La solució d'aquest problema es troba aquí:

http://www.elpais.com/articulo/sociedad/caminata/horas/elpepusoc/20110719elpepusoc_20/Tes


Nosaltres el vam solucionar de la següent manera:

.
.
.

Van a tardar 3,46 horas

Explicación
===========

Primero vamos a calcular el punto del triángulo tal que la suma de la distancia a los tres lados sea mínima. Obtendremos un resultado interesante.

Utilizando un sistema de coordenadas euclídeas podemos situar el triángulo con vértices en los puntos (denotaremos con r(x) a la raíz cuadrada de x)

A: (0,0)
B: (0,10)
C: (5*r(3),5)

Las rectas del plano que pasan por los vértices del triángulo son:

r: y = 0
s: 5x - 5r(3)y = 0
t: 5x - 5r(3)y - 50r(3) = 0

Denotando por P = (x,y) al punto buscado, la función a minimizar es f(x,y) = d(P,r) + d(P,s) + d(P,t)

Sabemos que la fórmula de distancia de un punto P = (x,y) a una recta Ax + By + C = 0 viene dada por la fórmula
d(P,r) = |Ax + By + C|/(r(A*A + B*B))

y, después de manipular adecuadamente, vemos que se anulan muchos térmminos y que llegamos a la función constante

f(x,y) = 5r(3)

lo que nos indica que todos los puntos del triángulo son mínimos (y máximos) respecto a la cantidad que buscamos. Además, la distancia de un punto a los tres lados es 5r(3), y como se recorre dos veces cada camino, una para ir y la otra para volver, tenemos que la distancia recorrida en un día es 10r(3) Km.

Si se mueven a 5 Km/h, tenemos que el tiempo total del recorrido es de 2r(3) horas, es decir, 3,46 horas.

17 - Una taula i una estovalla

El dissetè problema de la saga tenia el següent enunciat:

http://www.elpais.com/videos/sociedad/mesa/mantel/elpepusoc/20110707elpepusoc_1/Ves/

La solució d'aquest problema és troba aquí:

http://www.elpais.com/articulo/sociedad/mesa/igualitaria/elpepusoc/20110712elpepusoc_9/Tes

16 - Una mol·lècula de set àtoms

L'enunciat del setzè problema era aquest:

http://www.elpais.com/videos/sociedad/molecula/atomos/elpepudep/20110701elpepusoc_2/Ves/


.
.
.


La solució que vam enviar era la que ve a continuació:

Una posible situación es una molécula con átomos con las coordenadas del fichero adjunto El esquema de la solución está en el esquema adjunto.

Nota: Detalle de la obtención de la solución.

Fijando el punto 1 con coordenadas (0,0), consideramos dos triángulos equiláteros de lado 1 con puntos 1, 2, 3 y 1, 5, 6.
Consideramos además los triángulos 2,3,4 y 5,6,7, también de lado 1.
Finalmente, imponemos que la distancia entre 4 y 7 sea 1.

Inicialmente vemos que la distancia entre 4 y 7 tiene que ser sqrt(3). Por tanto, usando el Teorema de Pitágoras, y situando el punto 4 de modo que sea simétrico al punto 7 respecto al eje vertical, tenemos que las coordenadas de 4 son (-1/2,-sqrt(11)/2), y las de 7 son (1/2,-sqrt(11)/2.

Finalmente usando trigonometría obtenemos las coordenadas de los puntos 2 y 3, y por simetría las de los puntos 5 y 6.

15 - Una qüestió d'uns i zeros

El quinzè problema del concurs era el següent:

http://www.elpais.com/videos/sociedad/cuestion/ceros/elpepusoc/20110623elpepusoc_1/Ves/

Personalment, crec que és el millor que ha sortit fins ara. Malauradament, no vam trobar la solució. Us deixem la solució oficial, on podreu apreciar la bellesa d'una demostració ben senzilla.

http://www.elpais.com/articulo/sociedad/ceros/palomas/elpepusoc/20110628elpepusoc_13/Tes

14 - Partícules en col·lisió

El catorzè problema de El País era el següent:

http://www.elpais.com/videos/sociedad/Particulas/colision/elpepusoc/20110616elpepusoc_1/Ves/


La solució publicada a la web és la següent:

http://www.elpais.com/articulo/sociedad/habra/unica/clase/particulas/elpepusoc/20110621elpepusoc_9/Tes


I la solució que vam aportar nosaltres és aquesta:



No se puede diseñar ninguna secuencia de choques tal que todas las partículas terminen en el mismo estado.

Expliación:
===========

Analizamos un paso de la secuencia de choques.
Supongamos que tenemos un estado (a,b,c) con a partículas en estado positivo, b partículas en estado negativo y c partículas en estado neutro.
A partir de este estado, los distintos choques que cambian estado s de partículas son los siguientes

- Chocan una partícula positiva y una negativa -> estado (a-1,b-1,c+2)
- Chocan una partícula positiva y una neutra -> estado (a-1,b+2,c-1)
- Chocan una partícula negativa y una neutra -> estado (a+2,b-1,c-1)

Observamos que si calculamos el residuo módulo 3 de las diferencias entre los estados de cada tipo de partículas (es decir, si tenemos el estado (x,z,y) entonces estos cálculos son x-y mod 3, y-z mod 3 y z-x mod 3) los valores se mantienen entre estados obtenidos mediante las transformaciones especificadas, es decir, entre el estado (a,b,c) y cada uno de los tres estados obtenidos con choques.

Por tanto, una condición necesaria para que haya solución es que alguno de los estados finales deseados (57,0,0), (0,57,0) o (0,0,57) tengan las mismas diferencias que el estado inicial (30,10,17).

Vemos que las diferencias de este estado inicial son

30-10 mod 3 = 1
10-17 mod 3 = 2
17-30 mod 3 = 1

Es decir, ninguno de los valores comparte el mismo residuo módulo 3.
En cambio, cualquiera de las soluciones tiene todos las diferencias con el mismo residuo módulo 3, 0.
Por tanto, se trata de estados incompatibles, es decir, a partir del estado inicial no se puede conseguir ninguno de los estados finales deseados.

13 - Una camisa brodada

L'enunciat i solució del tretzè problema es troba aquí:

http://www.elpais.com/videos/sociedad/camiseta/bordada/zigzag/elpepusoc/20110609elpepusoc_1/Ves/

La solució publicada a la web és aquesta:

http://www.elpais.com/articulo/sociedad/camisa/bordada/angulo/45/elpepusoc/20110614elpepusoc_10/Tes



.
.
.


La solució que vam aportar és aquesta:


.
.
.



La solución a las tres preguntas que presento es la siguiente:

1. 4,5 grados
2. 1,9675 cm
3. No se puede realizar

Explicación
===========

Observamos que, al ir trazando las líneas de longitud l entre los dos lados del ángulo estamos obteniendo triángulos isósceles, es decir, triangulos que tienen dos lados iguales, y también dos ángulos iguales.

Por definición, tenemos que el ángulo inicial es alpha.

Vemos con un simple dibujo que el ángulo que forma el segundo trazo con la base horizontal del ángulo es 2 * alpha.
Sucesivamente observamos que el ángulo que forma el tercer trazo con la parte no horizontal del ángulo es 3 * alpha.
El ángulo que forma el cuarto trazo con la parte horizontal es 4 * alpha.
...
El ángulo que forma el decimoctavo trazo con la parte horizontal es 18 * alpha.
El ángulo que forma el decimonoveno trazo con la parte no horizontal es 19 * alpha.
El ángulo que forma el vigésimo trazo con la parte horizontal es 90 grados, por hipótesis, y también 20 * alpha grados, por construcción.

Por tanto, tenemos la ecuación 90 = 20 * alpha, que tiene por solución alpha = 4,5 grados.

Si el lado inferior mide 25 cms, usando trigonometría tenemos que

l = 25 * tan(4,5) = 1,9675 cms.

Finalmente, observamos que no existe solución con ventiún trazos, ya que el trazo vigésimoprimero sería vertical, formando un ángulo de 90 grados con la parte horizontal del ángulo. Eso implicaría que el triángulo isósceles no sería un triángulo "normal" sería un triángulo con un sólo dos lados, lo cual significaría que estaríamos repitiendo un trazo.


Nota: Me ha costado bastante encontrar la solución, ya que inicialmente entendí que el vigésimo trazo tenía que finalizar en la línea horizontal. Al final dí en el hecho que podía finalizar en el segmento no horizontal y encontré la solución.

12 - Una exhibició de cotxes de carreres

El dohttp://www.blogger.com/img/blank.giftzè problema anava sobre cotxes de carreres:

http://www.elpais.com/videos/sociedad/exhibicion/coches/carreras/elpepusoc/20110601elpepusoc_1/Ves/


La solució publicada a la Web és aquesta:

http://www.elpais.com/articulo/sociedad/cuadrado/coches/lado/elpepusoc/20110608elpepusoc_1/Tes


.
.
.


La solució que vam enviar és aquesta:


Van a participar 400 coches.

Explicación
===========

El número de coches totales es n*n.
Un rectángulo con el mismo número de coches que el cuadrado, con el formato pedido va a tener
n+5 filas
y
n*n / (n+5) columnas

El problema consiste en buscar, si existe, un valor de n tal que n*n / (n+5) sea entero y ver si este valor es único.

Un modo de verlo es el siguiente:

Definamos la función f(x) = x - x*x/(x+5)
Esta función es creciente: f'(x) > 0 para todo valor de x positivo.
Esta función tiene como máximo 5: podemos ver que f(x) < 5 para todo valor de x positivo.

Observamos que: Encontrar una solución entera a x*x/(x+5) es equivalente a encontrar una solución entera de f(x)
Las soluciones enteras de f(x) sólo pueden tomar 4 valores: 1,2,3,4

Sabiendo que f(x) es creciente, vemos (usando por ejemplo una hoja de cálculo) que la unica de estas condiciones que se cumple es cuando x = 20. En este caso f(x) = 4.

Por tanto, si n (o x) es igual a 20, el número de coches tiene que ser 20*20 = (20+5) * (20*20) / (20+5) = 25 * 16 = 400.

11 - Pesant cargols

L'onzè phttp://www.blogger.com/img/blank.gifroblema era el següent:

http://www.elpais.com/videos/sociedad/Pesando/tornillos/elpepusoc/20110526elpepusoc_1/Ves/




La solució publicada a la web es troba aquí:

http://www.elpais.com/articulo/sociedad/Basta/sola/pesada/tornillos/elpepusoc/20110531elpepusoc_19/Tes


.
.
.


La solució que vam enviar és aquesta:


Con una pesada basta.

Explicación
===========

Vamos a dar un modo de obtenerlo con una pesada. Como es el mínimo posible, no hará falta demostrar nada más.

Existen C(6,3) = 20 posibilidades distintas de distribución de las cajas que contienen los tornillos de 6 gramos:

Que estén en las cajas:

01. 1,2,3
02. 1,2,4
03. 1,2,5
04. 1,2,6
05. 1,3,4
06. 1,3,5
07. 1,3,6
08. 1,4,5
09. 1,4,6
10. 1,5,6
11. 2,3,4
12. 2,3,5
13. 2,3,6
14. 2,4,5
15. 2,4,6
16. 2,5,6
17. 3,4,5
18. 3,4,6
19. 3,5,6
20. 4,5,6

Si ponemos:

- 0 tornillos de la 1a caja
- 1 tornillo de la 2a caja
- 2 tornillos de la 3a caja
- 4 tornillos de la 4a caja
- 7 tornillos de la 5a caja
- 13 tornillos de la 6a caja

Vemos que el peso que dará la báscula en cada una de las veinte posibilidades será distinta, lo que nos permitirá identificar exactamente qué combinación es la buena.

01. 1,2,3 - Peso = 138 gramos
02. 1,2,4 - Peso = 140 gramos
03. 1,2,5 - Peso = 143 gramos
04. 1,2,6 - Peso = 149 gramos
05. 1,3,4 - Peso = 141 gramos
06. 1,3,5 - Peso = 144 gramos
07. 1,3,6 - Peso = 150 gramos
08. 1,4,5 - Peso = 146 gramos
09. 1,4,6 - Peso = 152 gramos
10. 1,5,6 - Peso = 155 gramos
11. 2,3,4 - Peso = 142 gramos
12. 2,3,5 - Peso = 145 gramos
13. 2,3,6 - Peso = 151 gramos
14. 2,4,5 - Peso = 147 gramos
15. 2,4,6 - Peso = 153 gramos
16. 2,5,6 - Peso = 156 gramos
17. 3,4,5 - Peso = 148 gramos
18. 3,4,6 - Peso = 154 gramos
19. 3,5,6 - Peso = 157 gramos
20. 4,5,6 - Peso = 169 gramos

10 - Com omplir amb peces un tauler

L'enunciat del desè problema era el següent:

http://www.elpais.com/articulo/sociedad/tablero/cubierto/piezas/elpepusoc/20110525elpepusoc_13/Tes

Aquest problema no el vam poder solucionar satisfactòriament. Us recomanem que llegiu la solució exposada a la pàgina web.

9 - Una enorme potència de 2

L'enunciat del novè problema el podeu veure aquí:

http://www.elpais.com/videos/sociedad/enorme/potencia/elpepusoc/20110512elpepusoc_2/Ves/


.
.
.


I la solució que vam enviar és la següent.

.
.
.


Las dos últimas cifras del número buscado son 52.

Explicación
===========

Si analizamos las dos últimas cifras de la sucesión de potencias de 2, vemos que se repiten cada 20 dígitos (con una sola excepción, al principio tenemos 2^1 = 2, con lo que las últimas dos cifras son 02, mientras que en los números 2^21, 2^41, etc las dos últimas cifras son 52).

Exponente Dos últimas cifras
1 2
2 4
3 8
4 16
5 32
6 64
7 28
8 56
9 12
10 24
11 48
12 96
13 92
14 84
15 68
16 36
17 72
18 44
19 88
20 76
21 52
22 4
23 8
24 16
25 32
26 64
27 28
28 56
...


Por tanto, las dos últimas cifras del número buscado 2^528*****7301 son las mismas que las del número 2^7301, que son las mismas que las del número 2^21, es decir, 52.

8 - Un cub de suma zero

L'enunciat del vuitè problema del concurs d'El País el podeu veure aquí:

http://www.elpais.com/articulo/sociedad/cubo/suma/cero/existe/elpepusoc/20110511elpepusoc_14/Tes

i la resposta que vam enviar la teniu a continuació.


.
.
.


No se puede construir el cubo pedido.

Lo vemos con una observación inicial y razonando a partir de ella.

Observación
===========
Al cambiar el valor de un vértice de 1 a -1 o viceversa, la diferencia entre la cantidad de vértices y caras con valor 1 antes y después es siempre par: -4, -2, 0, 2 o 4.

Es sencillo ver esto. El cambio de un vértice afecta al vértice en cuestión y a tres caras del cubo, las adyacenetes al vértice. Todos los casos posibles son los siguientes:

- Si las tres caras y el vértice tenían valor -1, al cambiar el vértice la diferencia aumenta en 4 unidades.
- Si las tres caras tenían valor -1 y el vértice 1, al cambiar el vértice la diferencia aumenta en 2 unidades.
- Si dos caras tenían valor -1 y el vértice también, al cambiar el vértice la diferencia aumenta en 2 unidades.
- Si dos caras tenían valor -1 y el vértice 1, al cambiar el vértice la diferencia se mantiene igual.
- Si dos caras tenían valor 1 y el vértice -1, al cambiar el vértice la diferencia se mantiene igual.
- Si dos caras tenían valor 1 y el vértice 1, al cambiar el vértice la diferencia disminuye en 2 unidades.
- Si las tres caras tenían valor 1 y el vértice -1, al cambiar el vértice la diferencia dismunuye en 2 unidades.
- Si las tres caras y el vértice tenían valor 1, al cambiar de signo el vértice la diferencia disminuye en 4 unidades.


Visto esto, vemos también que

1. Dada una asignación de 1's y -1's a los vértices, la suma es única.
2. Partiendo de la posición con 1's en todos los vértices, y por tanto suma 8 + 6 = 14, podemos obtener cualquier asignación posible cambiando 1's por -1's.
3. Cualquier asignación válida será de estas, ya que si no realizando cambios hasta llegar a la configuración con 1's en todos los vértices llegaríamos a una contradicción.
4. Por tanto, por la observación inicial, toda asignación válida tiene un número par de elementos con valor 1.

La posición que se pide, en que la suma total es 0, corresponde a que 7 elementos entre caras y vértices tomen por valor 1.
Pero esto no puede ser ya que todas las posiciones válidas tienen un número par de elementos con valor 1.

Por tanto, no se puede construir el cubo pedido.

7 - Un piano musical

El setè problema de la saga anava sobre les tecles d'un piano musical:

http://www.elpais.com/articulo/sociedad/Solucion/problema/piano/sorpresa/musical/elpepusoc/20110503elpepusoc_7/Tes

Us recomanem visitar aquesta pàgina, on el problema i les solucions proposades estan molt ben explicades.

La solució que vam enviar és la següent:




1) Se habrán pulsado 2000 Do's.
2) Las notas Mi, Sol y La no se pulsan nunca.


Explicación
===========

En todo el proceso sólo se tocan cuatro notas diferentes:

- Do
- Re
- Fa
- Si

Si identificamos a:

- Do como el conjunto de números congruentes con 1 módulo 7
- Re como el conjunto de números congruentes con 2 módulo 7
- Fa como el conjunto de números congruentes con 4 módulo 7
- Si como el conjunto de números congruentes con 0 módulo 7

Vemos que sólo se tocan estas notas ya que el procedimiento que se aplica tiene un ciclo que se va repitiendo. Este ciclo de notas que se pulsan es el siguiente (denotamos con = el signo de congruencia módulo siete):

- 1
- 1 + 1 = 2
- 2 + 2 = 4
- 4 + 3 = 7 = 0
- 0 + 4 = 4
- 4 + 5 = 9 = 2
- 2 + 6 = 8 = 1
- 1 + 7 = 1 + 0 = 1
- 1 + 8 = 1 + 1 = 2
- 2 + 9 = 2 + 2 = 4
...


Vemos que la secuencia que se va repitiendo es:

1240421124042112404211...,

que corresponde a las notas

Do Re Fa Si Fa Re Do Do Re Fa Si Fa Re Do Do...

También vemos que de cada 7 teclas pulsadas dos son Do's. Por tanto, si se pulsan 7000 teclas se habrán pulsado 2000 Do's.

En resumen:

1) Si se pulsan 7000 teclas se habrán pulsado 2000 Do's.
2) Las notas Mi, Sol y La no se pulsan nunca.