sábado, 13 de enero de 2018

Cadena más larga de 100 números

Le he estado dando vueltas a un problema curioso en http://simplementenumeros.blogspot.com.es/2013/05/1130-los-numeros-del-1-al-100.html. Se trata de formar la cadena más larga posible con los números del 1 al 100, de forma que cada número en la cadena sea o bien múltiplo o bien divisor de sus vecinos.

Una solución es la siguiente cadena de 77 números:

76-38-19-95-5-85-17-34-68-4-92-46-23-69-3-87-29-58-2-62-31-93-1-77-11-99-33-66-22-44-88-8-96-32-64-16-48-24-72-36-18-54-27-81-9-63-21-42-84-28-56-14-98-49-7-35-70-10-80-40-20-100-50-25-75-15-45-90-30-60-12-6-78-39-13-26-52

En realidad hay muchas soluciones con 77 números; por ejemplo, en esta cadena se pueden intercambiar las posiciones de 26 y 52, y de 40 y 80.

La cadena tiene la siguiente estructura:

  • 4 múltiplos de 19, y el 5;
  • 4 múltiplos de 17, y el 4;
  • 4 múltiplos de 23 y el 3;
  • 3 múltiplos de 29 y el 2;
  • 3 múltiplos de 31 y el 1;
  • y finalmente una cadena de 54 números múltiplos de 2, 3, 5, 7, 11 y 13.

Es fácil ver que en la solución no deberían aparecer los primos mayores que 50; 53,59,61,67,71,73,79,83,89 y 97; porque sólo se pueden conectar al 1. Ni tampoco aquellos primos entre 33 y 50 junto con sus dobles, 37 y 74, 41 y 82, 43 y 86, 47 y 94; porque sólo se pueden conectar al 1 y al 2. En cambio, los múltiplos de 17, 19, 23, 29 y 31 sí pueden aparecer, porque son 5 grupos con más de tres números que sólo se pueden conectar al 1,2,3,4,5. Si en la solución apareciese por ejemplo el 37, sería porque alguno de estos primos no aparecería, y por tanto se podría alargar la solución quitando el 37 y poniendo el primo que no estaba.

Aparte de estos 18 números (primos > 50 y primos y dobles entre 33 y 50) que sabemos que no pueden aparecer, hay otros 5 que no aparecen en la solución dada: 51, 55, 57, 65 y 91. El 51 y 47 son múltiplos de 17 y 19 y podrían aparecer, pero entonces tendrían que desaparecer el 85 y el 95.

Así que en realidad sólo se podría mejorar la solución en 3 números. Pero esto no es posible. La cadena larga, a partir del 1, es la más larga posible (demostrado por ordenador). Es verdad que podríamos quitar, por ejemplo, los múltiplos de 31 para dejar libre el 1, con lo cual podríamos enganchar algún otro número. Pero es que en la solución ya hay tres múltiplos de 31; incluso si pudiésemos enganchar los tres números que nos faltan, perderíamos otros 3, con lo cual no mejoraríamos la longitud de la cadena.

Total, que queda por ver cómo encontrar la cadena larga. El problema se puede formalizar como buscar el camino más largo posible en un grafo de 57 vértices. Se podría usar backtracking a lo bruto, pero esto tarda demasiado.

Una primera mejora para podar el árbol es, antes de probar a explorar un nuevo vértice, contar el número de vértices en su componente conexa. Si la componente conexa tiene N vértices, la cadena que ya he explorado tiene longitud L, y de momento el récord de cadena más larga que he encontrado es R, entonces no tiene sentido explorar si N+L <= R, no se podrá batir el récord. Esto mejora una burrada el tiempo de búsqueda, pero sigue siendo lento.

La clave para conseguir explorar todo el árbol de caminos es darse cuenta de que los grafos que quedan por explorar son bastante "fibrosos". Al principio hay unos cuantos números muy conectados, pero tienen a desaparecer pronto y dejar un grafo deshilachado. Por ejemplo, uno que aparece relativamente pronto y que estuve depurando en detalle es éste:

Se entra por el 35. Aunque tiene 21 vértices, está claro que los dos caminos más largos posibles son de sólo 11. Una forma de afinar la cota sería darse cuenta de que en ese grafo hay 6 hojas (vértices con un único vecino) y como sólo podremos usar como mucho uno de ellos (porque ahí se acaba el camino), aunque el grafo tenga 21 vértices podemos acotar los vértices útiles a 21-6+1.

Pero claro, podemos repetir esta observación... en un grafo como éste, si primero quitamos las hojas 21,25,35, nos queda otro grafo con hojas, así que le quitamos 3 y 5 y finalmente nos queda un grafo con 1 vértice sin hojas (15 no es hoja porque está conectado al principio del camino). Así que en ese grafo el camino más largo que podremos recorrer es de 1+2 vértices (1 es el número de vértices en el grafo final y 2 es el número de veces que hemos eliminado hojas).

Acotando de esta forma la longitud del camino máximo dentro de un subgrafo, se puede explorar todo el grafo de 57 vértices en unas 24 horas.

viernes, 12 de enero de 2018

Historias y probabilidades

He estado leyendo un libro, "El andar del borracho: cómo el azar gobierna nuestras vidas". Aparte de la novelesca biografía de Cardano en el capítulo 3, hay una cosa que me ha intrigado.

Imagínate que te pregunto "¿qué es más probable, que a mi empresa le vaya bien el año que viene, o que a mi empresa le vaya bien el año que viene a causa de la recuperación económica mundial?"

Vale, la pregunta es un poco ambigua, y además habría que adornarla un poco y poner otras opciones para que la trampa no sea tan descarada, pero incluso con esta presentación tan chusca, esta pregunta ha desconcertado a varios de mis compañeros de trabajo, varios de los cuales escogieron la segunda alternativa.

Bueno, pues no, la más probable es la primera; siempre que ocurra que a mi empresa le vaya bien _Y_ haya recuperación económica mundial _Y_ la causa de que a mi empresa le vaya bien sea la recuperación económica mundial (tres condiciones), ocurrirá que a mi empresa le irá bien (una condición).

Esta observación debería de ser obvia, pero la gente cae en ella con facilidad en cuanto la trampa se disimula un poco. Cuando quieres convencer a alguien de algo improbable, en vez de analizar las cosas, lo que tienes que hacer es contarle una historia. Esto lo saben perfectamente los abogados que tienen que convencer a un jurado de algo que normalmente resultaría obviamente falso; se inventan una historia en la que cada paso conecte con el siguiente, y así consiguen esquivar la capacidad de la gente de estimar si algo es creíble o no. Eso sí, no intentes esto con el juez: el profesional pasará de tus milongas y mirará el informe de balística. Así es como funcionan también las conspiranoias.

miércoles, 10 de enero de 2018

Otro problema chulo de grafos

Hace tiempo leí otro de esos problemas chulos de grafos sin datos, vagamente parecido al que ya conté de los señores Mancha, aunque este es más fácil.

Resulta que en una fiesta los invitados cumplen la siguiente propiedad más bien especialísima: para cada par de invitados, existe exactamente un invitado al que conocen los dos. Pregunta: ¿cómo es la fiesta?

Formas de montar una escena

Un amigo mío que es director de películas me contó intrigado el siguiente problema. En un libro sobre composición, donde querían enfatizar lo complicado que puede ser montar una escena, contaban que si tienes n tomas, entonces puedes montarlas de N=e·n!-1 formas diferentes para construir la escena, lo cual implica que habrá tantas posibilidades de hacerlo que no será nada fácil decidir entre ellas.

Un ejemplo para aclarar el problema. Quieres mostrar una fiesta en una habitación y tienes cinco tomas; en ellas, la cámara enfoca la puerta, un sofá, el balcón, la mesa con la comida, y la pista de baile. Podrías desechar algunas tomas, o usar sólo un trozo de alguna toma, pero claro, tienes que usar al menos una toma.

¿De cuántas formas se puede hacer esto? Se podrían usar las 5 tomas, mostrándolas ordenadas de 5!=120 formas diferentes. También se podrían usar cuatro tomas; se podrían escoger de comb(5,4)=5 formas, y para cada elección, las tomas seleccionadas se podrían mostrar ordenadas de 4!=24 formas diferentes. O tres, o...

En términos matemáticos, se quiere el número de permutaciones de subconjuntos no vacíos de un conjunto de n elementos.

En total,

Así que la fórmula es rara pero correcta, al redondear el resultado al entero más cercano dará la respuesta correcta.

Ese -1 es peculiar. Sería raro que te preguntasen qué permutaciones hay en el término e·n!. Sin embargo, está muy claro cuál es la permutación que no hay en el -1: la del conjunto vacío.

domingo, 3 de septiembre de 2017

El problema de las n reinas

La noticia mal contada es que ofrecen un millón de dólares por resolver el problema de las 8 reinas en el tablero de ajedrez. En realidad, el problema es que en un tablero de n x n ya tienes colocadas algunas reinas, y se trata de poner las que faltan. Bueno, no basta con hacerlo, hay que demostrar si existe o no un algoritmo que en tiempo polinómico decida si es posible hacerlo o no. Como han demostrado que este problema es NP completo, en realidad han subido el premio por resolver P = NP de uno a dos millones de dólares.

Pobrecillos, me pregunto cuántas cartas habrán recibido ya de gente reclamando el premio. Aunque lo mismo el propósito era hacerse publicidad aprovechándose de que los periodistas tienen que escribir artículos en cinco minutos.

http://www.hispantv.com/noticias/deporte/352348/premio-million-problema-ajedrez-ocho-reinas

http://jair.org/media/5512/live-5512-10126-jair.pdf

sábado, 11 de febrero de 2017

Los colores viven en un cono

El modelo de colores HSV es un plano proyectivo, donde el origen corresponde a los grises y las clases de equivalencia corresponden a "tonos de color" dentro de las que varía la saturación, junto con una dimensión adicional que es el brillo.

Vaya frikez; la próxima vez que me pregunten para qué sirven las geometrías exóticas, ya sé qué responder.

https://en.wikipedia.org/wiki/HSL_and_HSV

https://es.wikipedia.org/wiki/Modelo_de_color_HSV

martes, 19 de julio de 2016

Algoritmos para el problema de los vales

(Esta entrada es continuación de ésta).

Recordatorio: el problema consiste en que queremos comprar unos productos de precios pi y nos dan un vale de descuento por cada compra de C euros o mayor; así que tenemos que dividir los productos en varias compras, de forma que consigamos el mayor número posible de vales de descuento. En realidad, el planteamiento original era que el precio tenía que ser mayor que C.

Vale, ya sabemos que es imposible encontrar siempre rápidamente la mejor solución. ¿Pero cómo encontramos rápidamente una solución razonablemente buena?

Mi amigo sugirió este algoritmo:

Yo sugerí este otro. Tiene la pega de que hace falta suponer que todos los precios son múltiplos de un céntimo para poder calcular rápidamente la lista de todos los posibles precios.

  • Mientras el precio de los artículos que quedan por pedir exceda C:
    • Averiguar el precio de pedido más pequeño que se puede hacer que exceda C
    • Encontrar un conjunto de artículos que tenga ese precio
    • Hacer un pedido con ese conjunto
  • Añadir los artículos que sobran al último pedido, si se ha hecho algún pedido, o hacer con ellos el primer pedido.

Los dos algoritmos se ejecutan en tiempo polinómico, así que o bien P=NP y lo hemos resuelto, o bien estos algoritmos no siempre encuentran la solución óptima. He aquí dos ejemplos en los que fallan:

  • C=20 y los precios son {6,6,6,7,8,9}. En este caso, el primer algoritmo falla, porque al meter los dos precios mayores en la misma compra se queda sin encontrar la solución óptima, que es {9,6,6}, {8,7,6}. El segundo algoritmo sí que acierta, porque es posible hacer una compra de 21, luego la otra también tiene que ser de 21.
  • C=20 y los precios son {7,7,7,15,15,15}. Ahora el primer algoritmo acierta, porque encuentra la solución {7,15}, {7,15}, {7,15}, pero el segundo algoritmo falla, porque el precio más bajo superior a 20 es 21, así que empieza haciendo la compra {7,7,7}, y luego no puede conseguir dos vales más.

viernes, 15 de julio de 2016

El problema de los vales

He estado pensando con un amigo sobre el siguiente problema.

Quiero comprar en un supermercado n productos de precios estrictamente positivos {pi}. Por cada compra que haga de más de C euros me dan un vale de descuento. ¿Cómo tengo que particionar los productos que quiero comprar en varias compras, de forma que el número de vales de descuento que consiga sea máximo?

Este problema tiene toda la pinta de ser NP-completo, y tras darle varias vueltas, hemos conseguido una demostración bastante fea, reduciendo a él el problema del bin packing, que sabemos que es NP-completo.

Empezaremos formulando los dos problemas formalmente:

  1. Vales. Dados un número de productos n, sus precios {pi>0}i=1n, y la cantidad mínima C con la que obtener un vale, encontrar una partición {Si} de {pi} con el número máximo de conjuntos tales que ΣSipi > C. Dada una solución, llamaré pki a los precios de los productos de la compra k.
  2. Bin packing. Dada una colección ilimitada de contenedores de volumen V, un número de objetos n, y sus volúmenes {ai<V}i=1n, encontrar una partición {Si} de {ai} con el número mínimo de conjuntos tales que ΣSiai ≤ V. Dada una solución, llamaré aki a los volúmenes de los objetos del contenedor k. (Estos objetos sólo tienen tamaño, no forma; por ejemplo, como al guardar ficheros en un disco duro.) (Podría haber objetos de volumen ai=V, pero como ellos solos llenarían un contenedor, los quitaría del problema.)

La idea de la demostración es sencilla, consiste simplemente en tomar pi = V-ai, pero se complica bastante por el camino.

Vamos al grano. Supongamos que puedo resolver los problemas de vales en tiempo polinómico, y que tengo un problema de bin packing.

Para este problema de bin packing tendré un ε>0 definido de la siguiente manera:

ε < min( min{ai}, (min{Σsi : {si}⊂{ai}, Σsi>V} - V) / n)

Es decir, ε es menor que cualquier ai, y de todas las sumas de volúmenes mayores que V, me quedo con la menor, resto V, y divido entre n. Este ε tiene la propiedad de que si Σ(aki-ε)<V, entonces Σaki≤V; porque, de lo contrario, Σaki>V y estaría dentro del conjunto de la definición de ε, luego ε≤(Σaki-V)/n, y por tanto V≤Σaki-n·ε; pero, dado que como mucho hay n términos en la suma, V≤Σ(aki-n), y de aquí la contradicción.

Claro, esta definición plantea un problema filosófico; dado que en principio hay un número exponencial de posibles sumas, ¿cómo calcular ε en tiempo polinómico? Es una buena pregunta, que afea esta demostración. En realidad, no hay que calcular ése epsilon, vale cualquier número menor. Por ejemplo, si los volúmenes de todos los objetos fuesen múltiplos de 1 centímetro cúbico, entonces podría tomar ε = 1cc / n, sin preocuparme de si el mínimo es 1cc o 2cc o 3cc o lo que sea.

Sigamos. Para un m arbitrario (que no tiene por qué ser el número mínimo de contenedores, es simplemente un número) puedo considerar el siguiente problema de vales (nótese que ε no depende de m):

  1. Hay n·m productos;
  2. el precio de los n primeros productos es V-ai+ε;
  3. el precio de los siguientes n·(m-1) productos, que llamaré comodines, es V;
  4. para conseguir un vale tengo que hacer una compra de más de C = (n-1)·V.

A continuación demostraré cuatro proposiciones sobre este problema que depende de m.

Primera, todos los productos en este problema tienen un precio pi≤V, y los únicos que tienen precio V son los comodines. Porque si V-ai+ε>V, entonces ε>ai.

Segunda, si el problema de vales con m tiene soluciones con m compras, entonces todas sus compras tienen exactamente n productos. Porque si una compra tuviese n-1 productos, la suma de sus precios sería como mucho (n-1)·V = C, de forma que no conseguiría un vale, así que cada compra contiene al menos n productos. Pero en total hay m compras y n·m productos, así que cada compra tiene que contener exactamente n productos.

Tercera, si el problema de bin packing tiene una solución con m contenedores en la que ningún contenedor está vacío, entonces el problema de vales tiene al menos una solución con m vales, en la que ninguna compra consiste sólo en comodines. Esta solución se obtiene a partir de la solución del problema de bin packing, convirtiendo cada contenedor en una compra, mandando los jk objetos del contenedor k con volumen aki a productos de la compra k con precio V-aki+ε, y luego añadiendo n-jk comodines de precio V hasta tener n productos; se consigue un vale por cada compra porque, como Σaki≤V, entonces

Σpki = Σ(V-aki+ε) + (n-jk)·V
= jk·V - Σaki + jk·ε + n·V - jk·V
= n·V + jk·ε - Σaki
≥ n·V + ε - V = C + ε > C

donde sabemos que jk≥1 por la condición de que hay al menos un objeto en cada contenedor, que se traduce en que en la compra k hay al menos un producto que no es un comodín.

Cuarta, si el problema de vales tiene una solución con m vales, entonces el problema de bin packing tiene una solución con m contenedores (a diferencia de la tercera proposición, aquí se permiten contenedores vacíos y compras de sólo comodines). Como antes, generamos la solución del problema de bin packing a partir de la solución del problema de vales, mandando la compra k al contenedor k; como Σpki>C=(n-1)·V, y en esa suma hay n-jk comodines,

Σ(V-aki+ε) + (n-jk)·V > (n-1)·V

jk·V - Σ(aki-ε) + (n-jk)·V > (n-1)·V

V > Σ(aki-ε)

Al definir ε se demostró que esa última desigualdad implica Σaki ≤ V, y por tanto se satisfacen las condiciones para ser una solución del problema de bin packing; además, como había al menos un producto que no era un comodín, tiene que haber al menos un objeto de volumen >0 en el contenedor k, que por tanto no está vacío.

Juntando todo esto, el siguiente algoritmo encuentra la solución del problema de bin packing en tiempo polinómico:

  • Si no hay objetos, devolver m = 0.
  • Para m = 1, 2, ...
  •     Si el problema de vales con m tiene una solución, devolver m.

Para empezar, mientras m sea tan pequeño que el problema de bin packing no tenga soluciones porque m contenedores no bastan, el problema de vales tampoco la tendrá, por la cuarta proposición. Pero justo cuando alcancemos el m mínimo para que bin packing tenga una solución sin contenedores vacíos, entonces el problema de vales tendrá una solución, con m compras donde ninguna compra consistirá sólo en comodines, por la tercera proposición. Aquí hay que hacer la observación de que con el m mínimo no puede haber soluciones con contenedores vacíos... porque entonces eliminaríamos un contenedor vacío y tendríamos una solución con m-1 contenedores, de forma que m no sería mínimo.

Finalmente, ese algoritmo se ejecuta en tiempo polinómico porque el problema de bin packing contiene al menos n datos (los volúmenes de los n objetos), de forma que repetir algo n veces es polinómico en el tamaño del problema. Pero metiendo cada objeto en un contenedor diferente obtengo una solución trivial con n contenedores, así que el m mínimo tiene que ser menor o igual que n. Como cada ejecución del bucle se hace en tiempo polinómico, el tiempo total también lo es.

Quizás todo quede más claro con un ejemplo. Quisiera resolver el problema de bin packing consistente en guardar n=3 objetos de volúmenes 4, 6 y 7 en contenedores de volumen V=10. Como todos los volúmenes son múltiplos de 1, puedo tomar ε = 1/n = 1/3. Hay más de 0 objetos, luego no me basta con 0 contenedores. Pruebo m=1; es decir, resuelvo el problema de los vales con precios 10-ai+ε = 6.33, 4.33 y 3.33, y me dan un vale por compras de más de (n-1)·V = 20; obviamente no hay solución, porque el precio de todos los productos juntos, 6.33+4.33+3.33=18, no llega a 20. Pruebo ahora con m=2; a los productos de antes añado tres comodines de precio V=10, así que tengo 6 productos de precios 6.33, 4.33, 3.33, 10, 10 y 10. Ahora sí que hay soluciones, en concreto una: las dos compras son {6.33, 4.33, 10}>20 y {10, 10, 3.33}>20; por tanto, hay soluciones del problema de bin packing, que obtengo eliminando los comodines y restando del volumen y ε, para quedarme con {4,6}≤10 y {7}≤10. También puedo mirar qué habría ocurrido para m=3; en este caso podría encontrar una solución como {6.33, 4.33, 10}>20, {10, 10, 3.33}>20 y {10, 10, 10}>20, que me indicaría que m es demasiado grande porque contiene una solución con n=3 comodines; pero también podría encontrar una solución como {10, 10, 3.33}>20, {10, 10, 4.33}>20 y {10, 10, 7.33}>20, que me indicaría que 3 contenedores son suficientes, pero me dejaría con la duda de si hay soluciones con menos contenedores (como el algoritmo prueba todos los m en orden creciente, nunca llego a tener la duda, siempre habré probado m=2 antes de probar m=3).

Ahora un ejemplo en el que el truco con ε resulta crucial. Tendremos n=2, volúmenes 4 y 6, y C=10. La solución es, obviamente, {4, 6}≤10. Pero si no fuese por el ε, el problema de vales no tendría solución, ya que los precios serían 10-4=6 y 10-6=4, pero claro, 6+4≯C=(n-1)·V=10. En este caso ε tiene que ser menor que 4 (no hay sumas mayores que 10), así que si tomo ε=3, los precios son 10-4+ε=9 y 10-6+ε=7. Ahora sí que existe una solución para m=1, {9, 7}>10, y por tanto {10-9+ε, 10-7+ε} = {4, 6} ≤ 10 es una solución del problema de bin packing.

Es una reducción muy fea, lo admito...

domingo, 26 de abril de 2015

Dos demostraciones de que existen infinitos números primos

Mientras pensaba otro problema se me han ocurrido estas dos demostraciones de que existen infinitos números primos. No es que éste sea un resultado novedoso, ¿no?, pero como son medio chulas, pues las pongo aquí.

Primera demostración. Sean r1, r2, ... , rn n números impares relativamente primos entre sí. Entonces el número

N=3·(2r1·r2·...·rn-1)

tiene al menos n+1 factores impares relativamente primos entre sí. Lo que implica que existen al menos n+1 números primos, y por inducción, existen tantos primos como se quiera.

Los n+1 factores son 3 y si = 2ni-1. Es fácil ver que 3 divide a N pero no a si; también se ve que si divide a N porque para todos a y b impares

2ab-1 = (2a-1)·(2a(b-1)-2a(b-2)+2a(b-3)-...+22a-2a+1)

Falta demostrar que los si son relativamente primos entre sí; esto es un caso particular de la siguiente proposición: dos números a y b son relativamente primos entre sí si y sólo si lo son 2a-1 y 2b-1. Como

2a+b-1 = 2a(2b-1)+2a-1

tenemos que

resto ( 2a+b-1 , 2b-1 ) = resto ( 2a-1 , 2b-1 )

y

mcd(2a+b-1, 2b-1) = mcd(2a-1, 2b-1)

y por tanto se puede aplicar el algoritmo de Euclides para calcular el máximo común divisor entre 2a-1 y 2b-1 simplemente al número de unos. Finalmente, a y b son primos relativos si y solo si el algoritmo de Euclides aplicado a a y b da 1, si y solo si el algoritmo de Euclides aplicado a 2a-1 y 2b-1 da 1, si y solo si 2a-1 y 2b-1 son primso relativos. Quizás un ejemplo lo aclare; para a=7 y b=17:

mcd(7, 17)mcd(27-1, 217-1) en binario
mcd(7 ,17) = mcd(11111112, 111111111111111112 =
mcd(7 ,3+7*2) = mcd(11111112, 1112 + 11111112 · 100000010002) =
mcd(7 ,3) = mcd(11111112, 1112) =
mcd(3 ,7) = mcd(1112, 11111112) =
mcd(3 ,1+3*2) = mcd(1112, 12 + 1112 · 100102 =
mcd(3 ,1) = mcd(1112, 12) =
1 12

Segunda demostración. Sea p un número primo, y q un divisor primo de 2p-1. Entonces 2p=1 (mod q), luego p es un múltiplo del orden de 2 en N/qN. Pero p es primo y por tanto sólo tiene dos divisores; como el orden de 2 no puede ser 1, entonces el orden de 2 tiene que ser p. Pero en N/qN todos los órdenes son menores que q, por tanto p < q. De forma que si p es primo, todos los divisores primos de 2p-1 son mayores que p, y por tanto, para cada primo p existe otro primo mayor, que se puede encontrar "simplemente" factorizando 2p-1, de aquí que existan infinitos primos.

martes, 16 de julio de 2013

Lo injusto de los sorteos por letras

Todos hemos visto alguna vez algún sorteo en el que se escoge una letra aleatoriamente y los ganadores se seleccionan por orden alfabético, empezando por la primera persona cuyo apellido tenga esa letra como inicial. Todos nos hemos dado cuenta de que es un sistema injusto; por ejemplo, es un chollo llamarse Abad, porque probablemente conseguirás aquello que se sortee tanto si sale la W como si sale la X, Y, Z o la A.

La mayoría de nosotros, incluido yo, hemos pensado que la diferencia de probabilidades sería pequeña... bueno, pensar, lo que se dice pensar, no lo hemos pensado, simplemente lo hemos dado por supuesto.

Bueno, pues no, la diferencia no es pequeña. Yo me he dado cuenta después de que mi amigo Raúl Corvillo me llamase la atención sobre dos blogs, "Un dato vale más que mil palabras" y "La ciencia para todos". También está este artículo de una mujer cabreantemente apellidada Grima.

El problema es que las iniciales de los apellidos en España están distribuidas de una forma más caprichosa de lo que se podría esperar; estos datos están sacados del primer blog:


frecuencia
% sobre el total
A
2.884.390
6,7%
B
2.263.664
5,2%
C
3.969.992
9,2%
D
1.747.696
4,0%
E
781.910
1,8%
F
1.877.528
4,3%
G
4.857.351
11,2%
H
992.297
2,3%
I
424.730
1,0%
J
722.854
1,7%
K
55.885
0,1%
L
2.250.441
5,2%
M
5.291.515
12,2%
N
699.534
1,6%
O
803.973
1,9%
P
3.042.595
7,0%
Q
185.195
0,4%
R
3.565.620
8,2%
S
3.201.882
7,4%
T
1.425.424
3,3%
U
171.705
0,4%
V
1.631.083
3,8%
W
48.578
0,1%
X
14.690
0,0%
Y
92.553
0,2%
Z
269.539
0,6%
TOTAL
43.272.624
99,8%

Por si algún día le pasase algo al blog de Eduardo, también hago una copia de su histograma, que ilustra maravillosamente lo irregular que es la distribucion de las iniciales:

Para echar las cuentas, he escrito este programita:

Empecemos imaginando que se sortea algo que va a ganar el 1% de los participantes; por ejemplo, se sortean 100 plazas de campamentos para niños y se presentan 10.000. Resulta que el 79% de los participantes no tiene ninguna posibilidad de conseguir una plaza, mientras que los 100 primeros solicitantes cuyo apellido empiece por la A tienen nada más y nada menos que el 19,23% de probabilidades de conseguirla.

Hasta aquí no hay ninguna sorpresa, era obvio que el sistema era especialmente injusto si la probabilidad de ganar era pequeña.

La auténtica sorpresa empieza a aparecer cuando descubrimos que, al aumentar el número de premios, el sistema no se hace justo rápidamente. Por ejemplo, si la probabilidad "global" de ganar es un razonable 15%, hay gente que tiene un 31% de posibilidades de ganar (las primeras A) mientras que otros tienen sólo un 4% (las últimas G).

¿Y si el porcentaje de premiados fuese el 50%? Ahora las primeras C ganan con probabilidad 62%, mientras que las últimas M sólo tienen un 38% de probabilidad de ganar. Es decir, Cabaretero tiene un 60% más de probabilidades de ganar que Mutante.

Si vamos al extremo de dar premios al 90% de los solicitantes, resulta que las primeras A, G y M tienen garantizado el premio, mientras que las últimas M sólo tienen un 69,23% de probabilidades de conseguirlo.

Supongamos que estuviésemos dispuestos a aceptar que un sorteo es "tolerablemente injusto" (he aquí un oxímoron) si al más beneficiado le da sólo un 25% más de probabilidades de ganar que al más perjudicado. ¿Cuándo es tolerable un sorteo basado en las iniciales de los apellidos? Sorpresa, sólo si al menos el 97% de los participantes van a conseguir el premio. No era esto lo que yo me esperaba.

Es previsible que este sistema funcione incluso peor en pueblos pequeños donde algunos apellidos se repiten mucho.

Francamente, me parece un sistema inaceptable, especialmente cuando hay una solución obvia y al alcance de cualquier notario del siglo XXI: se numeran las solicitudes (ya sea alfabéticamente, usando otro criterio, o sin usar ningún criterio), se escoge un número al azar, y se otorgan los premios a partir de ahí.

sábado, 22 de junio de 2013

Simulación de olas

Le estamos poniendo olas al simulador de aerogeneradores de Gamesa para ver qué pasa cuando el oleaje aporrea la base de la torre de un aerogenerador en el mar. En esta simulación, las olas llegan a tener hasta 7 metros de altura y el agua tiene 20 metros de profundidad. Las flechas indican la velocidad del agua. La mayor parte del trabajo es de David Campillo.

He intentado publicar aquí un video en formato .avi, pero no he conseguido que funcione, así pongo un enlace en Facebook.

jueves, 23 de mayo de 2013

Sintaxis bizarra

En el trabajo, al hacer un interfaz entre MATLAB y una librería nuestra en C++, hemos seguido unas instrucciones quizás un poco anticuadas, y nos hemos encontrado con unas líneas bizarras de C++. Tras una investigación sintáctica, las rarezas se pueden simplificar a esto:

double a[2][2][2][2];
double (*data)[2][2][2][2];
data = new double[110][2][2][2][2];
data = (double (*)[2][2][2][2]) new double[32];

La única línea que resulta familiar es la primera; declara que a es una variable de un tipo peculiar, está formada por 16 doubles en un array unidimensional (sin los cuatro niveles usuales de indirección) al que se accede a través de no un índice, sino 4; es decir, el decimocuarto double no es a[13] sino a[1][1][0][1] (o quizás a[1][0][1][1], no estoy seguro ahora).

La segunda línea, que ya empieza a ser rara, simplemente declara que data es un puntero a un objeto del tipo descrito antes.

La tercera línea construye un objeto del tipo anterior pero de dimensiones [110][2][2][2][2]. Obsérvese que esto es posible porque todas las dimensiones son estáticas, y por tanto el compilador puede saber qué tamaño tendrá el objeto construido. La gracia está en que, aunque este objeto no tiene las dimensiones de los objetos a los que apunta data, en realidad se puede ver como un array de 110 objetos del tipo de data, luego el puntero del new se puede convertir al tipo de puntero de data. O algo parecido.

La cuarta línea construye un array de 32 doubles de los de toda la vida, y entonces convierte el puntero al tipo de puntero adecuado para poder asignarlo a data, de forma que los 32 doubles se ven como dos objetos del tipo double[2][2][2][2]. Una de las cosas llamativas de esta sintaxis es que, si le quitas los paréntesis al (*), el compilador no te entiende.

Para quien se haya quedado intrigado; Visual Studio es capaz de compilar esta línea, pero ¿cómo la interpreta?

double** b = (double**)(double* (***)[2][2][10]) new (double* (**)[2][50][2]) ();

domingo, 24 de marzo de 2013

Cómo ordenar una baraja cortándola

Un problema planteado por un compañero de trabajo. Hacemos un mazo con una baraja y lo desordenamos; sabiendo dónde están las cartas, ¿es posible cortar el mazo varias veces de alguna forma para reordenarla?

Los cortes "normales" consisten en separar el mazo en dos submazos y poner encima el que estaba debajo. Este tipo de cortes no cambia el orden relativo de las cartas, simplemente las rota, cambiando la que está encima, y por tanto no sirve para ordenar mazos salvo en raros casos.

Ahora bien, si se permiten cortes en los que el mazo se divida en varios submazos, ¿se puede conseguir ordenarlo?

Un ejemplo. Tenemos un mazo de 8 cartas, de la A a la H. Originalmente están en el orden BCEAFGHD, siendo la primera carta, B, la que está arriba. Podemos cortar el mazo por dos sitios, digamos (BC)(EA)(FGHD), dividiéndolo en tres bloques de cartas: BC, EA, FGHD. Primero dejaremos sobre la mesa el bloque FGHD, luego el EA, y luego el BC. Entonces recogeremos primero el primer bloque, FGHD, luego el segundo y finalmente el tercero, y tendremos las cartas del mazo en este orden: (FGHD)(EA)(BC). Ahora podría volver a cortar este mazo en tres bloques, (FGH)(DE)(ABC), y al recogerlos tendría (ABC)(DE)(FGH), que ya está ordenado.

La cuestión es si siempre podemos hacer esto, y cuántos cortes de qué tipo son necesarios.

Pensando en mazos pequeños, enseguida se encuentra un ejemplo curioso. Si tenemos un mazo de tres cartas, y sólo permitimos hacer cortes en tres bloques, no podremos ordenarlo, porque lo único que haremos será intercambiar las cartas de arriba y abajo. Es fácil ver que, si tenemos un mazo con n cartas que siempre se corta en n bloques, lo único que haremos será invertir el orden de las cartas.

Sin embargo, tenemos el siguiente teorema:

Teorema: si se permiten cortes de dos y tres bloques, siempre es posible ordenar un mazo de n cartas con 3n-3 cortes.

Demostración: supongamos que tenemos un grupo de cartas ya ordenado, D, y una carta B que queremos poner al principio o al final de D. Empezamos con un mazo ABCDE, donde alguno de los grupos A, C o E podría estar vacío. Si queremos colocar B delante de D, cortamos ABCDE en (A)(BC)(DE) para obtener DEBCA, que partimos en (DE)(B)(CA) y obtenemos CABDE, con B justo delante de D como queríamos. Si quisiéramos colocar B detrás de D, lo que podríamos hacer es partir en mazo en (AB)(CD)(E), luego partimos ECDAB en (E)(CDA)(B), y finalmente partimos BCDAE en (BC)(D)(AE) para llegar a AEDBC. Podría parecer que estos cortes usan tres bloques, pero como alguno de los grupos podría estar vacio, en realidad a veces usaremos cortes con sólo dos bloques. Por tanto, en dos o tres cortes podemos colocar cualquier carta delante o detrás de un bloque ya ordenado, de mode que en n-1 movimientos podemos ordenar el mazo, así que como mucho son necesarios 3n-3 cortes.

Por ejemplo, usando cortes de dos o tres bloques, un baraja española de 40 cartas siempre se puede reordenar en 117 cortes o menos. No es ésta una cota demasiado astuta. Es fácil ver que una baraja de 3 cartas siempre se puede reordenar en dos cortes de dos o tres bloques, y una de cuatro cartas en tres. Por cierto, si permitimos cortes de dos, tres o cuatro bloques, las barajas de cuatro cartas siempre se pueden reordenar en dos cortes.

¿Cuántos cortes de dos o tres bloques son necesarios para una baraja con n cartas en el peor caso? Me temo que es una pregunta demasiado difícil, pero se puede encontrar una cota trivial. Por ejemplo, un mazo de 40 cartas se puede cortar en dos bloques de 39 formas, y en tres bloques de comb(39,2) = 39*38/2 = 741 formas; incluso si todas las combinaciones de estos 780 movimientos diesen siempre resultados diferentes, no podríamos conseguir las 40! permutaciones diferentes usando 16 cortes, ya que 78016<40! ; por tanto, el peor caso necesitará al menos 17 cortes.

En cambio, si permitimos cortes en dos, tres, ... , cuarenta bloques, tenemos que el número total de cortes que podemos usar es 239-1 (porque podemos cortar o no entre cada par de cartas, pero no podemos no cortar en ningún sitio). Entonces, incluso si todas las combinaciones de estos cortes fuesen diferentes, necesitaremos 5 cortes en el peor caso, ya que (239-1)4<40!.

El problema de determinar los cortes óptimos para un mazo parece difícil, pero estuve pensando en este problema y en una tarde de hackeo compulsivo escribí este programa, que usa cortes de hasta n bloques y encuentra una solución con n-1 cortes o menos. En promedio consigue ordenar un mazo de 40 cartas ordenadas aleatoriamente en unos 14 cortes; AVISO, es un programa feo de narices:

La idea es la siguiente.

Definamos un tramo como una serie de cartas (posiblemente sólo una) que ya están ordenadas crecientemente. Al hacer cortes, nunca cortaremos por la mitad un tramo (no tendría sentido deshacer el trabajo ya hecho), así que los bloques (grupos de cartas por donde corto) están formados por tramos. Obviamente, si un tramo acaba en la carta x, otro tramo empieza con la x+1, a menos que la carta x sea la última del mazo. El mazo está ordenado si y sólo si contiene un único tramo.

Si el mazo no está ordenado, entonces existe un tramo que empieza por x+1 y que aparece antes que un tramo que acaba en x. Porque, si no, todos los tramos ya estarían ordenados entre sí, y por tanto todo el mazo estaría ordenado.

Vale, pues entonces cortamos por delante de x+1, por detrás de x, y en algún sitio intermedio (como x y x+1 están en tramos diferentes sé que hay al menos una separación de tramos entre ellos por donde puedo cortar). Al reordenar los bloques habremos juntado dos tramos en un solo tramo. Así que cada vez que hacemos un corte podemos reducir en uno el número de tramos. Como empezamos con como mucho n tramos, en n-1 cortes o menos llegaremos a tener un único tramo, y entonces el mazo estará ordenado.

Un ejemplo: tengo el mazo 2 8 6 7 1 3 4 5; sus tramos son [2] [8] [6 7] [1] [3 4 5]; como el tramo [6 7] empieza por 6 y el [3 4 5] acaba en 5, parto el mazo en tres bloques ([2] [8]) ([6 7]) ([1] [3 4 5]) y al reordenarlo me quedará 1 3 4 5 6 7 2 8, que ahora tiene sólo 4 tramos: [1] [3 4 5 6 7] [2] [8].

Obviamente, hay varias formas de agrupar los tramos en bloques; si ese mazo lo hubiese partido en ([2] [8]) ([6 7] [1]) ([3 4 5]), al reordenar no sólo empalmaría [3 4 5] con [6 7], sino también [1] con [2], y me quedaría con un mazo con sólo tres tramos: [3 4 5 6 7] [1 2] [8]. Y además, hay otros pares de tramos que podría haber usado para partir el mazo; [2] y [1], y [8] y [6 7], también me habrían servido porque cumplen que la primera carta del primer tramo es la siguiente (x+1) a la última carta del segundo tramo (x).

El programa es una caca escrita en una tarde, y la estrategia heurística que sigue no está demasiado pensada, pero a pesar de todo, parece que siempre consigue reordenar un mazo de 40 cartas en 17 cortes o menos - el promedio está en unos 14 cortes. He hecho un par de pruebas con mazos de 1000 cartas, y los reordena en unos 200 cortes. Parece que en una iteración con n tramos este programa consigue juntar unos log(n) tramos, así que para reordenar un mazo de n cartas necesita algo más de n/log(n) cortes. Estoy convencido de que esto se debe de poder mejorar bastante.