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 {p_i}. 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 {p_i>0}_i=1ⁿ, y la cantidad mínima C con la que obtener un vale, encontrar una partición {S_i} de {p_i} con el número máximo de conjuntos tales que Σ_Sip_i > C. Dada una solución, llamaré p_ki 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 {a_i<V}_i=1ⁿ, encontrar una partición {S_i} de {a_i} con el número mínimo de conjuntos tales que Σ_Sia_i ≤ V. Dada una solución, llamaré a_ki 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 a_i=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 p_i = V-a_i, 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{a_i}, (min{Σs_i : {s_i}⊂{a_i}, Σs_i>V} - V) / n)

Es decir, ε es menor que cualquier a_i, 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 Σ(a_ki-ε)<V, entonces Σa_ki≤V; porque, de lo contrario, Σa_ki>V y estaría dentro del conjunto de la definición de ε, luego ε≤(Σa_ki-V)/n, y por tanto V≤Σa_ki-n·ε; pero, dado que como mucho hay n términos en la suma, V≤Σ(a_ki-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-a_i+ε;
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 p_i≤V, y los únicos que tienen precio V son los comodines. Porque si V-a_i+ε>V, entonces ε>a_i.

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 j_k objetos del contenedor k con volumen a_ki a productos de la compra k con precio V-a_ki+ε, y luego añadiendo n-j_k comodines de precio V hasta tener n productos; se consigue un vale por cada compra porque, como Σa_ki≤V, entonces

Σp_ki = Σ(V-a_ki+ε) + (n-j_k)·V
= j_k·V - Σa_ki + j_k·ε + n·V - j_k·V
= n·V + j_k·ε - Σa_ki
≥ n·V + ε - V = C + ε > C

donde sabemos que j_k≥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 Σp_ki>C=(n-1)·V, y en esa suma hay n-j_k comodines,

Σ(V-a_ki+ε) + (n-j_k)·V > (n-1)·V

j_k·V - Σ(a_ki-ε) + (n-j_k)·V > (n-1)·V

V > Σ(a_ki-ε)

Al definir ε se demostró que esa última desigualdad implica Σa_ki ≤ 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-a_i+ε = 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...

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 r₁, r₂, ... , r_n n números impares relativamente primos entre sí. Entonces el número

N=3·(2^{r₁·r₂·...·r_n}-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 s_i = 2^n_i-1. Es fácil ver que 3 divide a N pero no a s_i; también se ve que s_i divide a N porque para todos a y b impares

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

Falta demostrar que los s_i 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 2^a-1 y 2^b-1. Como

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

tenemos que

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

y

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

y por tanto se puede aplicar el algoritmo de Euclides para calcular el máximo común divisor entre 2^a-1 y 2^b-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 2^a-1 y 2^b-1 da 1, si y solo si 2^a-1 y 2^b-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 2^p-1. Entonces 2^p=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 2^p-1 son mayores que p, y por tanto, para cada primo p existe otro primo mayor, que se puede encontrar "simplemente" factorizando 2^p-1, de aquí que existan infinitos primos.

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:

#include "stdafx.h" #include <iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]){ int i, winner, letter, imax, imin; double freq[26] = {6.7, 5.2, 9.2, 4.0, 1.8, 4.3, 11.2, 2.3, 1.0, 1.7, 0.1, 5.2, 12.2, 1.6, 1.9, 7.0, 0.4, 8.2, 7.4, 3.3, 0.4, 3.8, 0.1, 0.0, 0.2, 0.6 }; double pfirst[26]; double plast [26]; double sum = 0.0, p, noreach=0.0, percent, max, min, nochance = 0.0; for (i=0; i<26; i++) { sum += freq[i]; pfirst[i] = 0; plast [i] = 0; } cout << "sum = " << sum << "\n"; cout << "escriba la probabilidad de ganar como porcentaje:\n"; cin >> p; cout << "\n"; for (winner=0; winner<26; winner++) { percent = p; letter = winner; if (freq[letter]>p) nochance += freq[letter]-p; while (percent > freq[letter]) { pfirst[letter] += 100.0/26.0; plast [letter] += 100.0/26.0; percent -= freq[letter]; letter = (letter+1)%26; } pfirst[letter] += 100.0/26.0; } max = 0; min = 10000; for (i=0; i<26; i++) { if (pfirst[i]>max) { max = pfirst[i]; imax = i; } if (plast[i]<min) { min = plast[i]; imin = i; } } cout << "% de poblacion que no puede ganar: " << nochance << "\n"; cout << "la probabilida de que gane la primera " << (char)(65+imax) << " es " << pfirst[imax] << "\n"; cout << "la probabilida de que gane la ultima " << (char)(65+imin) << " es " << plast [imin] << "\n"; }

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í.

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.

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]) ();

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 780¹⁶<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 2³⁹-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 (2³⁹-1)⁴<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:

//#include <string> //#include <fstream> #include "stdafx.h" #include <iostream> #include "math.h" #include <time.h> using namespace std; // Un tramo es una secuencia de cartas ya ordenadas, como 12 13 14. Quizás // contiene una única carta. Nunca se cortará en mitad de un tramo. // // Un bloque es una serie de cartas que formará uno de los cortes. Un bloque está // formado por uno o más tramos. // // Un superbloque está formado exactamente por dos bloques que al intercambiar // su orden relativo juntarán dos cartas. // // Por ejemplo: un mazo de 8 cartas como 2 8 6 7 1 3 4 5 se puede partir en // cinco tramos [2] [8] [6 7] [1] [3 4 5], cuatro bloques ([2]) ([8]) ([6 7] [1]) ([3 4 5]) // y un superbloque ([2]) ([8]) <([6 7] [1]) ([3 4 5])>. Al romper el mazo en los // cuatro bloques y cambiar su orden quedará ([3 4 5]) ([6 7] [1]) ([8]) ([2]), y se juntan // las cartas 5 y 6 que antes eran las cartas en los extremos del superbloque. // // También se juntan las cartas 1 y 2; a esto le he llamado optimización, porque en // realidad los tramos [2] y [8] podrían haber formado un bloque ([2] [8]) en vez de // dos bloques ([2]) ([8]), pero entonces no se habrían juntado. // // El algoritmo eurístico es el siguiente: // 1. formar los tramos (existe una forma única de hacerlo) // 2. formar los superbloques decrecientes. Cosas como (x+1 y) (z x) que al // cortar resultarán en (z x x+1 y). Uso una strategia codiciosa, hago una lista // con todos los posibles superbloques (definidos por las parejas de tramos de // sus extremos), elimino los superbloques que contienen completamente a otros // superbloques, y cojo todos los superbloques que puedo empezando por la // izquierda. // 3. entre los tramos que me quedan sin asignar a superbloques, busco superbloques // crecientes; es decir, cosas como (x y) (z x+1) que al reordenar se convertirán // en (z x+1 x y) y que aunque ahora no mejorarán nada, en la siguiente iteración // se podrán usar para hacer un superbloque decreciente. // 4. buscar optimizaciones - por dónde partir los superbloques para conseguir alguna // mejora. // 5. si quedan superbloques sin dividir en bloques, los rompo por la izquierda. int debug = 0; // escribe todo const int NCARTAS = 40; int carta[NCARTAS]; int usada[NCARTAS]; int buffer[NCARTAS]; // tramos int nTramos; int tp[NCARTAS]; // tramo principio int tf[NCARTAS]; // tramo final int tb[NCARTAS]; // bloque al que pertenece este tramo int sbat[NCARTAS]; // superbloque al que ha sido asignado este tramo // parejas para hacer superbloques int nParejas; int tpp[NCARTAS]; // tramo principio pareja int tfp[NCARTAS]; // tramo final pareja // super bloques int nSB; int sbp[NCARTAS]; // principio int sbf[NCARTAS]; // final int sbd[NCARTAS]; // direccion int sbl[NCARTAS]; // libre para optimizar; -1 no, positivo partir ahí // bloques int nBloques; // random values #include <time.h> struct RANDOM{ unsigned long super_z0; unsigned long super_w0; }; void InitRandoms(struct RANDOM *random) { srand( (unsigned)time( NULL ) ); random->super_z0=rand();//2345; random->super_w0=rand();//6542; } unsigned long SuperRand(struct RANDOM *random, unsigned long max) { unsigned long super_znew0 = ((random->super_z0=36969*(random->super_z0&65535)+(random->super_z0>>16))<<16); unsigned long super_wnew0 = ((random->super_w0=18000*(random->super_w0&65535)+(random->super_w0>>16))&65535); unsigned long SUPER_RAND0 = (super_znew0+super_wnew0); return ((SUPER_RAND0)%max); } RANDOM randomSeed; int myRand(int max) { return SuperRand(&randomSeed, 1000000) %max; } double myDoubleRand() { return (double)SuperRand(&randomSeed, 1048576)/1048576.0; } void getRandomPermutation() { int i, j, iCarta, contador; for (i=0; i<NCARTAS; i++) usada[i] = 0; for (j=0; j<NCARTAS; j++) { iCarta = (int) (myDoubleRand()*((double)(NCARTAS-j))); contador = 0; for (i=0; i<NCARTAS; i++) { if (usada[i]==0) { contador++; if (contador>iCarta) { carta[i] = j+1; usada[i] = 1; break; } } } } } void parteCartasEnTramos() { int i; // añadir al primer tramo la primera carta tp[0] = 0; tf[0] = 0; nTramos = 1; // decidir si cada carta se añade al último tramo o si empieza tramo nuevo for (i=1; i<NCARTAS; i++) { if (carta[i]==carta[tf[nTramos-1]]+1) { tf[nTramos-1]++; }else{ tp[nTramos] = i; tf[nTramos] = i; nTramos++; } } } void printTramos() { if (debug==1) { int i; for (i=0; i<nTramos; i++) { if (tp[i]==tf[i]) { cout << carta[tp[i]] << " "; }else{ cout << carta[tp[i]] << "-" << carta[tf[i]] << " "; } } cout << "\n"; } } const int DECRECIENTE = 0; const int CRECIENTE = 1; void buscaSuperBloques(int direccion, int primerTramo, int ultimoTramo) { int i, p1, p2, minimo, primeraPareja; bool cambios; // lista de todas las parejas nParejas = 0; for (p1=primerTramo; p1<=ultimoTramo-1; p1++) { for (p2=p1+1; p2<=ultimoTramo; p2++) { if (direccion==DECRECIENTE && carta[tp[p1]]==carta[tf[p2]]+1) { if (debug==1) cout << "pareja " << p1 << "-" << p2 << "\n"; tpp[nParejas] = p1; tfp[nParejas] = p2; nParejas++; } if (direccion==CRECIENTE && carta[tp[p1]]+1==carta[tf[p2]]) { if (debug==1) cout << "pareja " << p1 << "-" << p2 << "\n"; tpp[nParejas] = p1; tfp[nParejas] = p2; nParejas++; } } } // Eliminar aquellas parejas que contengan completamente a otras parejas cambios = true; while (cambios) { cambios = false; for (p1=0; p1<nParejas; p1++) { for (p2=0; p2<nParejas; p2++) { if (p1!=p2) { // si p1 incluye a p2, eliminar p1 if (tp[tpp[p1]] <= tp[tpp[p2]] && tf[tfp[p1]] >= tf[tfp[p2]]) { if (debug==1) cout << "eliminando pareja " << tpp[p1] << "-" << tfp[p1] << " porque incluye pareja " << tpp[p2] << "-" << tfp[p2] << "\n"; tpp[p1] = tpp[nParejas-1]; tfp[p1] = tfp[nParejas-1]; nParejas--; cambios = true; break; } } } if (cambios) break; } } if (debug==1) { cout << "Lista limpia de parejas:\n"; for (i=0; i<nParejas; i++) { cout << i << " " << tpp[i] << "-" << tfp[i] << "\n"; } } // mientras haya parejas, convertir la primera en superbloque y borrar las que solapen while (nParejas>0) { minimo = 10000; for (i=0; i<nParejas; i++) { if (tpp[i]<minimo) { minimo = tpp[i]; primeraPareja = i; } } if (debug==1) cout << "conviertiendo pareja " << tpp[primeraPareja] << "-" << tfp[primeraPareja] << " en superbloque\n"; sbp[nSB] = tpp[primeraPareja]; sbf[nSB] = tfp[primeraPareja]; sbd[nSB] = direccion; sbl[nSB] = -1; // marcar libre para optimizar for (i=tpp[primeraPareja]; i<=tfp[primeraPareja]; i++) sbat[i] = nSB; nSB++; i = 0; while (i<nParejas) { if (tpp[i]<=sbf[nSB-1] && tfp[i]>=sbp[nSB-1]) { if (debug==1) cout << "borrando pareja " << tpp[i] << "-" << tfp[i] << " porque solapa\n"; tpp[i] = tpp[nParejas-1]; tfp[i] = tfp[nParejas-1]; nParejas--; }else{ i++; } } } } void marcaBloques() { int i, j; // dividir superbloques en bloques; for (i=0; i<nSB; i++) { if (sbl[i]==-1) sbl[i]=sbp[i]; // si todavía están libres para optimizar, partir en el primer sitio posible for (j=sbp[i]; j<=sbl[i]; j++) { tb[j] = nBloques; } nBloques++; for (j=sbl[i]+1; j<=sbf[i]; j++) { tb[j] = nBloques; } nBloques++; } // agrupar los tramos que queden en bloques for (i=0; i<nTramos; i++) { if (tb[i]==-1) { tb[i] = nBloques; j = i+1; while (j<nTramos && tb[j]==-1) { tb[j] = nBloques; j++; } nBloques++; } } if (debug==1) { cout << "partición de tramos en bloques:\n"; for (i=0; i<nTramos; i++) cout << tb[i] << " "; cout << "\n"; } } void printBloques() { int bloque, i; bloque = -1; for (i=0; i<nTramos; i++) { if (tb[i]!=bloque) { // nuevo bloque. Cerrar el anterior si bloque != -1. if (bloque!=-1) cout << ") "; cout << "("; if (tp[i]==tf[i]) { cout << carta[tp[i]]; }else{ cout << carta[tp[i]] << "-" << carta[tf[i]]; } bloque = tb[i]; }else{ // mismo bloque. cout << " "; if (tp[i]==tf[i]) { cout << carta[tp[i]]; }else{ cout << carta[tp[i]] << "-" << carta[tf[i]]; } } } cout << ")\n"; } // Como printBloques, pero leo al revés, escribo cartas en vez de tramos en buffer, y luego copio a cartas. void mueveCartas() { int i, j, k, bloque, finalBloque, write; bloque = -1; write = 0; for (i=nTramos-1; i>=0; i--) { if (tb[i]!=bloque) { if (bloque != -1) { // escribir en buffer las cartas de los tramos i+1 a finalBloque for (j=i+1; j<=finalBloque; j++) { for (k=tp[j]; k<=tf[j]; k++) { buffer[write++] = carta[k]; } } } bloque = tb[i]; finalBloque = i; } } // escribir en buffer las cartas de los tramos 0 a finalBloque for (j=0; j<=finalBloque; j++) { for (k=tp[j]; k<=tf[j]; k++) { buffer[write++] = carta[k]; } } for (i=0; i<NCARTAS; i++) { carta[i] = buffer[i]; } } void printEstructura() { int iTramo, iCarta; if (debug==1) { cout << "pos carta tramo bloque superbloque\n"; for (iCarta=0; iCarta<NCARTAS; iCarta++) { // buscar tramo al que pertenece esta carta for (iTramo=0; iTramo<nTramos; iTramo++) { if (tp[iTramo]<=iCarta && tf[iTramo]>=iCarta) { printf("%2d %2d %2d %2d %2d\n", iCarta, carta[iCarta], iTramo, tb[iTramo], sbat[iTramo]); } } } } } void buscaSuperBloquesCrecientes() { int i, primero, ultimo; // buscar tramos sin asignar a superbloques for (i=0; i<nTramos; i++) { if (sbat[i]==-1) { primero = i; ultimo = i; while (i+1 < nTramos && sbat[i+1]==-1) { i++; ultimo = i; } buscaSuperBloques(CRECIENTE, primero, ultimo); } } } // poner en primero y ultimo los tramos delante de tramo que no están asignados // a ningún bloque ni a ningún superbloque void anterior(int tramo, int & primero, int & ultimo) { ultimo = tramo - 1; primero = tramo; while (primero-1 >= 0 && tb[primero-1]==-1 && sbat[primero-1]==-1) { primero--; } } // poner en primero y ultimo los tramos detrás de tramo que no están asignados // a ningún bloque ni a ningún superbloque void posterior(int tramo, int & primero, int & ultimo) { primero = tramo + 1; ultimo = tramo; while (ultimo < nTramos-1 && tb[ultimo+1]==-1 && sbat[ultimo+1]==-1) { ultimo++; } } // marcar los tramos de primero a ultimo como pertenecientes a un nuevo bloque void nuevoBloque(int primero, int ultimo) { int i; for (i=primero; i<=ultimo; i++) { tb[i] = nBloques; } if (ultimo>=primero) nBloques++; } void optimizaSuperbloques() { int i, primero, ultimo, j, k; // buscar superbloques sin optimizar y mirar si los puedo partir de forma que // formen una pareja creciente con los tramos anteriores que no están en un superbloque // y que no están asignados a ningún tramo. loop1: for (i=0; i<nSB; i++) { if (sbl[i]==-1 && sbp[i]+1<sbf[i]) { anterior(sbp[i], primero, ultimo); for (j=primero; j<=ultimo; j++) { for (k=sbp[i]+1; k<sbf[i]; k++) { if (carta[tf[k]]==carta[tp[j]]-1) { cout << "opt: unire " << carta[tf[k]] << " con " << carta[tp[j]] << "\n"; sbl[i] = k; // partir este superbloque desde sbp[i] hasta tramo k; nuevoBloque(primero, j-1); nuevoBloque(j, ultimo); goto loop1; } } } } } // Idem pareja creciente con tramos posteriores loop2: for (i=0; i<nSB; i++) { if (sbl[i]==-1 && sbp[i]+1<sbf[i]) { posterior(sbf[i], primero, ultimo); for (j=primero; j<=ultimo; j++) { for (k=sbp[i]+1; k<sbf[i]; k++) { if (carta[tp[k]]==carta[tf[j]]+1) { cout << "opt: unire " << carta[tp[k]] << " con " << carta[tf[j]] << "\n"; sbl[i] = k-1; // partir este superbloque desde sbp[i] hasta tramo k-1; nuevoBloque(primero, j); nuevoBloque(j+1, ultimo); goto loop2; } } } } } // Idem pareja decreciente con tramos anteriores loop3: for (i=0; i<nSB; i++) { if (sbl[i]==-1 && sbp[i]+1<sbf[i]) { anterior(sbp[i], primero, ultimo); for (j=primero; j<=ultimo; j++) { for (k=sbp[i]+1; k<sbf[i]; k++) { if (carta[tf[k]]==carta[tp[j]]+1) { cout << "opt: unire " << carta[tf[k]] << " con " << carta[tp[j]] << "\n"; sbl[i] = k; // partir este superbloque desde sbp[i] hasta tramo k; nuevoBloque(primero, j-1); nuevoBloque(j, ultimo); goto loop3; } } } } } // Idem pareja decreciente con tramos posteriores loop4: for (i=0; i<nSB; i++) { if (sbl[i]==-1 && sbp[i]+1<sbf[i]) { posterior(sbf[i], primero, ultimo); for (j=primero; j<=ultimo; j++) { for (k=sbp[i]+1; k<sbf[i]; k++) { if (carta[tp[k]]==carta[tf[j]]-1) { cout << "opt: unire " << carta[tp[k]] << " con " << carta[tf[j]] << "\n"; sbl[i] = k-1; // partir este superbloque desde sbp[i] hasta tramo k-1; nuevoBloque(primero, j); nuevoBloque(j+1, ultimo); goto loop4; } } } } } } int _tmain(int argc, _TCHAR* argv[]){ clock_t time = clock(); int i, nCortes; InitRandoms(&randomSeed); getRandomPermutation(); nCortes = 0; while (true) { for (i=0; i<NCARTAS; i++) cout << carta[i] << " "; cout << "\n"; parteCartasEnTramos(); if (nTramos==1) { cout << "FIN; usados " << nCortes << " cortes.\n"; break; } printTramos(); // partir en superbloques. nSB = 0; // ningún superbloque for (i=0; i<NCARTAS; i++) sbat[i]=-1; // ningún tramo asignado a ningún superbloque buscaSuperBloques(DECRECIENTE, 0, nTramos-1); buscaSuperBloquesCrecientes(); for (i=0; i<nTramos; i++) tb[i] = -1; nBloques = 0; cout << "\n"; optimizaSuperbloques(); // parte superbloques no optimizados en cualquier sitio for (i=0; i<nSB; i++) { if (sbl[i]==-1) { sbl[i] = sbp[i]; } } marcaBloques(); nCortes++; cout << "corte numero " << nCortes << ":\n"; printBloques(); mueveCartas(); } time = clock() - time; cout << "time spent = " << time << " ms\n"; cout << "press any key to end\n"; char cinget; cin.get(cinget); return 0; }

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.

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).

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.

Dies de porno i kleenex / Cesc Llaverias

En esta divertida novela se cuentan las aventuras de una pandilla de amigos en esa edad aterradora en la que se les ha acabado el estudiar y tienen que hacerse un hueco en la vida. De repente se marcan objetivos como buscar trabajo, encontrar un piso, y hacer otras cosas que el sistema educativo ignora; obviamente, nada les saldrá bien a la primera, pero no es para preocuparse, son jóvenes y tienen tiempo para volver a fracasar una y otra vez.

Hay dos temas centrales en las diversas tramas: la búsqueda de sexo repetible y los trabajos basura.

Sexo, lo que se dice sexo, van encontrando, pero es esporádico, pícaro, insatisfactorio e infiel. El objetivo real es asegurarse un suministro de polvos para los fines de semana, a ser posible que se ajusten razonablemente a sus preferencias sexuales y emotivas, y para ello tienen que negociar diversas situaciones. Un afortunado se reúne con el amor de su vida y otro llega a celebrar una boda sin casarse, pero, en general, hay más masturbación que otra cosa.

La búsqueda de trabajo es el otro objetivo común, pero este problema no lo pueden arreglar engañándose entre sí, así que lo llevan incluso peor que lo del sexo. La gran desilusión se la lleva un chico que hace un curso de croupier para trabajar en el Casino de Barcelona. Otro desgraciado lo hace bien en su trabajo y de repente se ve agobiado por sus responsabilidades crecientes sin compensación salarial. Me consta que las historias de otros curros se han eliminado, quizás para no hacer deprimente el libro.

Además de tratar otros temas, como problemas con compañeros de piso o vacaciones cutres, la novela ofrece una descripción de la Barcelona golfa y optimista de principios de siglo, porque los miembros de la pandilla exploran todos los garitos de la ciudad en sus correrías nocturnas en busca de sexo y alcohol.

Editorial Autor-Editor; es posible que ya se pueda comprar aquí. Pronto estará traducido al español (salió la semana pasada).

Cenital / Emilio Bueso

Este NO es un libro divertido.

Hace unos años se hablaba de novelas post-apocalípticas; ahora parece que el palabro de moda es "colapso". Por ejemplo, llevan decenios avisándonos de que la Seguridad Social acabará colapsando (quebrando); esto no será el fin del mundo, simplemente será un desastre sin precedentes. ¿Pero qué hacemos nosotros al respecto? Discutir sobre si la culpa será del PP o del PSOE, como si así pudiésemos domeñar fuerzas demográficas irresistibles.

Desde la crisis de los años 70 se nos viene diciendo que la civilización lo tendrá crudo cuando se acabe el crudo. ¿Qué hemos hecho sobre el fin del petróleo?

En Cenital aparece un líder profético, Destral, que hace algo a pequeña escala. Observa que nuestra economía no es sostenible, en particular depende demasiado del petróleo, y, aunque no puede saber muy bien qué ocurrirá ni cuándo, llega a la conclusión de que las cosas no podrán seguir así, y que lo más probable es que evolucionen hacia el lado malo. Así que organiza una ecoaldea donde poder sobrevivir sin necesitar del mundo exterior. Y efectivamente, cuando la humanidad acaba de quemar sus recursos y la cosa se pone fea de verdad (el canibalismo es sólo un paso en el descenso a los infiernos), su pequeña población fuertemente armada parece tener todos los boletos para salir adelante.

La trama de Cenital no importa demasiado; es la historia de un intento de saqueo reminiscente de Mad Max, que en realidad es una excusa para explicarnos cómo funciona la ecoaldea y presentarnos a una serie de personajes. En concreto, la principal ocupación y preocupación de la ecoaldea es la próxima burbuja, una explosión de población causada por la falta de condones.

En Cenital el mundo colapsa en 2014, demasiado cerca de nosotros. Esto le resta credibilidad, pero por otra parte hace que sus personajes sean mileuristas que se hipotecaron, promotores inmobiliarios que ganaron y perdieron fortunas, activistas del 15-M, especuladores, y otra fauna contemporánea. En otras novelas parecidas, los personajes son unos tipos raros de un siglo raro que viven en una sociedad rara con problemas raros y visten de forma rara, y que tienen la rara idea de que sus antepasados cometieron un gran error pero que ellos no tienen la culpa y han aprendido y son mejores. En Cenital, no; los personajes de Cenital somos nosotros mismos desengañados, después de darnos cuenta de que fuimos unos simples y que no vendrá un Hada Renovable a resolvernos el problema energético. En Cenital la gente piensa cosas como "fuimos unos memos y mira la que montamos", "lo vi venir y me construí un refugio", o "fue correcto saquear el planeta antes, y ahora lo seguiré saqueando mientras quede un grano de trigo que robar."

El libro tiene un cierto aire proselitista, se nota que Destral quiere convencer a sus seguidores y al lector, y está repleto de citas lapidarias sobre la insostenibilidad de nuestra economía. Explica cosas como el pico del petróleo, las limitaciones de las energías renovables, y nos convence de que "comemos petróleo": ¿sabía usted que para pescar un kilo de peces nuestra sociedad gasta más de un litro de combustible?

En resumen, es una buena novela de ciencia ficción, bien documentada y que da qué pensar. Además es muy entretenida y cuesta dejar de leerla; como en sus anteriores libros, Noche Cerrada y Diástole, Emilio Bueso consigue dosificar la información que va dando de forma que siempre tienes que leer el capítulo siguiente.

Conjunción

La Luna, Júpiter (arriba) y Venus (abajo) 27 y 28 de febrero de 2012. Es curioso cómo envejecen las cámaras digitales; aunque no se note mucho en las fotos con luz, he tenido que borrar a mano cuatro "estrellas" de píxeles estropeados.

Otro concurso online de problemas matemáticos

He recibido una invitación para participar en otro concurso de problemas para freakies matemáticos: Cerebra. Se celebrará los sábados 21 y 28 poco después de comer hora española.

Voy a ver si me apunto, porque los últimos fines de semana he estado sufriendo demasiado mientras espero a que salga el problema del proyecto Euler.

Resulta que minutos antes de que se publique el problema y empiece la carrera para resolverlo, todos los matemáticos programadores ociosos del planeta se pasan por ahí y empiezan a pinchar frenéticamente en el botón de refrescar para ser los primeros en tener el enunciado, y la página recibe tal bombardeo que entre todos le hacemos involuntariamente un ataque de denegación de servicio. Sí, los freakies somos un horda. Como últimamente pasa una hora antes de poder ver el problema, la cosa está perdiendo su gracia. En fin, paciencia.

Problema real

Os voy a proponer un problema real de matemáticas financieras.

Érase que se era una empresa con graves problemas. Varios inversores compraron participaciones con una diversidad de condiciones, de forma que no está muy claro cuánto vale esta empresa, pero hay que buscar más socios e inyectar más dinero con la esperanza de que aguante hasta que acabe la crisis y empiece a ganar dinero.

Total, que los ejecutivos de esta empresa van a hablar con unos qataríes y les proponen que compren la mitad de la empresa por una cantidad de dinero X. Los qataríes dicen que están de acuerdo, pero exigen a los actuales propietarios de la empresa que se rasquen los bolsillos como sea y pongan otros X euros. Debe de ser un buen trato, porque los propietarios, que posiblemente sí que saben lo que vale la empresa, se ponen muy contentos y dicen que las negociaciones están muy avanzadas.

¿Cuánto vale la empresa ahora? (es decir, antes de que los qataríes compren la mitad)

El problema es curioso porque parece que faltan datos... pero no.

http://www.expansion.com/accesible/2011/12/16/catalunya/1324068132.html

Estadísticas

Otra encuesta que hacen en Telemadrid y les sale el 78%. Para mí que siempre preguntan a los mismos 9, y hay 2 de la oposición.