1595.- Problem(it)a: encuesta paradójica - CdM IX

[si no fuera por el Carnaval, no se si estos últimos meses hubiese posteado algo... Por cuestiones de tiempo, el blog entró en una lenta agonía pero no encuentro la forma menos dolorosa de sacrificarlo, veré qué pasa el año próximo.]

El siguiente problem(it)a, cuyo origen prefiero esconder así uno lo medita un rato, mezcla resultados de la teoría de la medida con otros de la teoría de elecciones (como el de Arrow al que hacía referencia en el post anterior).

Supongamos que N personas están formados en una fila para votar por Xérez o Yérez, ganará el que saque más votos, y varios encuestadores se acercan a preguntarles por su intención de voto.

Ahora:

i.- cada encuestador consulta un "segmento" de personas: elige una, y le va preguntando consecutivamente a todas hasta que para en alguna otra; distintos encuestadores se pueden "superponer" y preguntarle a las mismas personas.

ii.- todas son encuestadas al menos una vez, y dicen la verdad.

Supongamos que los encuestadores se juntan y comparan sus porcentajes de votos (pero no revelan a quiénes les preguntaron):

1.- Si cada encuestador obtuvo que el candidato Xérez saca más de la mitad de los votos de las personas que encuestó, ¿alcanza para afirmar que gana Xérez?

2.- ¿Cuál es el porcentaje mínimo que debería tener Xérez en cada encuesta para poder afirmar que gana?

* * *

Bien: 1 es fácil, 2 no tanto. No hago comentarios para no revelar la solución.

Para el Carnaval, esta vez en la trébede.

1573.- Fronteras - Carnaval V

Una de las tantas propagandas sobre el Mundial de Sudáfrica muestra uno de los pocos ejemplos de un país completamente ubicado dentro de otro (tampoco se termina ahí la lista, ¿se anima a nombrar otros?, descontando las embajadas, que sería una solución trivial).

¿Qué se puede decir de las fronteras de los países? Consideramos en los mapas que cada país define un conjunto, y la frontera de estos países/conjuntos serían sus costas y sus fronteras con otros países. Un repaso rápido nos muestra que la geografía real es bastante pobre, comparada con las posibilidades matemáticas:

todo punto frontera de Lesotho está incluído en la frontera de Sudáfrica.

Argentina, Paraguay, y Brasil (aparte de comerse a los rivales crudos) tienen la (in)famosa triple frontera, punto donde convergen no sólo los tres países sino otras cosas de las que mejor no hablar.

Las triples fronteras son sencillas, casi toda terna de tres países tales que dos cualesquiera comparten fronteras entre sí, tienen una. Pero hay excepciones, ¿alguna que conozcan? (ayuda: tres países que están con un pie afuera del mundial)

Andorra, Francia y España comparten dos triples fronteras. Y es que Andorra queda ensanguchada entre los otros dos. ¿Otros?

Colorado, New Mexico, Arizona y Utah comparten el Four Corners: turismo fácil generado a partir de un meridiano y un paralelo que se cruzan para formar la frontera entre los estados.

Zimbabwe, Namibia, Zambia y Botswana también tienen su Four Corners. ¿Conocen alguno más? (yo no)

Y a poco que uno empieza a pensar en esto, nada impide que tres países tengan tres triples fronteras. El hecho que vivamos en una esfera nos complica la vida para analizar el problema teóricamente, uno no está acostumbrado a imaginarlo. ¿Pero se puede lograr eso en un mapa plano? Agreguemos, acá, una condición importante: los tres países deben ser conexos, puedo ir de un punto a otro del país sin tener que utilizar pasaporte (Alemania Occidental con su medio Berlín antes de la unificación era un ejemplo de país disconexo).

* * *

Y, por último, en el plano, ¿podemos imaginar tres países tales que su triple frontera sea todo un segmento o una curva continua?

Vi este problema por primera vez hará más de 20 años, pero recién hace unos meses
encontré una solución explícita trivial.

Debería sugerir una pista, porque me la voy a olvidar, aunque sea sin un x para que no les sea tan inmediato, pero mejor no la sugiero... epa, ya lo hice!

Hasta el próximo carnaval, nos vemos esta vez en ciencia, y aquí

1572.- Problem(it)a

Sean dos animales esféricos, de radios r y R, con R mucho menor que r ;).

¿Cuál se desplaza más rápido en terreno llano?

¿Cuál se desplaza más rápido en terreno montañoso? (hacia arriba, hacia abajo dicen que Galileo dijo que caen a la misma velocidad)

¿Cuál duerme más horas?

Estos problemitas están en el genial Mathematical Methods of Classical Mechanics de Arnold.

* * *

Aprovecho para repetir un viejo post:

480.- POKER DE ASES

'Cuando comparé a A. N. Kolmogorov con un alpinista que era el primero en ascender difíciles cumbres, en contraste con I. M. Gelfand, cuyo trabajo comparé con la construcción de autopistas, ambos se me ofendieron...

"Por qué? Usted piensa que no soy capaz de construir teorías generales?" me dijo Andrei Nikolaievich. "Por qué? Piensa que no soy capaz de resolver problemas difíciles?", agregó I. M.'

V. I. Arnold, en Kolmogorov in perspective.

Cada país puede presentar sus cuatro mejores matemáticos del siglo XX. Estos tres rusos juntos, les ganan.

1569.- Carnaval IV - Problem(it)a

Imaginen dos barcos de guerra, enemigos, buscándose en el océano. Imaginen que uno de los capitanes (digamos, Xérez) tiene un espía en un puerto neutral, y le pagará 1 dolar por cada dato útil que reciba sobre el otro barco.

Imaginen, ahora, que el otro capitán (sea Yérez) se comunica con un espía que tiene en el mismo puerto y le dice:

-Te pago 1 dolar por cada dato útil que tengas sobre el otro barco. Es urgente, porque tengo el radar roto.

Imaginen, por último, que Xérez y Yérez, sin saberlo, confiaron en el mismo espía.

* * *

¿Cuánto es el máximo que puede ganar el espía con estos capitanes?

* * *

Imaginen la situación durante un minuto, el primer minuto de Everybody Knows, de Leonard Cohen, si quieren. Tal vez les sugiera la respuesta.




* * *

No es difícil imaginar cómo actuará el espía para hacer fortuna:

Le avisa a Xérez que el radar de Yérez no funciona.

y luego

Le avisa a Yérez que Xérez sabe que el radar de Yérez no funciona.

y luego

Le avisa a Xérez que Yérez sabe que Xérez sabe que el radar de Yérez no funciona.

y luego...

* * *

La idea detrás de este problem(it)a es la de conocimiento común, una genialidad de Robert Aumann en los '70, y una de las razones por las cuales le dieron el Nobel.

De hecho, el conocimiento común es clave para su teorema conocido como "agreeing to disagree":

Si dos personas tienen la misma distribución de probabilidad a priori, y las consecuencias de un evento A son conocimiento común, tendrán la misma distribución de probabilidad a posteriori.

* * *

En fayerwayer posteaban el año pasado diez preguntas para trabajar en Google, y la segunda es un problema basado en la idea de conocimiento común. Cambiando 100 por cualquier otro número, se ve que no alcanza con k iteraciones en el "sabe que sabe que sabe...".

El problema inicial es de S Ambroszkiewicz.

Este post va de cabeza a la 4ta edición del Carnaval Matemático, ahora en manos de Zurditorium.

1556.- Problem(it)a

Tenemos n números reales s₁, s₂, ..., s_n tales que todas las sumas

 \sum _{i} s_i, \quad \sum_{i \lt j}s_is_j, \quad  ..., \quad s_1s_2\cdots s_n

son positivas.

Entonces, los s_i son todos positivos.

1542.- Omerta

(vamos, carajo!! estoy volviendo: recién iba a poner negritas, y en vez del código html usual, apelé al téxico \textbf{})

* * *

(mmm... y ahora empecé \begin{center} antes de darme cuenta... tampoco es cuestión de no postear culpa de eso!!)

* * *

Ejercicio: analice el Dilema del Prisionero en el caso de que (al menos) uno de ellos pertenezca a la mafia^(*).

* * *

Por si no conoce el DdelP, dos ciudadanos son detenidos y aislados hasta confesar un crimen e incriminar al otro. Si no lo hacen, van presos 3 años c/u. Si los dos lo hacen, van presos 10 años c/u. Si uno lo hace y el otro no, el que habla sale libre y el otro va 15 años preso.

* * *

Omerta viene, créase o no, de hombredad, prudentemente reemplazada en nuestro idioma por hombría.

* * *

(*) Por si hace falta aclararlo, la Omerta es la prohibición categórica^(**) de cooperar con las autoridades policiales, aún habiendo sido víctima de un crimen.

* * *

(**) Con flechas y todo!

* * *

Ejercicio avanzado: en una población de N personas, pN son de la mafia (p entre 0 y 1). La policía elige un par al azar y juegan al DdelP. ¿Cómo se comporta el porcentaje de mafiosos después de k juegos? (suponga que se realizan antes de que nadie quede libre)

(si alguien quiere prenderse, escribimos algo)

1512.- Problem(it)a

Uno fácil: 20km de vía, un riel de 20001 m. ¿Cuánto se levantará si lo hacemos calzar 'a presión' entre los dos extremos de la vía?



(mentalmente, claro, y con tres o cuatro cifras significativas)

1478.- Problem(it)a

Difícil, dado que google no tiene indexado el paper...

¿Quién (cuándo, dónde) publicó un trabajo titulado My group?

1473.- Atrapar al conejo

Un conejo está parado en el lado positivo del eje x, en el número A. Un cazador está parado en el número B del eje y. Se descubren mutuamente, y comienza la cacería. Si el conejo se aleja siempre sobre el eje x a velocidad v, y el cazador se dirige siempre hacia él a velocidad w...



...sí, ya se: si w es mayor que v lo atrapa y se puede calcular cuándo y donde. Ni cuentas hacen falta: otro cazador que vaya de B al origen, y luego camine por el eje x lo alcanza seguro, con más razón este que tiende a optimizar las cosas.

* * *

La cosa se pone interesante si v = w. Ahora está claro que no lo puede alcanzar. Pero:

a.- ¿Qué pasa con las distancias entre el cazador y el conejo? En lo posible, sin hacer cuentas, intuitivamente (con ecuaciones diferenciales se calcula al toque).

b.- ¿Cuál es la distancia límite? Es decir, a medida que pasa el tiempo, ¿qué distancia los separa al cazador y el conejo? (al principio, era raíz de A² + B²)

1464.- Para lelos

Un cazador cree ver un oso. Camina diez pasos hacia el sur, apuntando en esa dirección con una escopeta. Como no lo ve, gira y camina diez pasos hacia el oeste, con su escopeta descansando en el antebrazo izquierdo (sigue apuntando al sur). Frena, y camina diez pasos hacia el norte, con su escopeta en el hombro apuntando hacia atrás. Dado que regresó al mismo punto del que había partido, si el oso estuviera en el punto donde creía haberlo visto al principio, ¿puede matarlo aprentando el gatillo?

1449.- Problem(it)a

Este lo saqué de un paper reciente del arxiv: se divide una pizza radialmente en N porciones no necesariamente iguales (N es par). Dos personas se sirven alternadamente, pero salvo para la 1ra porción, que puede elegirse libremente, sólo pueden retirar una porción adyacente a un lugar vacío. ¿Es cierto que el 1er jugador tiene una estrategia que le garantiza morfarse al menos media pizza?

* * *

i.- Si N es impar, el primer jugador puede asegurarse al menos 1/3 de la pizza.

ii.- Es el segundo caso que conozco de una estrategia ganadora casi paradójica.

1448.- Problem(it)a

Una madre es 21 años mayor que su hijo. En 6 años el niño será 5 veces menor que su madre.

¿Dónde está el padre?

(éste pidió permanecer en el anonimato, a ver si afecta su próximo concurso por un cargo, pero va con mi agradecimiento a todos los que me mandan cosas por mail! sigan así el año próximo!)

1436.- Problem(it)a

Para resolver mentalmente, mientras prepara el asadito del domingo. Sume:



Y hasta le puede calcular el límite cuando N tiende a infinito, sin mucho esfuerzo, le digo.

1408.- Problem(it)a

Uno fácil, facilísimo. ¡Qué digo facilísimo: trivial, una boludez! Hallar los próximos términos de

3, 13, 1113, 3113, 132113, 1113122113, 311311222113,...

Es tan simple, entre otras cosas, porque podemos guglear para ver la respuesta si no sabemos cómo se genera la sucesión.

* * *

Esta sucesión tiene nombre propio, el de uno de los grandes matemáticos del siglo XX (que sigue vivo) y hay una parte curiosa en la historia, que dejo para otro post: cuando uno de sus alumnos se la propuso, él no supo resolverla.

1381.- Ayudita y pseudodesagravio

El problemita del cubo con los vértices blanco me gustó bastante, así que casi voy a postear la solución:

Supongamos que elegimos una carta del mazo, y tenemos los siguientes eventos:

A = {la carta es de copas} B = {la carta es un rey}

Entonces, si nos interesa el evento C = {rey de copas},

P(C) = P(AB)= 1/40 = 1/4 x 1/10 = P(A) x P(B)

En el problema de los vértices de un cubo, ubicar uno al azar y que no sea blanco tiene probabilidad 1/10. Claro, la ubicación del segundo vértice no resulta independiente de la ubicación del primero...

1379.- Problem(it)a

Tengo una esfera y el 90% de su superficie es blanca (el 10% restante es verde, o azul, o rojo, o amarillo,... pero no todos a la vez o sería también blanco). ¿Siempre podré inscribir un cubo en ella tal que todos sus vértices se apoyen en un punto blanco?

* * *

Pasando a otra clase de problemas, más graves, y probablemente sin solución, Craig linkea esta advertencia de la Universidad de Manchester. La frase "While the University does not wish to bar access to and use of such sites..." me pone los pelos de punta (¿se olvidaron de los foros?, dicho sea de paso), y me suena a una toma de partido por parte de una universidad en situaciones como la del post anterior.

1362.- Problem(it)a

¿Cuál será el máximo número de cuadraditos de lado 1 que se pueden meter dentro de un círculo de radio 100 sin que se salgan ni se superpongan?

cuánto hace que no ponía un problem(it)a! Se escuchan soluciones, especialmente aquellas ingeniosas y raras, aunque no sean necesariamente correctas.

691.- Descubra el número

Hace mucho que no posteaba un problem(it)a! Vamos con uno clásico de Stanislaw Ulam:

Una persona piensa un número del 1 al 1.000.000, y otra debe adivinarlo haciendo preguntas que se contesten por si o por no. ¿Cuántas preguntas necesita?

Si la persona que eligió el número puede mentir una vez, ¿cuántas preguntas hacen falta?