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.

miércoles, 30 de enero de 2013

Por qué el descubridor de la distribución t de Student no se llamaba Student

Resulta que, a principios del siglo XX, Claude Guinness se dedicaba a contratar a los mejores licenciados de Oxford y Cambridge para que trabajasen mejorando los procesos industriales de su cervecería.

Uno de sus fichajes fue William Sealy Gosset, un joven químico y matemático que trabajó en el control de calidad de stout, un tipo de cerveza negra. Gosset atacó el problema de minimizar el número de pruebas necesario para decidir si el stout era bueno. Los aficionados a la cerveza pensarán que este problema es estúpido, así que para justificarlo diré que cuanto menos stout se gaste en la fábrica haciendo pruebas, más barato se podrá vender el resto.

Por no entrar en detalles, cuando se hace un número grande de cierto tipo de pruebas, el resultado sigue aproximadamente una distribución normal. Pero Gosset quería hacer precisamente un número pequeño de pruebas, y la aproximación habitual no le servía. Así que echó sus cuentas, descubrió su distribución, y la encontró bastante útil, así que quiso publicarla.

Pero entonces se topó con la política de publicaciones del señor Claude Guinness, al que no le hacía nada de gracia que sus trabajadores revelasen a su competencia lo que él consideraba información confidencial sobre sus métodos de elaboración. Guinnes ya había tenido unos cuantos problemas con estos temas, y no estaba muy dispuesto a regalar al mundo un método que le ahorraba bastante dinero. Francamente, esto era un poco ponerle puertas al campo; no puedes reunir a los mejores científicos del mundo para que descubran la mejor forma de hacer cerveza y esperar que no publiquen sus resultados. Por otro lado, lo que Gosset quería publicar no eran las temperaturas óptimas para fermentar variedades de lúpulo, sino una distribución estadística...

Así que Gosset y Guinness llegaron a un acuerdo: Gosset podría publicar sus descubrimientos, pero usando un pesudónimo científico, para no dar pistas a los otros fabricantes de cerveza sobre cómo abaratar sus procesos de calidad. Este tipo de apaños era relativamente frecuente allá por 1908.

Esta es la razón por la que Gosset publicó sus artículos bajo el nombre de Student, y así hoy en día todos conocemos la distribución t de Student pero casi nadie sabe quién fue Gosset.

Incidentalmente, es posible que Guinness se preocupase demasiado. Es verdad que en aquellos tiempos ya estaba de moda aplicar metodologías científicas a todo tipo de industrias, pero la industria cervecera en concreto resultó ser muy conservadora, y la mayoría de sus competidores continuó con sus métodos tradicionales hasta que el éxito de Guinness les apabulló y les obligó a modernizarse.

Gosset siguió publicando y alcanzó renombre, a pesar de su nombre falso. Tuvo unas cuantas oportunidades de trabajar en la universidad, pero las rechazó porque tenía una familia grande y en Guinness le pagaban muy bien. Debió de ser un tío muy majo, porque consiguió la proeza de hacerse amigo a la vez de Pearson y de Fisher. Estos dos matemáticos se profesaban un intensísimo desprecio por sus desacuerdos sobre la filosofía de las pruebas de significancia, y sus agrias discusiones abarcaron dos generaciones; como esta historia es larga, los interesados podrán alucinar leyendo, por ejemplo, http://www.econ.uba.ar/www/institutos/epistemologia/marco_archivos/ponencias/actas%20xiii/trabajos%20episte/urbisaia-brufman_trabajo.pdf o http://stats.org.uk/statistical-inference/Lenhard2006.pdf (la verdad es que no sé si hay mejores artículos donde cuenten bien esta historia, no he buscado mucho).

martes, 21 de agosto de 2012

Fotocópiame las pelotas / Mario Fernández

Recientemente tres amigos míos han publicado libros, así que voy a hacerles un poquito de publicidad gratuita.

Una cosa que recuerdo de "Fotocópiame las pelotas" es cómo me miraba la gente en el metro mientras yo me partía de risa y pensaba "esto no tiene ninguna gracia".

A pesar de lo que pueda parecer, Mario no es un psicópata; al revés, cuando nació era un tío estupendo y una bellísima persona. Es simplemente que tuvo un trabajo malo en el que aprendió a odiar a sus clientes y que le convirtió temporalmente en un misántropo. Luego tuvo otro trabajo peor, luego otro que no os creeríais, y luego otro tan impeorable que no se lo creyó ni él. Pero esto fue sólo el principio. Cuando estuvo tan alienado que temió perder el sentido de la realidad, empezó a escribir un diario en Internet para desahogarse. Luego se inventaron los blogs, y resultó que Mario ya tenía uno hecho. Años más tarde ha seleccionado algunas de sus entradas para publicarlas, y de esta forma ha salido algo que parece un diario de cuando estuvo trabajando vendiendo cámaras de fotos en una conocida tienda.

La vida de Mario es como una caja de bombones: nunca se sabe qué mierda le va a explotar en las narices, pero podemos apostar a que le ocurrirá algo humillante e innecesario. En realidad no hay trama, el libro es una sucesión de episodios reales contados con gracia, pero tan estúpidos que por separado resultan desesperantes y juntos te convencen de que el mundo necesita más arsenales nucleares. En una ocasión tras otra, Mario es agredido por la falta de sentido común de sus vecinos, clientes, jefes, o compañeros de trabajo; a veces consigue devolver la pelota, pero no se hace ilusiones, sabe que siempre tuvo perdida su guerra contra la humanidad y su idiotez. El diario acaba cuando liga con una compañera de trabajo y deciden escaparse del trabajo y hacerse sus propios jefes. ¿Final feliz? No sé, es triste observar que toda esta mierda y estos sueldos seiscientoseuristas ocurren entre 2002 y 2004, que pasarán a la historia como los años de la abundancia antes del catacroc.

Imprescindible para todos aquellos a los que les guste el humor ácido y grosero, las historias de trabajos basura, los personajes perdedores, o que necesiten revolcarse en el cieno del absurdo existencial.

Trailer publicitario. Las 30 primeras páginas. Otras reseñas: Sergi Puertas, Salva Dávila, Els llibres del Senyor Dolent, 20 minutos. Para comprar: Editorial Mi Cabeza.