tag:blogger.com,1999:blog-71802533651541707472024-03-06T00:53:57.168-08:00Jugando a programarUn blog dedicado a la programación y las matemáticasSantiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.comBlogger46125tag:blogger.com,1999:blog-7180253365154170747.post-16719078600356885012020-04-02T14:19:00.001-07:002020-04-02T14:22:41.809-07:00Estimando con precisión el número de infectados de coronavirus
<P>En una charla en Facebook salió el problema de a cuánta gente habría que hacer tests para conocer con precisión el número de infectados en España; concretamente, con un error del 1%.</P>
<P>Claro, un 1% es demasiada precisión, porque en el momento de escribir esto, el número oficial de infectados crece cada día un 10%. Olvidémonos de este detalle.</P>
<P>El resultado es chocante, porque hace falta una cantidad enorme de tests. Antes de entrar en faena, veamos dos casos extremos. Primero, tenemos un pueblo con 50 habitantes y queremos conocer el número de infectados con un error del 1%; bueno, es sencillo, hay que hacerle el tests a todos y cada uno de los vecinos. Segundo, tenemos una enfermedad rara que posiblemente padece una persona de cada millón; en realidad no lo sabemos, porque sólo se ha tratado a pacientes que iban a la consulta porque su caso era grave. Hacerle el test a un millón de personas no sería suficiente; posiblemente pillarías a un enfermo, pero a lo mejor no pillarías a ninguno; obviamente, esto no sería suficiente para estimar el número de enfermos con un error del 1%.</P>
<P>Vamos al grano. Imaginemos que en España hay 50M personas, y que el 0,4% de la población está infectada (el dato oficial era más o menos la mitad en el momento de formularse la pregunta). Hacemos un test a N personas. El resultado tendrá una media 0,004*N y una desviación típica raiz(N*0,004*0,996). Supongamos que usamos una confianza del 95%; esto quiere decir que aceptamos que el resultado puede ir desde -2 desviaciones típicas hasta 2, es decir, desde 0,004*N-2*raiz(N*0,004*0,996) hasta 0,004*N+2*raiz(N*0,004*0,996). Como queremos que este resultado tenga un error del 1%, 2*raiz(N*0,004*0,996) = 0,01*0,004*N. Y uf, eso quiere decir que N = 10.000.000. </P>
<P>¿Uh?</P>
<P>Sí, en serio. Si hago 10 millones de tests, encontraré un número de infectados que tendrá de media 40.000 y de desviación típica 199; de forma que si confío en que caerá entre 39.600 y 40.400 ya me aseguro el error de 1%.</P>
<P>Un ejemplo un poco menos chocante. Si sólo testeo a 10.000 personas, espero encontrarme 40 infectados, pero la desviación típica será 6,3, así que el número que me saldrá estará entre 40-2*6,3=27 y 53. Claro, 53 es casi el doble de 27; con 10.000 tests estoy muy, muy lejos del error de 1% en el número de infectados.</P>
<P>Esto es llamativo entre otras cosas porque estamos acostumbrados a que los sondeos electorales con 3.000 personas nos den un error del orden del 1%. Pero es que ahí los porcentajes buscados no son pequeños, los partidos minoritarios ni aparecen. Imaginemos que la mitad de la población estuviese infectada; si tomo 3.000 muestras me saldrá un resultado con media 1.500 y desviación típica raiz(3000*0,5*0,5)=27, así que con confianza 95% el resultado estaría entre 1446 y 1554, y tendría un error menor que 3.6%. Nada que ver.</P>
<P>Una pregunta interesante: imaginemos que hacemos 10.000 tests, pero en vez de escoger a 10.000 españoles al azar, usamos algún tipo de criterio geográfico. ¿Podríamos tener una estimación más precisa? La respuesta es que sí, pero quizás no mucho. Me invento un ejemplo.</P>
<P>Seguimos suponiendo que hay 50M españoles y el % = 0,4% están enfermos. Pero ahora España está dividida en dos "sitios"; el Norte tiene 30M habitantes y %n = 0,6% infectados, y el Sur tiene 20M habitantes y %s = 0,1% infectados (esta diferencia de porcentajes es exagerada). Nosotros no conocemos %, %n y %s, pero obviamente 50 * % = 30 * %n + 20 * %s. En vez de tomar una muestra de m = 10.000 españoles, tomaremos dos muestras de mn norteños y ms sureños, donde nosotros podemos escoger mn y ms con la retricción de que mn+ms = m = 10.000.</P>
<P>Al analizar las muestras nos encontraremos con in y is infectados.</P>
<P>La media de in es %n * mn y su varianza es mn * %n * (1-%n)</P>
<P>La media de is es %s * ms y su varianza es ms * %s * (1-%s)</P>
<P>Así que estimaremos el número total de infectados en el norte como (30M/mn) * in; esto tiene media 30M * %n y varianza mn * %n * (1-%n) * (30M/mn)^2.</P>
<P>Cuando sumamos las estimaciones del norte y del sur, nos sale la media correcta (aquí no hay sorpresa) y varianza </P>
<P>%n * (1-%n) * 30M^2 / mn + %s * (1-%s) * 20M^2 / ms</P>
<P>comparado con la encuesta inicial de una sola muestra para toda España, que tiene una varianza de</P>
<P>% * (1-%) * 50M^2 / m = 996M</P>
<P>Vale, ¿cuál es la mejor forma de escoger mn y ms? Pues resulta que la varianza se minimiza para mn = 7856 y ms = 2144, si lo hacemos así la varianza sale 870M. Claro, esto es un poco hacer trampa, porque para precisar tanto hay que conocer %n y %s. Lo que pasa es que tampoco es algo tan descabellado; si sospechamos que hay más enfermos en el norte que en el sur, parece lógico afinar el muestreo en el norte; si no tuviésemos ninguna preferencia, repartiríamos la muestra 6000/4000 para norte/sur por tener poblaciones 30M/20M; si en vez de 7856/2144 hubiésemos usado 8500/1500, la varianza nos saldría 898M, que tampoco es tan diferente. Si se nos fuese la olla y usásemos 9750/250, la varianza se dispararía y subiría hasta 2149M; pero vaya, cualquier matemático que pasase por ahí nos avisaria de que eso es un disparate.</P>
<P>A lo que vamos: si usamos una sola muestra, nuestra estimación tendría una media 50M * 0,004 = 200.000 infectados con una desviación típica = raiz(varianza) = 31.559 , mientras que si usamos dos muestras, lo menos que podemos conseguir es una desviación típica de raiz(870M) = 29.496. La mejora es como mucho un 7%, y corremos el riesgo de meter la pata y hacerlo mal.</P>
<P>Esto parece muy poco, posiblemente porque, de nuevo, comparamos con las encuestas electorales, que sabemos que consiguen mejoras mucho mayores.</P>
<P>Pero claro, para exprimir la información de una encuesta electoral, se usa un montón de información. Se tienen los resultados de elecciones anteriores, y si decides que vas a usar tal sitio paa hacer la encuesta, te puedes informar de si ahí ha cambiado el censo, si se ha construido una fábrica que atraerá obreros, o urbanizaciones con campos de golf, puedes obtener un montón de datos como estadísticas sobre la declaración de la renta, etc.</P>
<P>Con el coronavirus no tenemos esa información, así que no sabemos cómo sacarle tanto jugo a una muestra. </P>
<P>Si lo que nos interesase no fuese estimar el número de infectados sino el número de muertes, podríamos poner en nuestra encuesta más personas mayores y hombres, que mueren más de covid19 que las mujeres. Esto lo podríamos hacer de dos formas: o bien encuestamos más a hombre y a mayores en vez de escoger gente al azar (aplicable al problema de toda España o por zonas); o bien escogemos aquellos sitios donde haya más hombre o más mayores, y después seleccionamos al azar dentro de esos sitios escogidos (sólo para el problema por zonas).</P>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-51105916505506948822019-03-02T04:53:00.001-08:002019-03-06T14:42:11.924-08:00¿Cuánto cuesta encontrar el número más probable en una ruleta?<P>Alguien me ha preguntado recientemente si teniendo los números que han salido en 6.000 partidas
de ruleta se podría averiguar a qué número habría que apostar. La pregunta me ha intrigado...</P>
<P>Es sorprendente, pero 6.000 partidas no son muchas. "Muchas", "pocas" o "suficientes" dependerá de
cuánto se aparten las probabilidades de 1/37. He googleado un poco, pero no he encontrado ningún sitio
donde hablen de esto; los fabricantes afirman que sus ruletas están maravillosamente equilibradas y
que usan la teoría del caos para diseñarlas de forma que sean impredecibles, pero por ninguna parte
se menciona nada parecido a una tolerancia.</P>
<P>Admito mi ignorancia pero, como estoy intrigado, no me rindo, así que me voy a inventar una tolerancia.</P>
<P>Lo ideal sería que todos los números tuviesen una probabilidad de 1/37; de esta forma, apuestes al
número al que apuestes, esperas perder 1/37 de tu apuesta, porque ganas 35 con probabilidad 1/37, pierdes
1 con probabilidad 36/37, y 35*1/37-1*36/37 = -1/37.</P>
<P>Si las probabilidades reales de un número se desvían menos de un 1%, no pasará gran cosa, el casino
seguirá ganando bastante.</P>
<P>El casino empezaría a tener problemas si alguno de los números llegase a tener probabilidad 1/36
(que está un 2.7% por encima de 1/37). Si esto ocurre, es posible "jugar gratis" apostando a ese número,
porque 35*1/36-1*(1-1/36)=0; es decir, ni se gana ni se pierde. Quizás el casino podría tolerar que un
jugador hiciera esto mientras no se lo contase a los demás, o a lo mejor el casino no se daría cuenta
porque le sería difícil detectarlo (lo veremos a continuación).</P>
<P>Lo que sí que no creo que ningún casino pueda tolerar es que un número de la ruleta llegue a tener
una probabilidad de 38/(36*37), un 5.5% por encima de 1/37, porque en ese momento el jugador que conozca
esto jugará con tanta ventaja sobre el casino como la que el casino tiene normalmente sobre los jugadores;
35*38/(36*37)-1*(1-38/(36*37))=1/37. Así que se ganaría un 1/37 de lo apostado, que es lo que normalmente
hace el casino. No sólo sería intolerable, es que además me imagino que se notaría mucho si se hiciese
mucho tiempo. Aquí "intolerable" no quiere decir nada mafioso: el casino cambiaría la ruleta y dejaría
que el jugador siguiese jugando para que perdiese lo ganado anteriormente.</P>
<P>Así que me he inventado el criterio de que las ruletas en un casino legal (las cosas serán diferentes
en timbas en furgonetas) pueden llegar a tener, como mucho, una probabilidad de que salga un número de
75/2664, que está a mitad de camino entre 1/36 y 38/(36*37).</P>
<P>Vale, quizás esto es un disparate; de hecho, yo apostaría a que será muy poco probable que en un casino
con ruletas modernas haya algún número con probabilidad de salir por encima de 1/36. Pero bueno,
imaginemos que precisamente queremos encontrar una ruleta que está estropeada. El caso es que ya tengo un
límite con el que echar cuentas.</P>
<P>El problema entonces es el siguiente. Tenemos una ruleta en la que un número (no sabemos cuál) sale
con probabilidad 75/2664, y todos los demás números salen con probabilidad 2589/95904. Tengo los
resultados de 6.000 partidas. ¿Puedo decir que el número buscado es simplemente el número que aparece más
veces en mi lista de 6.000 resultados?</P>
<P>Sorpresa: no; he simulado esto 100.000 veces, y sólo se acierta en el 8.4% de las ocasiones.</P>
<P>Esto puede parecer sorprendente, pero en realidad está claro por qué ocurre. En promedio, la diferencia
entre que un número salga en el 1/37 o en el 75/2664 de 6.000 partidas es 162 y 169; pero la desviación
típica del número de veces que sale es aproximadamente 12; así que la diferencia que buscamos (7) es menor
que la variación de nuestro número debida al azar. Pero es que en realidad vamos a mirar al máximo del
número de veces que han los 37 números; que tiene media 190 y desviación típica 6.1. Es decir, que lo
normal es que alguno de los 36 números con probabilidad pequeña tenga suerte y salga 21 veces más que el
que en principio debería ser el favorito.</P>
<P>Vale, con 6.000 partidas acertamos el 8.4% de las veces.</P>
<P>Pero con 20.000 partidas acertamos el 16% de las veces.</P>
<P>Y con 200.000 partidas acertamos el 82.6% de las veces.</P>
<P>Se me ha ocurrido otro "juego". Volvamos a una ruleta con un número que sale con probabilidad 75/2664.
Primero observo sin jugar 6.000 partidas, y entonces empiezo a jugar, pero sigo contando cuántas veces
sale cada número, y siempre apuesto al que ha salido con más frecuencia. En algún momento acertaré con el
número correcto y empezaré a ganar sistemáticamente, porque mi ordenador va a jugar millones de partidas.
La cuestión es, ¿cuál es la última partida en la que voy perdiendo? Para esto no me basta con simplemente
encontrar el número correcto, sino que también tengo que recuperarme de las malas rachas que podría haber
tenido al principio.</P>
<P>Los resultados son francamente decepcionantes. He simulado este juego 100.000 veces. En 39 ocasiones
ha empezado a ganar desde el principio; lo normal es que se llegue a estar perdiendo unas 200.000
partidas; y en el 2,6% de las simulaciones hubo que jugar más de un millón de partidas antes de quedarse
permanentemente en verde. Aquí están los resultados:</P>
<CENTER><TABLE><TR><TH>Intervalo</TH><TH>n</TH></TR>
<TR><TD>6000-6000</TD><TD>39</TD></TR>
<TR><TD>6001-6500</TD><TD>4067</TD></TR>
<TR><TD>6501-7000</TD><TD>2091</TD></TR>
<TR><TD>7001-8000</TD><TD>1980</TD></TR>
<TR><TD>8001-10000</TD><TD>2993</TD></TR>
<TR><TD>10001-20000</TD><TD>9320</TD></TR>
<TR><TD>20001-50000</TD><TD>15778</TD></TR>
<TR><TD>50001-100000</TD><TD>14678</TD></TR>
<TR><TD>100001-200000</TD><TD>15099</TD></TR>
<TR><TD>200001-500000</TD><TD>20520</TD></TR>
<TR><TD>500001-1000000</TD><TD>10781</TD></TR>
<TR><TD>1000001-inf</TD><TD>2654</TD></TR>
</TABLE></CENTER>
<P>Todo esto no encaja muy bien con las historias que todos conocemos de gente que ha hecho saltar la
banca. En España son famosos los Pelayo, pero hay muchos héroes parecidos en otros países. Se me ocurren
tres explicaciones:</P>
<OL>
<LI>Quizás cuando nos cuentan estas historias no enfatizan lo suficiente cuantísimas noches se pasaron
apuntando números. O a lo mejor somos nosotros los que no escuchamos eso.</LI>
<LI>Podría ser que las ruletas sean mucho menos imparciales de lo que yo me he inventado. Imaginemos que
la probabilidad de que salga un cierto número en una ruleta fuese el 4% en vez del 2.7% normal; entonces,
con los datos de 6.000 partidas pasadas acertaríamos el 99.9% de las veces. Quizás el truco no está en
trabajar mucho buscando el mejor número en una ruleta normal, sino en encontrar rápido una ruleta desastrosa.
Lo que pasa es que me cuesta creer que el casino no se dé cuenta de que tiene una ruleta estropeada; vamos,
cuando yo he estado en un casino, los números que salen en las ruletas van apareciendo en una pantalla, así
que me imagino que algún ordenador debe de ir comprobando que los números que salen son normales. Quizás
parte del truco está en buscar casinos negligentes en vez de limitarse a buscar ruletas defectuosas.</LI>
<LI>He estado pensando en el caso de que sólo un número sea más probable que los demás, pero a lo mejor es
más fácil detectar si el eje de la ruleta está desviado; entonces la mitad de los números será un poco más
probable que la otra mitad, y esto debería ser bastante más fácil de detectar estadísticamente que un
número solo. (Por cierto, no importa mucho que la mesa de la ruleta esté inclinada si la ruleta está bien
equilibrada; si, es verdad que las bolas acabarán con más frecuencia en la parte baja de la mesa, pero el
número que habrá ahí irá cambiando.)
</LI>
</OL>
<P>Aquí dejo el programa usado, en C++.</P>
<center><textarea rows="4" cols="50">
#include "stdafx.h"
#include <string>
#include <fstream>
#include <iostream>
#include "math.h"
#include <time.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int NDATOS = 6000;
// Generación de número aleatorios
unsigned int randomz, randomw;
void initializeRandomSeq() {
srand( (unsigned)time( NULL ) );
randomz = rand();
randomw = rand();
}
double random() { // Get a random number with uniform distribution U(0,1)
randomz = 36969*(randomz&65535)+(randomz>>16);
randomw = 18000*(randomw&65535)+(randomw>>16);
return 0.00000000023283064365386962890625*double((randomz<<16)+(randomw&65535));
}
int ruletaJusta() { return (int)(37*random()); }
// La ruleta desviada devuelve 36 con probabilidad provDesv,
// y el resto de los números con probabilidad (1-probDesv)/36
const double probDesv = 75./2664.;
int ruletaDesviada() {
double r = random();
if (r < probDesv) return 36;
return (int)((r-probDesv)*36/(1-probDesv));
}
int _tmain(int argc, _TCHAR* argv[]){
clock_t time0 = clock();
initializeRandomSeq();
/*
// Cálculo desviación típica número de veces que sale un número en 6000 partidas
int * nEn6000 = new int[100000]; int * count = new int[37];
int suma = 0;
for (int repeticion = 0; repeticion < 100000; repeticion++) {
for (int i = 0; i < 37; i++) count[i] = 0;
for (int partida = 0; partida < 6000; partida++) {
count[ruletaJusta()]++;
}
int max = count[0];
for (int i = 1; i < 37; i++) if (count[i] > max) max = count[i];
nEn6000[repeticion] = max;
suma = suma + max;
}
double promedio = suma / 100000.0;
double stdev = 0.0;
for (int i = 0; i < 100000; i++) {
stdev = stdev + (nEn6000[i]-promedio)*(nEn6000[i]-promedio);
}
stdev = sqrt(stdev/99999);
cout << "promedio = " << promedio << ", desviación típica = " << stdev << "\n";
delete[] nEn6000; delete[] count;
*/
// Cálculo de la probabilidad de acertar el número más probable de la ruleta
int * count = new int[37];
int nAciertos = 0;
int nFallos = 0;
for (int rep = 0; rep < 100000; rep++) {
for (int i = 0; i < NDATOS; i++) count[ruletaDesviada()]++;
int imax = 0; int max = count[0];
for (int i = 1; i < 37; i++) {
if (count[i] >= max) {
max = count[i];
imax = i;
}
}
if (imax == 36) {
nAciertos++;
}else{
nFallos++;
}
}
cout << "se acierta el " << 100.*nAciertos/(nAciertos+nFallos) << " % de las veces\n";
delete[] count;
/*
// Apostar al número más frecuente en una ruleta no imparcial, y ver cuándo es la última partida
// en la que pierdo
int * count = new int[37]; for (int i = 0; i < 37; i++) count[i] = 0;
int * countIntervalos = new int[12]; for (int i = 0; i < 12; i++) countIntervalos[i] = 0;
int maxIntervalo[12] = {6000, 6500, 7000, 8000, 10000, 20000, 50000, 100000, 200000, 500000, 1000000, 2000000000};
for (int repeticion = 0; repeticion < 100000; repeticion++) {
for (int i = 0; i < NDATOS; i++) count[ruletaDesviada()]++; // 6000 partidas iniciales
int saldo = 0; // lo que llevo ganado
int ultimaPartidaPerdiendo = NDATOS; // la última partida en la que perdí
int partida = NDATOS; // la partida actual
int n = 0; // el número que ha salido con más frecuencia
int max = count[0]; // cuántas veces ha salido el número más frecuente
for (int i = 1; i < 37; i++) if (count[i] > max) { max = count[i]; n = i; } // buscar el máximo
while (partida < ultimaPartidaPerdiendo + 1000000 && partida < 1900000000) { // cuando llevemos un millón de partidas en verde, creemos que ya no perderemos nunca más
partida++;
int sale = ruletaDesviada();
if (sale == n) {
saldo = saldo + 35; // aposté a n porque era el más frecuente, y he ganado
}else{
saldo = saldo - 1;
}
count[sale]++;
if (count[sale] > max) { // mirar si el número que acaba de salir se convierte en el más frecuente
n = sale;
max = count[sale];
}
if (saldo < 0) ultimaPartidaPerdiendo = partida; // mirar si sigo perdiendo
}
cout << repeticion << " -> " << ultimaPartidaPerdiendo << "\n";
int intervalo = 0;
while (ultimaPartidaPerdiendo > maxIntervalo[intervalo]) {
intervalo++;
}
countIntervalos[intervalo]++;
}
for (int intervalo = 0; intervalo < 12; intervalo++) {
if (intervalo == 0) cout << "6000-"; else cout << maxIntervalo[intervalo-1]+1 << "-";
if (intervalo == 11) cout << "inf"; else cout << maxIntervalo[intervalo];
cout << " " << countIntervalos[intervalo] << "\n";
}
delete[] count; delete[] countIntervalos;
*/
cout << "time spent = " << clock() - time0 << " ms\n"; cout << "press any key to end\n"; char cinget; cin.get(cinget); return 0;
}
</textarea></center>
<P>Nota añadida: me confirman que los Pelayo detectaban una mitad de la ruleta en la que la bola tenía más probabilidades de acabar,
como si tuviese el eje torcido. Esto tiene mucho más sentido que buscar un número ligeramente mejor que el resto.</P>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-67161534768258104472018-01-13T19:54:00.001-08:002018-01-13T19:54:02.353-08:00Cadena más larga de 100 números<p>Le he estado dando vueltas a un problema curioso en <a href="http://simplementenumeros.blogspot.com.es/2013/05/1130-los-numeros-del-1-al-100.html">http://simplementenumeros.blogspot.com.es/2013/05/1130-los-numeros-del-1-al-100.html</a>.
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.</p>
<p>Una solución es la siguiente cadena de 77 números:</p>
<p>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</p>
<p>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.
<p>La cadena tiene la siguiente estructura:
<ul>
<li>4 múltiplos de 19, y el 5;</li>
<li>4 múltiplos de 17, y el 4;</li>
<li>4 múltiplos de 23 y el 3;</li>
<li>3 múltiplos de 29 y el 2;</li>
<li>3 múltiplos de 31 y el 1;</li>
<li>y finalmente una cadena de 54 números múltiplos de 2, 3, 5, 7, 11 y 13.</li></ul></p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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:</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsslCyZ8BHCBBKSrwxgQkOO4WKqtr8kz2SkkA-eTkn4Wf6qqxlz3O91jKQgrReUnH3ZqVY62sQlW6aiT50RKi04Cv04QaxeP2nqczcNUd2t_j4i7VXxoDYnKOoq57E0yfKaB-JrZmI6pCm/s1600/grafo+1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhsslCyZ8BHCBBKSrwxgQkOO4WKqtr8kz2SkkA-eTkn4Wf6qqxlz3O91jKQgrReUnH3ZqVY62sQlW6aiT50RKi04Cv04QaxeP2nqczcNUd2t_j4i7VXxoDYnKOoq57E0yfKaB-JrZmI6pCm/s400/grafo+1.png" width="400" height="217" data-original-width="481" data-original-height="261" /></a></div>
<p>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.</p>
<p>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).</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiH1WFGh5rDj4E1ufNwCf4zQqkqcoCSYlqi-2pBnZeJ8T8L-2g5OYpGPfSSHHilhfYp2he8j6ylivgfcfvyPMFrttTFYBAp-IzjCebdJYOApzv6YV3Kap17t6nAj28-EQrWGKPvec9GViok/s1600/grafo2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiH1WFGh5rDj4E1ufNwCf4zQqkqcoCSYlqi-2pBnZeJ8T8L-2g5OYpGPfSSHHilhfYp2he8j6ylivgfcfvyPMFrttTFYBAp-IzjCebdJYOApzv6YV3Kap17t6nAj28-EQrWGKPvec9GViok/s400/grafo2.png" width="400" height="175" data-original-width="425" data-original-height="186" /></a></div>
<p>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.</p>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-11560674086966675042018-01-12T17:30:00.001-08:002018-01-12T17:30:56.678-08:00Historias y probabilidades<p>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.</p>
<p>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?"</p>
<p>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.</p>
<p>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).</p>
<p>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.</p>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-2035215856456738372018-01-10T17:40:00.004-08:002018-01-10T17:40:39.213-08:00Otro problema chulo de grafos<p>Hace tiempo leí otro de esos problemas chulos de grafos sin datos, vagamente parecido al que ya conté de los <a href="http://jugandoaprogramar.blogspot.com.es/2011/08/enlaces-paginas-de-problemas.html">señores Mancha</a>, aunque este es más fácil.</p>
<p>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?</p>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-7126010649331850362018-01-10T16:38:00.001-08:002018-01-10T16:38:37.534-08:00Formas de montar una escena<p>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.</p>
<p>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.</p>
<p>¿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...</p>
<p>En términos matemáticos, se quiere el número de permutaciones de subconjuntos no vacíos de un conjunto de n elementos.</p>
<p>En total,</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgURE1gSDC5AjqRhKf-fjetp3SPpZtQ3y5CxytMp-jAw-iNrk7zsbTBvV41-ILkX-fye84f0ypA0krtVgF1Y-eIZIZuimMAgTpcFbA7rQV5Oj0aajumqxYxj2vzLr1QzchGXiwZVfeDHcwa/s1600/problema+numero+tomas.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgURE1gSDC5AjqRhKf-fjetp3SPpZtQ3y5CxytMp-jAw-iNrk7zsbTBvV41-ILkX-fye84f0ypA0krtVgF1Y-eIZIZuimMAgTpcFbA7rQV5Oj0aajumqxYxj2vzLr1QzchGXiwZVfeDHcwa/s320/problema+numero+tomas.png" width="320" height="106" data-original-width="354" data-original-height="117" /></a></div>
<p>Así que la fórmula es rara pero correcta, al redondear el resultado al entero más cercano dará la respuesta correcta.</p>
<p>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.</p>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-77400971787996878522017-09-03T03:56:00.001-07:002017-09-03T03:56:57.505-07:00El problema de las n reinas<P>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.</P>
<P>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.</P>
<P><A HREF="http://www.hispantv.com/noticias/deporte/352348/premio-million-problema-ajedrez-ocho-reinas">http://www.hispantv.com/noticias/deporte/352348/premio-million-problema-ajedrez-ocho-reinas</A></P>
<P><A HREF="http://jair.org/media/5512/live-5512-10126-jair.pdf">http://jair.org/media/5512/live-5512-10126-jair.pdf</A></P>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-58118571793462796702017-02-11T09:56:00.000-08:002017-02-11T09:58:08.777-08:00Los colores viven en un cono<P>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.</P>
<P>Vaya frikez; la próxima vez que me pregunten para qué sirven las geometrías exóticas, ya sé qué responder.</P>
<P><A HREF="https://en.wikipedia.org/wiki/HSL_and_HSV">https://en.wikipedia.org/wiki/HSL_and_HSV</A></P>
<P><A HREF="https://es.wikipedia.org/wiki/Modelo_de_color_HSV">https://es.wikipedia.org/wiki/Modelo_de_color_HSV</A></P>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-68991157658054795382016-07-19T15:02:00.001-07:002016-07-19T15:02:51.557-07:00Algoritmos para el problema de los vales
<P>(Esta entrada es continuación de <A HREF="http://jugandoaprogramar.blogspot.com.es/2016/07/el-problema-de-los-vales.html">ésta</A>).</P>
<P>Recordatorio: el problema consiste en que queremos comprar unos productos de precios p<SUB>i</SUB> 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.</P>
<P>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?</P>
<P>Mi amigo sugirió este algoritmo:</P>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlSTFbxE4YPpRtDmBGszvjk31VphKLXvFRyu3ysafpXd0vJ4CRCt5GHfQ5sGmlj7CQMaOSD1cT4MIpORcPFow2GGxe0il9rCOlUG1NRIkQfo6Nba9yGz5eF6sr54A8c0sOLdixg76oM82J/s1600/039+El+problema+de+los+vales+2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlSTFbxE4YPpRtDmBGszvjk31VphKLXvFRyu3ysafpXd0vJ4CRCt5GHfQ5sGmlj7CQMaOSD1cT4MIpORcPFow2GGxe0il9rCOlUG1NRIkQfo6Nba9yGz5eF6sr54A8c0sOLdixg76oM82J/s320/039+El+problema+de+los+vales+2.png" width="320" height="196" /></a></div>
<P>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.</P>
<UL>
<LI>Mientras el precio de los artículos que quedan por pedir exceda C:
<UL>
<LI>Averiguar el precio de pedido más pequeño que se puede hacer que exceda C</LI>
<LI>Encontrar un conjunto de artículos que tenga ese precio</LI>
<LI>Hacer un pedido con ese conjunto</LI>
</UL>
<LI>Añadir los artículos que sobran al último pedido, si se ha hecho algún pedido, o hacer con ellos el primer pedido.</LI>
</UL>
<P>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:</P>
<UL>
<LI>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.</LI>
<LI>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.</LI>
</UL>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-34202682814243712132016-07-15T17:08:00.000-07:002016-07-20T02:18:02.604-07:00El problema de los vales<P>He estado pensando con un amigo sobre el siguiente problema.</P>
<P>Quiero comprar en un supermercado n productos de precios estrictamente positivos {p<SUB>i</SUB>}. Por cada compra que haga de
<B>más de C euros</B> 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?</P>
<P>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 <A HREF="https://en.wikipedia.org/wiki/Bin_packing_problem">bin packing</A>, que sabemos que es NP-completo.</P>
<P>Empezaremos formulando los dos problemas formalmente:</P>
<OL>
<LI><B>Vales</B>. Dados un número de productos n, sus precios {p<SUB>i</SUB>>0}<SUB>i=1</SUB><SUP>n</SUP>, y la cantidad mínima C con la
que obtener un vale, encontrar una partición {S<SUB>i</SUB>} de {p<SUB>i</SUB>} con el número <B>máximo</B> de conjuntos tales que
Σ<SUB>S<SUB>i</SUB></SUB>p<SUB>i</SUB> > C. Dada una solución, llamaré p<SUB>ki</SUB> a los precios de los productos de la compra k.</LI>
<LI><B>Bin packing</B>. Dada una colección ilimitada de contenedores de volumen V, un número de objetos n, y sus volúmenes {a<SUB>i</SUB><V}<SUB>i=1</SUB><SUP>n</SUP>,
encontrar una partición {S<SUB>i</SUB>} de {a<SUB>i</SUB>} con el número <B>mínimo</B> de conjuntos tales que
Σ<SUB>S<SUB>i</SUB></SUB>a<SUB>i</SUB> ≤ V. Dada una solución, llamaré a<SUB>ki</SUB> 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<SUB>i</SUB>=V, pero como ellos solos llenarían un contenedor, los quitaría del problema.)</LI>
</OL>
<P>La idea de la demostración es sencilla, consiste simplemente en tomar p<SUB>i</SUB> = V-a<SUB>i</SUB>, pero se complica bastante por el camino.</P>
<P>Vamos al grano. Supongamos que puedo resolver los problemas de vales en tiempo polinómico, y que tengo un problema de bin packing.</P>
<P>Para este problema de bin packing tendré un ε>0 definido de la siguiente manera:</P>
<P><CENTER>ε < min( min{a<SUB>i</SUB>}, (min{Σs<SUB>i</SUB> : {s<SUB>i</SUB>}⊂{a<SUB>i</SUB>}, Σs<SUB>i</SUB>>V} - V) / n)</CENTER></P>
<P>Es decir, ε es menor que cualquier a<SUB>i</SUB>, 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 <B>si
Σ(a<SUB>ki</SUB>-ε)<V, entonces Σa<SUB>ki</SUB>≤V</B>; porque, de lo contrario, Σa<SUB>ki</SUB>>V y estaría dentro del conjunto
de la definición de ε, luego ε≤(Σa<SUB>ki</SUB>-V)/n, y por tanto V≤Σa<SUB>ki</SUB>-n·ε; pero, dado que como mucho hay
n términos en la suma, V≤Σ(a<SUB>ki</SUB>-n), y de aquí la contradicción.<P>
<P>Claro, esta definición plantea un <B>problema filosófico</B>; 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.</P>
<P>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):</P>
<OL>
<LI>Hay n·m productos;</LI>
<LI>el precio de los n primeros productos es V-a<SUB>i</SUB>+ε;</LI>
<LI>el precio de los siguientes n·(m-1) productos, que llamaré <B>comodines</B>, es V;</LI>
<LI>para conseguir un vale tengo que hacer una compra de más de C = (n-1)·V.</LI>
</OL>
<P>A continuación demostraré cuatro proposiciones sobre este problema que depende de m.</P>
<P><B>Primera, todos los productos en este problema tienen un precio p<SUB>i</SUB>≤V</B>, y los únicos que tienen precio V son los comodines. Porque si V-a<SUB>i</SUB>+ε>V, entonces
ε>a<SUB>i</SUB>.</P>
<P><B>Segunda, si el problema de vales con m tiene soluciones con m compras, entonces todas sus compras tienen exactamente n productos</B>. 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.</P>
<P><B>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</B>. 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<SUB>k</SUB> objetos del contenedor k con volumen a<SUB>ki</SUB> a productos de la compra k con precio V-a<SUB>ki</SUB>+ε, y luego añadiendo n-j<SUB>k</SUB>
comodines de precio V hasta tener n productos; se consigue un vale por cada compra porque, como Σa<SUB>ki</SUB>≤V, entonces</P>
<P><CENTER>Σp<SUB>ki</SUB>
= Σ(V-a<SUB>ki</SUB>+ε) + (n-j<SUB>k</SUB>)·V<BR>
= j<SUB>k</SUB>·V - Σa<SUB>ki</SUB> + j<SUB>k</SUB>·ε + n·V - j<SUB>k</SUB>·V<BR>
= n·V + j<SUB>k</SUB>·ε - Σa<SUB>ki</SUB><BR>
≥ n·V + ε - V = C + ε > C</CENTER></P>
<P>donde sabemos que j<SUB>k</SUB>≥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.</P>
<P><B>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</B> (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<SUB>ki</SUB>>C=(n-1)·V, y en esa suma hay n-j<SUB>k</SUB> comodines,</P>
<P><CENTER>Σ(V-a<SUB>ki</SUB>+ε) + (n-j<SUB>k</SUB>)·V > (n-1)·V</CENTER></P>
<P><CENTER>j<SUB>k</SUB>·V - Σ(a<SUB>ki</SUB>-ε) + (n-j<SUB>k</SUB>)·V > (n-1)·V</CENTER></P>
<P><CENTER>V > Σ(a<SUB>ki</SUB>-ε)</CENTER></P>
<P>Al definir ε se demostró que esa última desigualdad implica Σa<SUB>ki</SUB> ≤ 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.</P>
<P><B>Juntando todo esto</B>, el siguiente algoritmo encuentra la solución del problema de bin packing en tiempo polinómico:</P>
<UL>
<LI>Si no hay objetos, devolver m = 0.</LI>
<LI>Para m = 1, 2, ...</LI>
<LI> Si el problema de vales con m tiene una solución, devolver m.</LI>
</UL>
<P>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.</P>
<P>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.</P>
<P>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<SUB>i</SUB>+ε = 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).</P>
<P>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.</P>
<P>Es una reducción muy fea, lo admito...</P>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-63695049909223479342015-04-26T16:14:00.002-07:002015-04-26T16:14:59.411-07:00Dos demostraciones de que existen infinitos números primos
<P>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í.</P>
<P><B>Primera demostración</B>. Sean r<sub>1</sub>, r<sub>2</sub>,
... , r<sub>n</sub> n números impares relativamente primos entre sí.
Entonces el número</P>
<CENTER>N=3·(2<sup>r<sub>1</sub>·r<sub>2</sub>·...·r<sub>n</sub></sup>-1)</CENTER>
<P>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.</P>
<P>Los n+1 factores son 3 y s<sub>i</sub> = 2<sup>n<sub>i</sub></sup>-1.
Es fácil ver que 3 divide a N pero no a s<sub>i</sub>; también se
ve que s<sub>i</sub> divide a N porque para todos a y b impares</P>
<CENTER>2<sup>ab</sup>-1 = (2<sup>a</sup>-1)·(2<sup>a(b-1)</sup>-2<sup>a(b-2)</sup>+2<sup>a(b-3)</sup>-...+2<sup>2a</sup>-2<sup>a</sup>+1)</CENTER>
<P>Falta demostrar que los s<sub>i</sub> 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<sup>a</sup>-1 y 2<sup>b</sup>-1.
Como</P>
<CENTER>2<sup>a+b</sup>-1 = 2<sup>a</sup>(2<sup>b</sup>-1)+2<sup>a</sup>-1</CENTER>
<P>tenemos que</P>
<CENTER>resto ( 2<sup>a+b</sup>-1 , 2<sup>b</sup>-1 ) = resto ( 2<sup>a</sup>-1 , 2<sup>b</sup>-1 )</CENTER>
<P>y</P>
<CENTER>mcd(2<sup>a+b</sup>-1, 2<sup>b</sup>-1) = mcd(2<sup>a</sup>-1, 2<sup>b</sup>-1)</CENTER>
<P>y por tanto se puede aplicar el
<a href="http://es.wikipedia.org/wiki/Algoritmo_de_Euclides">algoritmo de Euclides</a>
para calcular el máximo común divisor entre 2<sup>a</sup>-1 y 2<sup>b</sup>-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<sup>a</sup>-1 y 2<sup>b</sup>-1 da 1, si y solo si 2<sup>a</sup>-1 y 2<sup>b</sup>-1 son
primso relativos. Quizás un ejemplo lo aclare; para a=7 y b=17:</P>
<center>
<table border = 1 cellpadding = 4 cellspacing = 0>
<tr>
<th>mcd(7, 17)</th><th>mcd(2<sup>7</sup>-1, 2<sup>17</sup>-1) en binario</th>
</tr>
<tr><td> mcd(<B><FONT COLOR="RED">7</FONT></B> ,17) = </td><td>mcd(<B><FONT COLOR="RED">1111111<sub>2</sub></FONT></B>, 11111111111111111<sub>2</sub> = </td></tr>
<tr><td> mcd(<B><FONT COLOR="RED">7</FONT></B> ,<B><FONT COLOR="GREEN">3</FONT></B>+<B><FONT COLOR="RED">7</FONT></B>*2) = </td><td> mcd(<B><FONT COLOR="RED">1111111<sub>2</sub></FONT></B>, <B><FONT COLOR="GREEN">111<sub>2</sub></FONT></B> + <B><FONT COLOR="RED">1111111<sub>2</sub></FONT></B> · 10000001000<sub>2</sub>) = </td></tr>
<tr><td> mcd(<B><FONT COLOR="RED">7</FONT></B> ,<B><FONT COLOR="GREEN">3</FONT></B>) = </td><td> mcd(<B><FONT COLOR="RED">1111111<sub>2</sub></FONT></B>, <B><FONT COLOR="GREEN">111<sub>2</sub></FONT></B>) = </td></tr>
<tr><td> mcd(<B><FONT COLOR="GREEN">3</FONT></B> ,<B><FONT COLOR="RED">7</FONT></B>) = </td><td> mcd(<B><FONT COLOR="GREEN">111<sub>2</sub></FONT></B>, <B><FONT COLOR="RED">1111111<sub>2</sub></FONT></B>) = </td></tr>
<tr><td> mcd(<B><FONT COLOR="GREEN">3</FONT></B> ,1+<B><FONT COLOR="GREEN">3</FONT></B>*2) = </td><td> mcd(<B><FONT COLOR="GREEN">111<sub>2</sub></FONT></B>, 1<sub>2</sub> + <B><FONT COLOR="GREEN">111<sub>2</sub></FONT></B> · 10010<sub>2</sub> = </td></tr>
<tr><td> mcd(<B><FONT COLOR="GREEN">3</FONT></B> ,1) = </td><td> mcd(<B><FONT COLOR="GREEN">111<sub>2</sub></FONT></B>, 1<sub>2</sub>) = </td></tr>
<tr><td> 1 </td><td> 1<sub>2</sub> </td></tr>
</table>
</center>
<P><b>Segunda demostración</b>. Sea p un número primo, y q un divisor
primo de 2<sup>p</sup>-1. Entonces 2<sup>p</sup>=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<sup>p</sup>-1 son mayores que p, y por tanto, para cada
primo p existe otro primo mayor, que se puede encontrar "simplemente"
factorizando 2<sup>p</sup>-1, de aquí que existan infinitos primos.</P>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-86991680482125897382013-07-16T12:02:00.000-07:002013-07-17T03:15:29.404-07:00Lo injusto de los sorteos por letras
<P>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.</P>
<P>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.</P>
<P>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,
<a href="http://undatovalemas.blogspot.com.es/2012/06/los-sorteos-por-letra-del-apellido-son.html">"Un dato vale más que mil palabras"</a>
y <a href="http://lacienciaparatodos.wordpress.com/2013/07/01/sorteos-por-letra-injustos/">"La ciencia para todos"</A>.
También está este artículo de una mujer cabreantemente apellidada <a href="http://www.jotdown.es/2013/05/la-importancia-de-llamarse-grima/">Grima</A>.
<P>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 <a href="http://undatovalemas.blogspot.com.es/2012/06/los-sorteos-por-letra-del-apellido-son.html">primer blog</A>:</P>
<CENTER>
<table border="0" cellpadding="0" cellspacing="0" class="MsoNormalTable" style="border-collapse: collapse; margin-left: 2.75pt; width: 237px;">
<tbody>
<tr style="height: 8.5pt; mso-yfti-firstrow: yes; mso-yfti-irow: 0;">
<td nowrap="" style="background: #F2F2F2; border: solid windowtext 1.0pt; height: 8.5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<br /></div>
</td>
<td style="background: #F2F2F2; border-left: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<b><span style="font-family: 'Trebuchet MS', sans-serif;">frecuencia<o:p></o:p></span></b></div>
</td>
<td style="background: #F2F2F2; border-left: none; border: solid windowtext 1.0pt; height: 8.5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<b><span style="font-family: 'Trebuchet MS', sans-serif;">% sobre el total <o:p></o:p></span></b></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 1;">
<td nowrap="" style="border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">A<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">2.884.390<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">6,7%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 2;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">B<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">2.263.664<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">5,2%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 3;">
<td nowrap="" style="background: red; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">C<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: red; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">3.969.992<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: red; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">9,2%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 4;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">D<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1.747.696<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">4,0%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 5;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">E<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">781.910<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1,8%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 6;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">F<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1.877.528<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">4,3%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 7;">
<td nowrap="" style="background: red; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">G<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: red; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">4.857.351<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: red; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">11,2%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 8;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">H<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">992.297<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">2,3%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 9;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">I<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">424.730<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1,0%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 10;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">J<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">722.854<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1,7%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 11;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">K<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">55.885<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">0,1%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 12;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">L<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">2.250.441<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">5,2%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 13;">
<td nowrap="" style="background: red; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">M<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: red; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">5.291.515<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: red; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">12,2%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 14;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">N<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">699.534<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1,6%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 15;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">O<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">803.973<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1,9%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 16;">
<td nowrap="" style="border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">P<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">3.042.595<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">7,0%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 17;">
<td nowrap="" style="border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">Q<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">185.195<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">0,4%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 18;">
<td nowrap="" style="border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">R<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">3.565.620<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">8,2%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 19;">
<td nowrap="" style="border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">S<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">3.201.882<o:p></o:p></span></div>
</td>
<td nowrap="" style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">7,4%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 20;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">T<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1.425.424<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">3,3%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 21;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">U<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">171.705<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">0,4%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 22;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">V<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">1.631.083<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">3,8%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 23;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">W<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">48.578<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">0,1%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 24;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">X<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">14.690<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">0,0%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 25;">
<td nowrap="" style="background: white; border-top: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">Y<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">92.553<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-right-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">0,2%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 26;">
<td nowrap="" style="background: white; border-bottom: none; border-left: solid windowtext 1.0pt; border-right: solid windowtext 1.0pt; border-top: none; height: 8.5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<span style="font-family: 'Trebuchet MS', sans-serif;">Z<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-right: solid windowtext 1.0pt; border: none; height: 8.5pt; mso-border-right-alt: solid windowtext .5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">269.539<o:p></o:p></span></div>
</td>
<td nowrap="" style="background: white; border-right: solid windowtext 1.0pt; border: none; height: 8.5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<span style="font-family: 'Trebuchet MS', sans-serif;">0,6%<o:p></o:p></span></div>
</td>
</tr>
<tr style="height: 8.5pt; mso-yfti-irow: 27; mso-yfti-lastrow: yes;">
<td nowrap="" style="background: #F2F2F2; border: solid windowtext 1.0pt; height: 8.5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 41.9pt;" valign="bottom" width="56"><div class="MsoNormal" style="margin-bottom: 0.0001pt;">
<b><span style="font-family: 'Trebuchet MS', sans-serif;">TOTAL<o:p></o:p></span></b></div>
</td>
<td nowrap="" style="background: #F2F2F2; border-left: none; border: solid windowtext 1.0pt; height: 8.5pt; mso-border-bottom-alt: solid windowtext 1.0pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext 1.0pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 75.3pt;" valign="bottom" width="100"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<b><span style="font-family: 'Trebuchet MS', sans-serif;">43.272.624<o:p></o:p></span></b></div>
</td>
<td nowrap="" style="background: #F2F2F2; border-left: none; border: solid windowtext 1.0pt; height: 8.5pt; padding: 0cm 3.5pt 0cm 3.5pt; width: 60.75pt;" valign="bottom" width="81"><div align="right" class="MsoNormal" style="margin-bottom: 0.0001pt; text-align: right;">
<b><span style="font-family: 'Trebuchet MS', sans-serif;">99,8%<o:p></o:p></span></b></div>
</td>
</tr>
</tbody></table></CENTER>
<P>Por si algún día le pasase algo al blog de <a href="http://undatovalemas.blogspot.com.es/2012/06/los-sorteos-por-letra-del-apellido-son.html">Eduardo</A>, también hago una copia de su histograma, que ilustra maravillosamente lo irregular que es la distribucion de las iniciales:</P>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj27YJJaxQ6Nhp7fJLkIlhPAvjq2O1Cgu-_islmyfDI9X0iCoZfyFR0p4rE4rS_9L-XcDpgGFiVSvvMptbQg1oEPz7TQ71dolE4WyEahveUdojSzXkNhyphenhyphenA82C1W1uW3DxevPpmV0v5BJxfj/s1600/sorteos.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj27YJJaxQ6Nhp7fJLkIlhPAvjq2O1Cgu-_islmyfDI9X0iCoZfyFR0p4rE4rS_9L-XcDpgGFiVSvvMptbQg1oEPz7TQ71dolE4WyEahveUdojSzXkNhyphenhyphenA82C1W1uW3DxevPpmV0v5BJxfj/s320/sorteos.jpg" /></a></div>
<P>Para echar las cuentas, he escrito este programita:</P>
<textarea rows="8" cols="50">
#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";
}
</textarea>
<P>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.<P>
<P>Hasta aquí no hay ninguna sorpresa, era obvio que el sistema era especialmente injusto si la probabilidad de ganar era pequeña.</P>
<P>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).</P>
<P>¿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.</P>
<P>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.</P>
<P>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.</P>
<P>Es previsible que este sistema funcione incluso peor en pueblos pequeños donde algunos apellidos se repiten mucho.</P>
<P>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í.</P>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com3tag:blogger.com,1999:blog-7180253365154170747.post-72298947871142352462013-06-22T05:45:00.001-07:002013-06-22T05:45:15.048-07:00Simulación de olas<P>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.</P>
<P>He intentado publicar aquí un video en formato .avi, pero no he conseguido que funcione, así pongo un enlace en <a href="https://www.facebook.com/photo.php?v=436705566365921¬if_t=like">Facebook</a>.</P>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-81984326620694243012013-05-23T16:18:00.001-07:002013-05-23T16:18:47.490-07:00Sintaxis bizarra<P>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:</P>
<PRE>
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];
</PRE>
<P>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).</P>
<P>La segunda línea, que ya empieza a ser rara, simplemente declara que
data es un puntero a un objeto del tipo descrito antes.</P>
<P>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.</P>
<P>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.</P>
<P>Para quien se haya quedado intrigado; Visual Studio es capaz de
compilar esta línea, pero ¿cómo la interpreta?</P>
<PRE>
double** b = (double**)(double* (***)[2][2][10]) new (double* (**)[2][50][2]) ();
</PRE>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-22700313234782012572013-03-24T04:40:00.000-07:002013-03-24T04:50:30.306-07:00Cómo ordenar una baraja cortándola<P>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?<P>
<P>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.<P>
<P>Ahora bien, si se permiten cortes en los que el mazo se divida en varios submazos, ¿se puede conseguir ordenarlo?<P>
<P>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.<P>
<P>La cuestión es si siempre podemos hacer esto, y cuántos cortes de qué tipo son necesarios.<P>
<P>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.<P>
<P>Sin embargo, tenemos el siguiente teorema:<P>
<P><B>Teorema:</B> si se permiten cortes de dos y tres bloques, siempre es posible ordenar un mazo de n cartas con 3n-3 cortes.</P>
<P><B>Demostración:</B> 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.<P>
<P>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.
<P>¿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 <nobr>780<SUP>16</SUP><40!</nobr> ; por tanto, el peor caso necesitará al menos 17 cortes.<P>
<P>En cambio, si permitimos cortes en dos, tres, ... , cuarenta bloques, tenemos que el número total de cortes que podemos usar es <nobr>2<SUP>39</SUP>-1</nobr> (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 <nobr>(2<SUP>39</SUP>-1)<SUP>4</SUP><40!</nobr>.</P>
<P>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; <B>AVISO</B>, es un programa feo de narices:</P>
<textarea rows="4" cols="50">
//#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;
}
</textarea>
<P>La idea es la siguiente.</P>
<P>Definamos un <B>tramo</B> 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 <B>bloques</B> (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.</P>
<P>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.</P>
<P>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.</P>
<P>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].<P>
<P>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).</P>
<P>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.</P>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-8699427844493061782013-01-30T15:45:00.003-08:002013-01-30T15:45:41.727-08:00Por qué el descubridor de la distribución t de Student no se llamaba Student<P>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.</P>
<P>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.</P>
<P>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.</P>
<P>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...</P>
<P>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.</P>
<P>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.</P>
<P>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.</P>
<P>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, <a href="http://www.econ.uba.ar/www/institutos/epistemologia/marco_archivos/ponencias/actas%20xiii/trabajos%20episte/urbisaia-brufman_trabajo.pdf">http://www.econ.uba.ar/www/institutos/epistemologia/marco_archivos/ponencias/actas%20xiii/trabajos%20episte/urbisaia-brufman_trabajo.pdf</a> o <a href="http://stats.org.uk/statistical-inference/Lenhard2006.pdf">http://stats.org.uk/statistical-inference/Lenhard2006.pdf</a> (la verdad es que no sé si hay mejores artículos donde cuenten bien esta historia, no he buscado mucho).</P>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-89483942052383293052012-08-21T16:21:00.000-07:002012-08-21T16:21:17.829-07:00Fotocópiame las pelotas / Mario Fernández<p>Recientemente tres amigos míos han publicado libros, así que voy a hacerles un poquito de publicidad gratuita.</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghWXWZi3ITN5KAezBWcIYcpTnsKviiZRrTybNfvHTz9fDVeOPSte9nTyNBypAOGroMJWryidG7j51apNVPlisUEn7iDKvng70Q21qJtiWQ1lOlo8Mf99iTDu1xEuQ37uc7UUwKjDWlcd8b/s1600/fotocopiame.jpg" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="320" width="208" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghWXWZi3ITN5KAezBWcIYcpTnsKviiZRrTybNfvHTz9fDVeOPSte9nTyNBypAOGroMJWryidG7j51apNVPlisUEn7iDKvng70Q21qJtiWQ1lOlo8Mf99iTDu1xEuQ37uc7UUwKjDWlcd8b/s320/fotocopiame.jpg" /></a></div>
<p>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".</p>
<p>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.</p>
<p>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. </p>
<p>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.</p>
<p><a href="http://www.youtube.com/watch?v=TbH__JJLkeI">Trailer publicitario</A>. Las <a href="http://issuu.com/rafaelfernandezezcritor/docs/fotocopiame_lite">30 primeras</a> páginas. Otras reseñas: <a href="http://mispelotas.micabeza.net/?p=119">Sergi Puertas</A>, <a href="http://mispelotas.micabeza.net/?p=161">Salva Dávila</a>, <a href="http://llibressenyordolent.blogspot.com.es/2012/03/fotocopiame-las-pelotas-mario-fernandez.html">Els llibres del Senyor Dolent</a>, <a href="http://blogs.20minutos.es/ezcultura/2007/01/30/diario-un-perdedor-fotocopiame-pelotas/">20 minutos</a>. Para comprar: <a href="http://mispelotas.micabeza.net/?page_id=23">Editorial Mi Cabeza</A>.</p>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-63517296267594903242012-08-21T16:16:00.001-07:002012-08-23T04:21:41.088-07:00Dies de porno i kleenex / Cesc Llaverias<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiV814WWz4yhBsthH-8pxJDpZKX5FvKPnUEv2Ipyb-iN5IPqyTrTcWztRfbg8PNX_GQCw6Tvd4afRAzXq5404J9eG3P8kEsJnGA5wLeCA0ABHRhpxPaznlPF4jmf3SB23YOPweBURYqOk2S/s1600/dpk.jpg" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="320" width="226" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiV814WWz4yhBsthH-8pxJDpZKX5FvKPnUEv2Ipyb-iN5IPqyTrTcWztRfbg8PNX_GQCw6Tvd4afRAzXq5404J9eG3P8kEsJnGA5wLeCA0ABHRhpxPaznlPF4jmf3SB23YOPweBURYqOk2S/s320/dpk.jpg" /></a></div>
<p>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.</p>
<p>Hay dos temas centrales en las diversas tramas: la búsqueda de sexo repetible y los trabajos basura. </p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>Editorial Autor-Editor; es posible que ya se pueda comprar <a href="http://www.cescllaverias.cat/comprar">aquí</a>. Pronto estará traducido al español (salió la semana pasada).</p>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com1tag:blogger.com,1999:blog-7180253365154170747.post-30284508256135302092012-08-21T16:11:00.001-07:002012-08-21T16:11:37.474-07:00Cenital / Emilio Bueso
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEip85KOZrewh6Ua_98YGJOrHdQOKGVei5zqXLoq2epKnpmDzWjQ_eaFvy1cHCfIuuCS-6PZ6gGXmmJKdXGCsOVJ-WDmyL-anZBljMhzS-ngqLozAnrOW6q_UxaZ6DX_WZdtAAkKqKz4-lVC/s1600/Cenital.jpg" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="320" width="205" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEip85KOZrewh6Ua_98YGJOrHdQOKGVei5zqXLoq2epKnpmDzWjQ_eaFvy1cHCfIuuCS-6PZ6gGXmmJKdXGCsOVJ-WDmyL-anZBljMhzS-ngqLozAnrOW6q_UxaZ6DX_WZdtAAkKqKz4-lVC/s320/Cenital.jpg" /></a></div>
<p>Este <b>NO</b> es un libro divertido.</p>
<p>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.</p>
<p>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?</p>
<p>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 <a href="http://es.wikipedia.org/wiki/Ecoaldea">ecoaldea</a> 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.</p>
<p>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.</p>
<p>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."</p>
<p>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 <a href="http://es.wikipedia.org/wiki/Pico_petrolero">pico del petróleo</a>, 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?</p>
<p>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.</p>
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com2tag:blogger.com,1999:blog-7180253365154170747.post-74508764998115543622012-02-28T15:50:00.002-08:002012-02-28T15:51:27.670-08:00Conjunción<p>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.</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyEgZUpXkgirZ2qnfGcTyN3SA_im6MNh3GQAyPJ-6wcsOW05Z5bV3PiKfxgSqOnDv7u9q6r2DBzIZR1j8vicRP634JInOPoJJYOeS-G2W5Iy-6SV4e2wQnzolXXiKFOBHtYFerUYYYAOF-/s1600/Luna%252C+J%25C3%25BApiter%252C+Venus%252C+27+y+28+feb+2012.jpg" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="320" width="302" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyEgZUpXkgirZ2qnfGcTyN3SA_im6MNh3GQAyPJ-6wcsOW05Z5bV3PiKfxgSqOnDv7u9q6r2DBzIZR1j8vicRP634JInOPoJJYOeS-G2W5Iy-6SV4e2wQnzolXXiKFOBHtYFerUYYYAOF-/s320/Luna%252C+J%25C3%25BApiter%252C+Venus%252C+27+y+28+feb+2012.jpg" /></a></div>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-69490663607797880832012-01-17T15:42:00.000-08:002012-01-17T15:42:04.287-08:00Otro concurso online de problemas matemáticos<p>He recibido una invitación para participar en otro concurso de problemas para freakies matemáticos: <a href="http://kurukshetra.org.in/2012/#!/Events/Online-Events/Cerebra.k">Cerebra</a>. Se celebrará los sábados 21 y 28 poco después de comer hora española.</p><p>Voy a ver si me apunto, porque los últimos fines de semana he estado sufriendo demasiado mientras espero a que salga el problema del <a href="http://projecteuler.net/">proyecto Euler</a>.</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR9h_Gw3JGzE295-U-_plvkT41ZFCzn_dqZrJTOeAWYI2GPJZ5vT4GtHMLy0E3Ks53a6jWoanDiUgDNZeJwvifKFDeuonQvSfiJ1l08GYpa8vGJVaB7QrVffqLPanuGRp8z2WPGfrcJaX-/s1600/ratita+esperando.JPG" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="284" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR9h_Gw3JGzE295-U-_plvkT41ZFCzn_dqZrJTOeAWYI2GPJZ5vT4GtHMLy0E3Ks53a6jWoanDiUgDNZeJwvifKFDeuonQvSfiJ1l08GYpa8vGJVaB7QrVffqLPanuGRp8z2WPGfrcJaX-/s320/ratita+esperando.JPG" /></a></div><p>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 <a href="http://es.wikipedia.org/wiki/Ataque_de_denegaci%C3%B3n_de_servicio">ataque de denegación de servicio</a>. 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.</p>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-24309138721134401872011-12-22T15:11:00.000-08:002011-12-22T15:11:53.568-08:00Problema real<p>Os voy a proponer un problema real de matemáticas financieras.</p><p>É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.</p><p>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.</p><p>¿Cuánto vale la empresa ahora? (es decir, antes de que los qataríes compren la mitad)</p><p>El problema es curioso porque parece que faltan datos... pero no.</p><p><a href="http://www.expansion.com/accesible/2011/12/16/catalunya/1324068132.html">http://www.expansion.com/accesible/2011/12/16/catalunya/1324068132.html</a></p>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-81842111562701074312011-10-25T14:33:00.001-07:002011-10-25T14:34:36.212-07:00EstadísticasOtra 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.Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com0tag:blogger.com,1999:blog-7180253365154170747.post-78343398103231582132011-08-27T10:11:00.000-07:002011-08-27T10:15:22.627-07:00Otro descubrimiento maravilloso que no lo es<h1>Otro descubrimiento maravilloso que no lo es<br />
</h1><p>¿Habéis oído hablar de Aidan Dwyer? Lo mismo no, dejadme que os copie unos titulares de la prensa española:</p><ul><li><a href="http://www.abc.es/20110823/ciencia/abci-nino-anos-puede-revolucionar-201108230749.html"><b>ABC</b>: "Un niño de 13 años puede revolucionar la energía solar"</a> (23 de agosto de 2011)</li>
<li><a href="http://www.rtve.es/noticias/20110824/nino-13-anos-crea-sistema-mejora-energia-solar-20-gracias-fibonacci/457029.shtml"><b>RTVE.es</b>: "Un niño de 13 años crea un sistema que mejora la energía solar en un 20% gracias a Fibonacci"</a> (24 de agosto de 2011)</li>
<li><a href="http://www.cronica.com.mx/nota.php?id_nota=599965"><b>La Crónica</b>: Joven de 13 años crea "árbol solar" que genera más energía que paneles</a> (21 de agosto de 2011)</li>
</ul><p>La historia viene a ser ésta. Un chico tiene que hacer un proyecto de ciencias, se da un paseo por un bosque para pensar, y se le ocurre cómo sacar más energía de los paneles solares al observar cómo están orientadas las hojas de los árboles. Tras inspirarse en la naturaleza, recupera un modelo matemático del siglo XIII de Leonardo de Pisa alias Fibonacci, lo usa para construir un modelo de árbol con células fotovoltaicas orientadas en diversas direcciones, y comprueba que funciona mejor que los paneles tradicionales.</p><p>Impresionante, ¿no? Veamos qué resortes nos toca esta noticia para que estemos dispuestos a creernos algo que parece demasiado bueno para ser verdad:</p><ul><li>El adolescente genial e inocente.</li>
<li>Culto a la naturaleza.</li>
<li>Reaprovecha conocimientos antiguos.</li>
<li>Es una idea fácil de entender.</li>
<li>Es algo útil.</li>
<li>Es un tema de moda.</li>
<li>Jolín, si es que hasta Fibonacci, el matemático mencionado, es "amistoso"; se le suele vincular con la <a href="http://es.wikipedia.org/wiki/N%C3%BAmero_%C3%A1ureo#El_n.C3.BAmero_.C3.A1ureo_en_el_arte_y_en_la_cultura">razón áurea</a>, un número relacionado con el arte, nada que ver con matemáticas aburridas. O sí, claro.</li>
</ul><p>Seamos sinceros, los científicos tienen/tenemos un problema de imagen; al público le parecen unos listillos pedantes que se gastan cantidades enormes de dinero en cosas que no se entienden, y nos encanta que les enmienden la plana. Cualquier artículo que diga que un experto se lo tiene que replantear todo deja un buen sabor de boca.</p><p>Así que cuando leemos sobre un chaval que ha descubierto que cambiando la orientación de los paneles solares se puede producir desde un 20% hasta un 50% más de energía, lo queremos creer. Seguro que a los expertos en energía solar nunca se les ha ocurrido eso de orientar los paneles, qué coño sabrán ellos.</p><p>Pero lo que revela el incidente es el pésimo nivel de nuestros periodistas científicos. Aquí nadie habla con un experto antes de publicar una noticia que a todos nos hace desconfiar. Me pregunto durante cuánto tiempo habrá gente que al ver paneles solares orientados paralelamente piense que están mal montados y que se hace así porque hay una conspiración para que la energía fotovoltaica no funcione bien.</p><p>(Cambiando de tema, los <a href="http://es.wikipedia.org/wiki/Panel_fotovoltaico">paneles fotovoltaicos de tercera generación</a> ya tienen una eficiencia del 45%. Vale que son carísimos y que en la práctica lo que se sigue usando son los paneles de primera generación, que sólo aprovechan alrededor del 8% de la luz, pero esto va mejorando poco a poco.)</p><p>El fallo de Aidan fue medir el <b>voltaje</b> de su árbol, en vez de su <b>potencia</b> (queremos los paneles solares para generar energía, no voltios). Resulta que, al usar un voltímetro sin carga, lo que estaba midiendo en realidad era el voltaje de la célula mejor orientada. La mayoría de sus células estaban peor orientadas que con el método tradicional, pero lo más probable es que alguna de ellas estuviese muy bien orientada hacia el sol, y era esta célula la que determinaba el voltaje medido (mientras no se usase la electricidad para nada). <a href="http://goo.gl/tE3bo">Aquí lo explican bastante bien</a>, aunque está en inglés.</p><p>Es posible que ahora Aidan esté avergonzado al ver que todo el planeta se dedica a explicar por qué hizo mal su proyecto, pero yo apostaría a que está cabreado con el primer periodista que empezó esta avalancha mediática de verano: "Mira que ya le dije que mi profesor de ciencias me había explicado el error, pero ese capullo quería un titular que vendiese". Pasa de todos, Aidan, tu idea era buena y merecía mirarse.</p>Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com2tag:blogger.com,1999:blog-7180253365154170747.post-29091056330059044472011-08-21T03:33:00.000-07:002011-08-21T03:33:17.269-07:00El motor de agua<p>Hace poco tuve una charla con alguien que todavía cree en el motor de agua. A mí me sonaba que esto estuvo de moda allá por la crisis energética de los 70, cuando yo era muy niño, y apenas recordaba nada, así que por pura curiosidad estuve googleando un poco para enterarme. Y bueno, he encontrado tantas cosas absurdas que me entraron ganas de escribir un articulito organizándolas.</p><p>Para no confundirnos, aclaremos que un motor de hidrógeno es un motor de explosión que usa hidrógeno en vez de gasolina; y que una célula de hidrógeno produce electricidad pero no es un motor. Las células de hidrógeno y los motores eléctricos son muchos más eficientes que los motores de explosión. Estas cosas funcionan, pero no son motores de agua. Un motor de agua usaría agua como combustible, no hidrógeno.</p><p><b>Primera sorpresa</b>: sigue habiendo en Internet bastante gente que habla del motor de agua como si pudiese funcionar, pero no hay absolutamente ningún debate. Si visitas una página "en contra" del motor de agua, se hablará de química y de entropía. Pero en las páginas "a favor" sólo hay conspiranoia sobre las empresas petroleras, y de la más chusquera.</p><p><b>La segunda sorpresa</b> ha sido descubrir que en realidad ha habido cientos de inventores del motor de agua, cualquiera diría que esta tecnología cuenta con una poderosa industria antes de existir. Veamos algunos casos de errores, estafas, manipulaciones, y otras confusiones:</p><ul><li>Entre los conspiranoicos hay ganas de hacer creer que esto del motor del agua es tan sencillo que ya se inventó en <a href="http://www.liberauto.com/articulos/historia/isaac-de-rivaz-y-el-motor-de-combustion-interna/art11.aspx">1807</a> (lástima que eso sea un motor de hidrógeno). He aquí una <a href="http://energialibrebcn.blogspot.com/">buena lista con 31 inventores</a> que supuestamente inventaron motores de agua, pero yo he buscado un poquito sobre los primeros, los del siglo XIX, y no he visto que inventasen nada por el estilo (parece que el motor de agua se convirtió en el Santo Grial de la ciencia durante el siglo XX). También es curioso que haya tanta gente convencida de que las referencias de Julio Verne (1828-1905) al hidrógeno les justifican.</li>
<li><b>Albert Elder von Filek</b> le vendió a Franco el secreto de la gasolina en polvo <a href="http://curistoria.blogspot.com/2009/07/albert-elder-von-filek-el-tipo-que.html">1</a> <a href="http://barcomasgrande.blogspot.com/2008_06_01_archive.html">2</a>. Aparecieron cosas en el BOE y en los <a href="http://hemeroteca.lavanguardia.com/preview/1940/01/21/pagina-6/33122294/pdf.html">periódicos</a>, hasta que se dieron cuenta de que aquéllo era un timo y enchironaron al austríaco. En realidad, hay formas de producir gasolina sintética a partir de carbón, como el <a href="http://es.wikipedia.org/wiki/Licuefacci%C3%B3n_directa_del_carb%C3%B3n">proceso Bergius</a>, pero son ruinosamente ineficientes, y Filek no pretendía usar carbón, sino agua.</li>
<li><b>Stanley A. Meyer</b> se convirtió en el prototipo de inventor asesinado por las fuerzas del mal. Un día estaba comiendo cuando de repente se puso a gritar "¡Me han envenenado! ¡Me han envenenado!". Y pocos minutos después moría de un aneurisma cerebral. Dejando al margen la cuestión de cómo un veneno podría causar un aneurisma, Meyer tenía un buggy en el que decía haber instalado una célula de combustible de su invención. El problema es que él fue la única persona que consiguió hacer funcionar su invento, y un tribunal le condenó a devolver 25.000 dólares a unos inversores; por si hubiese dudas, la sentencia decía <a href="http://groups.google.com/group/sci.energy.hydrogen/msg/8ee0acb80e943e21?hl">"gross and egregious fraud"</a>.</li>
<li><a href="http://www.gstrail.es/foro/fusion-fria-y-motores-de-agua-engano-del-petroleo-i-ii-y-iii-9667/"><b>Francisco Pacheco</b></a>, Bolivia 1943, y otros cuantos inventores. Entre otras cosas inventó una cortadora de césped que no funcionaba, evidencia indiscutible de que producía tanto hidrógeno que se ahogaba.</li>
<li><a href="http://www.cafebabel.es/article/25042/quien-mato-al-coche-de-agua.html"><b>Jean Chambrin</b> Francia 1975 y <b>Paul Pantone</b> EEUU 1998</a>, el segundo condenado por fraude.</li>
<li><a href="http://en.wikipedia.org/wiki/Hongcheng_Magic_Liquid"><b>Wang Hongcheng</b></a> China 1984, inventó la forma de convertir agua en un líquido inflamable. Ya me contarán por qué un país pobre, comunista, y dependiente de energía ajena le condenó a 10 años de cárcel en vez de explotar su invento (o cualquier otro invento occidental).</li>
<li>Cuando <a href="http://es.wikipedia.org/wiki/Fusi%C3%B3n_fr%C3%ADa"><b>Martin Fleischmann y Stanley Pons</b></a> anunciaron el descubrimiento de la fusión fría en 1986, aparecieron varios fraudes de tipos diferentes.</li>
<li><a href="http://www.nature.com/news/2007/070910/full/news070910-13.html"><b>Ramar Pillai</b></a> India 1996, descubrió que el agua mezclada con un orujo de hierbas puede impulsar motos.</li>
<li><a href="http://www.nj.gov/oag/newsreleases06/pr20061109d.html"><b>Patrick Kelly</b></a>, Idaho 2006, consiguió convencer a unos inversores para que le dejasen 400.000$ con los que desarrollar un motor de agua, pero lo que hizo fue gastárselos en ponerse una fuente en su casa y financiar la tarjeta de crédito de su hija de 12 años.</li>
<li><a href="http://creatucamino.com/blog/2010/09/02/%C2%BFquien-era-john-kanzius-como-transformar-agua-salada-en-energia-libre/"><b>John Kanzius</b></a> EEUU 2007. Estaba buscando un remedio contra el cáncer cuando descubrió que si se irradia una muestra de agua con una cantidad brutal de ondas de radio, algunas moléculas de agua se rompen y el hidrógeno y el oxígeno se vuelven a recombinar, formando una llama. La idea básica no es demasiado original, inyecta mucha enegía de alguna forma en el agua y acabará saliendo algo de energía en otra forma.</li>
<li><a href="http://newsinfo.inquirer.net/inquirerheadlines/nation/view/20081220-179008/Inventor-82-gets-20-years-for-estafa"><b>Daniel Dingel</b></a>, Filipinas 2008, cuando le mandaron a la cárcel por estafar 380.000$ dijo que le quitasen lo bailado (tenía 82 años).</li>
<li><a href="http://www.elakiri.com/forum/archive/index.php/t-113937.html"><b>Mohotti Arachchilage Thushara Priyamal Edirisinghe</b></a>, Sri Lanka 2008, estafador profesional que engañó a un montón de incautos, y a uno de ellos le quitó más o menos 1.104.693,72 rupias.</li>
<li><a href="http://orcosalvaje.blogspot.com/2008/05/el-motor-de-agua.html"><b>Tareq Abu-Hamed</b></a>, Universidad de Minnesota 2008, sigue investigando lo del boro, ver más abajo.</li>
<li><a href="http://www.motordehidrogeno.net/genepax-el-motor-japones-que-funciona-solo-con-agua"><b>Genepax</b></a> Japón 2008, ya han construido un coche de demostración, pero les está costando encontrar inversores, quizás porque no explican cómo funciona.</li>
<li><a href="http://starviewer.wordpress.com/2010/01/08/el-motor-de-agua-ya-es-una-realidad-sale-a-la-luz-la-patente-internacional-en-2009/"><b>Stone Charles Luther</b></a> Europa 2009.</li>
<li><a href="http://www.emporda.info/catalunya/2010/03/24/motors-que-funcionen-aigua-no-contaminen-estalvien-benzina/72247.html"><b>Jordi Freixas</b></a> Mataró 2010. Añade agua al combustible para mejorar el rendimiento del motor, con lo que recuerda al <a href="http://www.rexresearch.com/chambrin/chambrin.htm">motor de Chambrin</a>; lo de "motor de agua" lo dice el periodista porque tiene que usar un títular corto, y así vamos creando leyendas.</li>
<li><a href="http://english.cntv.cn/program/newsupdate/20110302/104225.shtml"><b>Masahide Ichikawa</b></a> Japón 2011, ha inventado una motocicleta que funciona con agua de mar. Supuestamente usa un calentador de energía solar para evaporar el agua, con lo que se deposita sodio metálico, y al mezclarlo con agua se genera hidrógeno.</li>
<li><a href="http://en.wikipedia.org/wiki/List_of_water_fuel_inventions">Otros nueve inventores</a> de rarezas sobre agua y energía. También está la <a href="http://es.wikipedia.org/wiki/Sonoluminiscencia">sonoluminiscencia</a>, pero, como siempre, se inyecta más energía en los ultrasonidos que la que sale en forma de luz ultravioleta.</li>
</ul><p>Ya me he cansado. Pero de verdad, creo que no exagero cuando digo "cientos".</p><p>Mención aparte merece Arturo Estévez Varela, el "inventor en España" del motor de agua, en 1971. La verdad es que, tras haberle visto en videos, me cae bien este extremeño, porque no engañó demasiado a nadie; por ejemplo, explicaba que su invento no era un motor de agua, sino un generador de hidrógeno, y que el hidrógeno se usaba luego en un motor de explosión convencional. Hacía sus demostraciones usando una moto y un botijo; primero bebía del botijo para demostrar que contenía agua, luego llenaba con él el depósito de la moto, echaba sus pastillas con el aditivo secreto de forma que todo el mundo le viese echarlas, y hala, a correr. Si después de esto alguien insistía en pensar que aquello era un motor de agua, pues allá él.</p><p>No es que Estévez fuese un modelo de transparencia; nunca explicó qué eran esas pastillas negras que echaba en el generador. La opinión generalizada es que era boro, que reacciona con el agua para producir óxido de boro e hidrógeno, con lo cual en vez de motor de agua lo que habría inventado sería, si acaso, un motor de boro. No es que esto sea malo, el problema es que el motor de boro no puede competir con los motores de gasolina por las siguientes razones:</p><ol><li><b>El precio del boro</b>. Cito de <a href="http://www.lamentiraestaahifuera.com/2010/01/07/el-absurdo-motor-de-agua/">http://www.lamentiraestaahifuera.com/2010/01/07/el-absurdo-motor-de-agua/</a>: <em>"El problema es que se necesitan 45 litros de agua y 19 kg de boro para producir 5 kg de hidrógeno que proporcionarían una autonomía semejante a la de un tanque de 40 litros de gasolina o gasoil. El precio de esos 19 kilos de boro rondaría los 95.000$ (unos 68.000€) mientras que el equivalente en gasoil sería unos 40€"</em>. En realidad se puede encontrar boro en diversas formas. Imaginemos que el generador de hidrógeno pudiese funcionar con boro amorfo (pero esto lo digo yo, porque Estévez usaba pastillas negras en vez de polvo marrón, y vista la diferencia de precio debía de tener una buena razón). El caso es que el kilo de boro amorfo se puede conseguir por 1,40€ si compras un mínimo de 20 toneladas; así que en vez de importar dos litros de petróleo que cuestan unos 0,34€ cada uno en origen (el resto son impuestos), pasaríamos a importar un kilo de boro que cuesta 1,40€ en origen. Pues vaya.</li>
<li><b>La contaminación</b>. El óxido de boro contamina bastante más que la gasolina <a href="http://nepis.epa.gov/Exe/ZyNET.exe/91004YZ9.TXT?ZyActionD=ZyDocument&Client=EPA&Index=Prior+to+1976&Docs=&Query=APTD6931&Time=&EndTime=&SearchMethod=1&TocRestrict=n&Toc=&TocEntry=&QField=pubnumber%5E%22APTD6931%22&QFieldYear=&QFieldMonth=&QFieldDay=&UseQField=pubnumber&IntQFieldOp=1&ExtQFieldOp=1&XmlQuery=&File=D%3A%5Czyfiles%5CIndex%20Data%5C70thru75%5CTxt%5C00000008%5C91004YZ9.txt&User=ANONYMOUS&Password=anonymous&SortMethod=h%7C-&MaximumDocuments=10&FuzzyDegree=0&ImageQuality=r75g8/r75g8/x150y150g16/i425&Display=p%7Cf&DefSeekPage=x&SearchBack=ZyActionL&Back=ZyActionS&BackDesc=Results%20page&MaximumPages=1&ZyEntry=1&SeekPage=x&ZyPURL">1</a> <a href="http://www.npi.gov.au/substances/boron/index.html">2</a>; el problema es que forma ácido bórico, un conocido insecticida. Actualmente dedicamos un 45% de todo el petróleo a producir gasolina; eso son 5.700 millones de litros al día, que podíamos sustituir por unos 11 millones de toneladas de boro al día, que producirían unos 35 millones de toneladas de óxido de boro al día.</li>
<li><b>Las reservas mundiales de boro</b> son 10 millones de toneladas, así que nuestros coches podrían funcionar durante un día antes de acabar con todo el boro del planeta.</li>
<li><b>El coste energético de producir boro</b> es mayor que la energía que libera. Además, la mayor parte de la energía se convierte en calor al oxidarse el boro, al motor llega menos de la mitad de la energía.</li>
</ol><p>Así pues, usar boro en vez de gasolina no es rentable ni económica ni energética ni medioambientalmente; además, es inviable e insostenible, no hay suficiente boro. Si hiciese falta buscaríamos más depósitos de bórax, pero suele ocurrir que la extracción en minas pequeñas es más cara que en las minas grandes (las que explotamos ahora). Y podríamos encontrar formas de reciclar el óxido de boro para producir boro, pero cualquier procedimiento que haga esto gastará al menos tanta energía como la que se produce al oxidar el boro; ¿de dónde sacaríamos esta energía? De hecho, si tuviésemos esta energía, probablemente sería más eficiente usarla en coches eléctricos. <a href="http://www.rexresearch.com/chambrin/chambrin.htm">Aquí</a> explican por qué hacerlo con aluminio y galio sería mejor que con boro, aunque tampoco esto funciona.</p><p>Muchas páginas conspiranoicas dicen que don Arturo "desapareció sin dejar el menor rastro", pero en la primera página de resultados de google se encuentra un video de uno de sus hijos explicando que murió con 82 años. Parece ser que fue el mismo Franco quien, tras un estudio del Colegio de Ingenieros Industriales, le dijo a Estévez que dejase de hablar del asunto, porque "ya se había hecho bastante el ridículo". Estévez, que venía de una familia de posibles pero se había gastado nueve millones de pesetas de la época en su invento sin que nadie le hiciera mucho caso, desapareció de la vida pública. A lo largo de su vida registró unas 100 patentes, pero ninguna de ellas estaba relacionada con el invento que le hizo famoso.</><br />
<p><b>Tercera sorpresa</b>, los conspiranoicos no tienen ni idea de lo que es una <a href="http://es.wikipedia.org/wiki/Patente">patente</a>:</p><ul><li>Las patentes, como su propio nombre indica, son documentos públicos; es decir, si está patentado no es secreto, y si es secreto no está patentado. Por ejemplo, he aquí las patentes de Meyer: <a href="http://www.google.com/patents/about?id=GNQfAAAAEBAJ&dq=5149407">5149407</a>, <a href="http://www.google.com/patents/about?id=lLcjAAAAEBAJ&dq=4936961">4936961</a>, <a href="http://www.google.com/patents/about?id=79Y9AAAAEBAJ&dq=4826581">4826581</a>, <a href="http://www.google.com/patents/about?id=xhczAAAAEBAJ&dq=4798661">4798661</a>, <a href="http://www.google.com/patents/about?id=evQ6AAAAEBAJ&dq=4613779">4613779</a>, <a href="http://www.google.com/patents/about?id=Dz86AAAAEBAJ&dq=4613304">4613304</a>, <a href="http://www.google.com/patents/about?id=fqt1AAAAEBAJ&dq=4465455">4465455</a>, <a href="http://www.google.com/patents/about?id=gz0wAAAAEBAJ&dq=4421474">4421474</a>, <a href="http://www.google.com/patents/about?id=ihY9AAAAEBAJ&dq=4389981">4389981</a>; todas ellas son variantes cada vez más enrevesadas de la idea de separar el agua en hidrógeno y oxígeno por electrólisis, y luego volver a juntarlos para obtener energía, así que no valen nada, pero supuestamente hay gente capaz de matar para ocultar estos documentos.</li>
<li>Las patentes caducan al cabo de 20 años; a partir de entonces, todo el mundo puede hacer lo que quiera con ese invento.</li>
<li>Se puede patentar una idea, sin tener que construir nada ni demostrar que funciona. Es decir, el que algo esté patentado no quiere decir que funcione.</li>
<li>El que un invento tenga una patente vigente no quiere decir que no puedas hacerte uno en casa para investigar; simplemente quiere decir que si vas a explotarlo comercialmente tienes que ponerte de acuerdo con el inventor.</li>
<li>Hay oficinas de patentes que aceptan todo sin leerlo. Si quieres patentar algo impatentable, bien porque es la <a href="http://www.newscientist.com/article/dn965-wheel-patented-in-australia.html">rueda</a> y no la has inventado tú, o bien porque es algo tan ridículo como <a href="http://www.google.com/patents/about?id=T2QKAAAAEBAJ&dq=6368227">la forma de balancearse en un columpio</a>, lo único que tienes que hacer es ir a la oficina de patentes adecuada.</li>
</ul><p>Cualquier persona que diga algo del tipo de "los malos compraron la patente y la escondieron" refiriéndose a algo que ocurrió antes de 1990 no está haciendo un gran esfuerzo por ser objetivo: las patentes no se pueden ocultar, así que cualquiera puede ir a la oficina de patentes más cercana y pedir una copia de la patente, que podrá usar libremente porque ya han pasado los 20 años (ojo, tendrá que darle datos suficientes a los trabajadores de la oficina, decirles "busco un invento fabuloso" no será suficiente).</p><p>Para acabar, mencionaré mis razones para pensar que nunca ha existido un motor de agua:</p><ul><li>Si empiezas con agua y acabas con agua, los principios de la termodinámica aseguran que no puedes obtener energía. Un motor que usase sólo agua y acabase produciendo agua sería un móvil perpetuo.</li>
<li>Si fuese posible lo sabríamos; ¿alguien se cree que algo tan sencillo que supuestamente ya se hacía en el siglo XVIII se pueda guardar en secreto en los tiempos de Wikileaks? Por un lado nos dicen que hay personas redescubriendo el motor de agua cada año, pero por otro lado ninguno de estos genios sabe manejarse en Internet.</li>
<li>Hay bacterias que viven de extraer energía de reacciones químicas realmente exóticas, pero todavía no ha aparecido una bacteria que extraiga energía simplemente del agua. Quizás la única forma de hacerlo es usar el hidrógeno en un reactor de fusión.</a><br />
<li>¿Cómo es posible que haya asociaciones ecologistas como Greenpeace que se dedican a chinchar todo lo que pueden a las empresas petroleras, y sin embargo no se ocupan de resucitar el motor de agua?</li><br />
<br />
<li>Si las malvadas empresas petroleras se estuviesen tomando tantas molestias para ocultar el motor de agua, ¿cómo es que han dejado que el 21% de la energía generada en España sea eólica y el 5% fotovoltaica? ¿A lo mejor no saben que los coches eléctricos se podrán recargar con energía eólica? ¿Cómo se explica que los países comunistas tampoco tengan sus motores de agua?</li><br />
<br />
<ul><br />
<br />
Santiago Egido Arteagahttp://www.blogger.com/profile/14137066752624247290noreply@blogger.com4