25.10.14

Variaciones sobre una cáscara de banana

(Éste es el resumen de mi charla en el 5to. Encuentro para Celebrar el Ingenio de Martin Gardner y Jaime Poniachik.)

..............
Adenda del 8/11/14: Conjeturo que la suma máxima en el cuadrado de $n\times n$ es aproximadamente igual a $\frac{n^3}{2}$. Predigo en consecuencia que para 8x8 la suma máxima es aproximadamente igual a 256.
..............

En el movimiento cáscara de banana (1) una pieza resbala (hacia arriba, hacia abajo, hacia la derecha o hacia la izquierda) tanto como le sea posible, es decir, hasta que llega al borde del tablero o hasta que choca contra una casilla anulada. En el primer desafío elegimos una casilla inicial cualquiera, colocamos una pieza y marcamos allí un 0 (las casillas donde anotamos números se convierten en anuladas). A continuación, comenzamos a mover la pieza anotando, cada vez, en la casilla de llegada cuál ha sido la distancia recorrida. Por ejemplo:
Así seguimos hasta que la ficha ya no se puede mover. Para tableros de 3x3, 4x4, 5x5,… hay que lograr:

1) Que al trabarse el movimiento, la suma de los números sea la MENOR posible.
2) Que se complete el tablero y que a la vez la suma sea la MENOR posible.
3) Que se complete el tablero y que a la vez la suma sea la MAYOR posible.

Como segundo desafío transformamos este mecanismo en un juego para dos jugadores, digamos Alicia y Bruno. Alicia juega primero y elige una casilla inicial cualquiera (que queda anulada), luego Bruno desplaza la ficha y la casilla final queda igualmente anulada; así siguen hasta que el juego se traba. Quien haya hecho la última jugada, gana. Para tableros de 3x3, 4x4, 5x5,… la pregunta es: ¿Cuál de los dos jugadores tiene una estrategia ganadora? También podemos preguntarnos qué sucede en la versión de “el último que juega pierde”.

Nota:
(1) No sé si el mecanismo, pero sí su nombre, hasta donde conozco, se debe a Jaime Poniachik. [Según comentó Pablo Milrud en el propio encuentro, el mecanismo "cáscara de banana" -y tal vez también el nombre- serían en realidad creaciones de Iván Skvarca.]

Resumen de las soluciones recibidas hasta ahora (véanse más abajo los detalles):
Para la pregunta 1) la respuesta es 5 independientemente del tamaño del tablero, siempre que sea mayor que 2 (respuesta enviada por Rodolfo Kurchan).

Para las preguntas 2) y 3):
3x3: Mín = 12, Máx = 12. (Rodolfo Kurchan)
4x4: Mín = 23, Máx = 30. (Rodolfo Kurchan)
5x5: Mín = 41, Máx = 61. (Marcos Donnantuoni)
6x6: Mín = 68, Máx = 107. (Marcos Donnantuoni)
7x7: Mín = 102, Máx = 172. (Marcos Donnantuoni)

Para el juego de dos, Rodolfo demostró que en tableros de 3x3 y 5x5 gana el primero.

Detalles:
(26/10/14) Pocas horas después del evento, Rodolfo Kurchan envió estas soluciones:
Para la pregunta 1 me parece que para cualquier tablero de lado nxn (salvo 2x2 que es muy chico) se traba con suma 5:

.0.
11.
12.

Ésta es la "punta" de cualquier tablero, va de 0 a 2, al 1 de arriba, al 1 de la izquierda y al 1 de abajo.

Para las preguntas 2 y 3:
3x3 mínimo 12, máximo 12
4x4 mínimo 23, máximo 30

1131        0313
2011        2113
1113        3221 
3211        3113

Para el juego:
Tablero de 3x3 y 5X5 gana el primero

...
.12
453

76...
OX...
891..
453..
..2..

X es la jugada 10 y O es la jugada 11 (si el segundo jugador luego de A5 va para abajo pierde en 7 movidas en lugar de en 11.

(29/10/14) Marcos Donnantuoni envía estas soluciones (aclara que sin garantía de que sean óptimas):
5x5 min
41
← ↑ ↓ → ↑ ← ↓ → ↑ ← ↓ → ← ↑ → ↓ ← ↓ → ↑ → ← ↑ ↓ 
2     3     1     1     1     
1     1     2     2     4     
1     0     1     2     1     
4     1     1     2     1     
1     1     4     1     2     

5x5 max
61
↑ ← ↓ → ← → ↑ ↓ ← ↑ → ↓ ← → ↑ ← ↑ → ↓ ↑ ↓ ↑ ← ↓ 
4     1     1     4     3     
2     2     3     1     4     
4     1     1     3     1     
3     1     2     3     0     
4     3     4     2     4     

6x6 min
68
→ ↑ ↓ ↑ ← ↑ → ↓ ↑ ← ↑ → ← ↓ → ↑ ← ↓ → ↑ ← ↓ → ← ↓ → ↓ ← ↑ ← ↑ → ↓ ← ↓ 
1     1     1     2     4     3     
5     3     3     1     1     1     
1     3     1     1     2     2     
1     2     1     3     0     1     
5     1     1     1     3     1     
1     1     5     1     1     3   

6x6 max
107
↓ ← → ↑ ← ↓ → ↑ ← → ↓ ↑ → ↓ ← → ← ↑ → ↓ ↑ ↓ ← ↓ → ↑ ↓ ↑ ↓ → ↑ ← → ← ↑ 
4     3     5     2     5     0     
5     1     3     4     4     3     
3     1     2     1     2     1     
5     3     2     1     4     1     
4     2     4     3     3     5     
5     1     1     5     4     5     

7x7 min
102                                                                             
↓ → ← ↑ → ↓ ← ↑ → ↓ ↑ ↓ ← ↓ ↑ ↓ → ↓ ← → ↑ ← ↓ ↑ → ↑ ← ↓ → ← ↑ → ↓ ← ↑ ↓ ↑ → ← ↓ ← ↑ → ↑ ↓ → ← ↑                                                                      
2       3       6       1       1       6       1                                                                                                                    
1       1       1       2       4       4       1                                                                                                                    
2       2       2       1       2       1       2                                                                                                                    
6       4       1       1       2       1       1                                                                                                                    
2       1       1       4       1       2       3                                                                                                                    
1       1       4       3       0       1       5                                                                                                                    
3       2       1       1       1       1       2   

7x7 max
172                                                                             
← ↓ ↑ → ↓ ← ↑ → ↓ ↑ ↓ ← ↑ → ↓ ↑ ← ↓ → ← ↑ → ↓ ← ↑ → ← ↓ ↑ ↓ ← → ↑ ↓ → ↑ ← ↓ → ← ↑ → ↓ ↑ ↓ ← ↑ ↓                                                                      
6       6       6       1       2       4       0                                                                                                                    
5       3       4       5       3       5       6                                                                                                                    
3       4       1       2       2       2       6                                                                                                                    
6       1       3       1       2       4       2                                                                                                                    
1       5       3       1       1       3       6                                                                                                                    
5       2       1       4       3       4       3                                                                                                                    

6       5       2       6       5       6       5      

16.10.14

Axiomas de Peano y consecuencias (5) con algunos comentarios sobre el teorema de Gödel

(Para ver todas las entradas de esta serie hágase clic aquí.)
A la parte 4 - A la parte 6

Nota: desde que publiqué por primera este entrada he ido modificando ligeramente su contenido buscando que converja a lo que quiero expresar.

Desde hace algún tiempo venimos mostrando algunos teoremas que se deducen de los axiomas de Peano. En las entradas previas hemos demostrado, por ejemplo, que la suma de números naturales es asociativa y conmutativa, y que el 0 es su neutro. También probamos que el producto es asociativo y conmutativo, y que el 1 (definido como S(0)) es su neutro. Veremos ahora algunos teoremas más, que tendrán esta vez, además, cierta relación con el teorema de Gödel. Para comenzar, recordemos dos de los axiomas de Peano:

Axioma 1: Para todo n, $S(n)\neq 0$.
Axioma 2: Si S(n) = S(m) entonces n = m.

Veamos ahora un nuevo teorema:

Teorema 13: Si $n\neq 0$ entonces existe m tal que S(m) = n.
Demostración:
El enunciado que queremos demostrar equivale a $\forall n (n=0 \vee \exists m(S(m)=n))$, y este último enunciado se prueba fácilmente por inducción. En efecto, para n = 0 vale, y supuesto que vale para n entonces es claro que también vale para S(n) ya que si n = S(m) entonces S(n) = SS(m).

Teorema 13 bis: Si $n\neq 0$ entonces n se obtiene aplicando al 0 la función S sucesivamente una cantidad finita de veces.
Demostración:
Por inducción. Para n = 0 vale (el antecedente de la implicación es falso). Supuesto que vale para n es inmediato que vale para S(n) ya que si n = SS...S(0) entonces S(n) = SSS...S(0) (una S más).

Teorema 13 ter: Si una afirmación vale para 0, S(0), SS(0), SSS(0), SSSS(0),... entonces la afirmación vale para todo n.
Demostración:
Sea n cualquiera, entonces, por el teorema anterior, o bien n = 0, o bien n = SS...S(0), en cualquiera de los dos casos, por hipótesis, la afirmación vale para n.

¿Cree usted que los tres teoremas son válidos?

Sucede que el enunciado y la demostración del primer teorema respetan las restricciones que impone la lógica de primer orden, mientras que los otros dos no las respetan (se enmarcan en la lógica de segundo orden). ¿Es importante esta distinción? En parte sí, porque el teorema de Gödel sólo vale en teorías basadas en la lógica de primer orden. De hecho, si se acepta la validez del teorema "13 ter" entonces el teorema de Gödel pasa a ser directamente falso (o, si se quiere, es falso si se acepta en la matemática ese tipo de razonamiento). Por así decirlo, la validez del teorema de Gödel termina en la delgada línea que separa el teorema 13 del teorema 13 bis. Vuelvo a preguntar: ¿cree usted que los tres teoremas son válidos?

Una primera conclusión es (o debería ser) que el teorema de Gödel involucra ciertas sutilezas que impiden que sea discutido a la ligera, y que refutan cualquier análisis que no tome en cuenta adecuadamente sus complejidades técnicas.

Por otra pare, yo sí creo que los tres teoremas son válidos, por lo que esta situación me convence (al menos a mí) de que la lógica que usan naturalmente los matemáticos no es (a diferencia de los que los lógicos suelen sostener) la lógica de primer orden, sino la lógica de segundo orden. La "verdadera lógica", digo yo, es la de segundo orden, la otra es una lógica muy apta para ser estudiada, pero no es la que usamos realmente para razonar.

¿Es falso entonces el teorema de Gödel? No, el teorema de Gódel sigue siendo válido en la teorías basadas en la lógica de primer orden, es decir, tiene una aplicación específica que, según yo lo veo, no alcanza a toda la matemática en su conjunto.

20.8.14

¿Verdadero o falso?


"Si un número entero es negativo entonces ese número es positivo."

"Si 3 es negativo entonces 3 es positivo."

4.8.14

¿Sí o no?


"Si todo triángulo tiene tres lados entonces esta afirmación (la implicación completa) es falsa."

(*) Agregado para evitar ambigüedades.

31.7.14

Una demostración

(Esta entrada ya había sido publicada en el blog en julio de 2013; se la vuelve publicar aquí "remozada".)

Vamos a demostrar a continuación que si p es un número primo que es divisor del producto ab entonces p es divisor de a o es divisor de b. La "originalidad" de esta demostración reside en el hecho de que se basa directamente en el principio del mínimo mientras que la demostración que habitualmente se encuentra en los libros usa el hecho de que si mcd(a,b) = 1 entonces existen s y t tales que as + bt = 1.

(Aunque casi nunca se lo mencione explícitamente, todos los números mencionados son enteros positivos.)

Teorema: Si p es un número primo positivo y $k,a,b\in \mathbb{N}$ son tales que pk = ab entonces p es divisor de a o p es divisor de b.

Demostración: Supongamos que la afirmación es falsa y sea p el menor primo para el cual existen $k,a,b\in \mathbb{N}$ con pk = ab sin que p sea divisor de a ni de b. De todos los valores posibles de k elegimos, a su vez, el menor posible. 

Afirmo que $a < p$ y que $b < p$. En efecto, supongamos que $p < a$ (no pueden se iguales porque p no es divisor de a). Dividimos a por p y obtenemos a = pq + r; como p y q son positivos entonces $r < a$ y además p no es divisor de r (porque no es divisor de a). 

Luego, ab = pqb + rb y en consecuencia p es divisor de rb, existe entonces un k' tal que pk' = rb. Observemos que $pk^\prime = rb < ab = pk$ y entonces $k^\prime < k$ con pk' = rb y además r y b no divisibles por p. Esto contradice la minimalidad de k. El absurdo proviene de suponer que $p < a$, deducimos entonces que $a < p$.

Tenemos entonces que pk = ab con $a < p$ y $b < p$. Nótese que $pk = ab < p^2$, luego $k < p$. Sea $p^\prime $ primo y $n\in \mathbb{N}$ tales que $p^\prime n = k$ (si k resultara ser primo, entonces tomamos $p^\prime =k$ y $n=1$). Luego, $pp^\prime n=ab$. Como $p^\prime \leq k < p$ entonces, por la minimalidad de p, $p^\prime $ es divisor de a o es divisor de b. Podemos suponer que $p^\prime $ es divisor de a, luego, existe t tal que $p^\prime t=a$. Tenemos que:

$pk = ab$
$pp^\prime n = p^\prime tb$
$pn = tb$

Como n es menor que k entonces, por la minimalidad de k, p es divisor de t (y entonces, divisor de a) o bien p es divisor de b. En ambos casos se llega a un absurdo. Esto finaliza la demostración.

Desafío para los lectores: ¿En qué punto de la demostración se usa la hipótesis de que p es primo?

28.7.14

Axiomas de Peano y consecuencias (4)

(Para ver todas las entradas de esta serie hágase clic aquí.)
A la parte 3 - A la parte 5

Definición: 1 = S(0).

Teorema 10: $1\neq 0$.
(Es consecuencia inmediata del axioma 1.)

Teorema 11: n + 1 = S(n).
Demostración:
n + 1 = 
= n + S(0)  (definición)
= S(n + 0)  (Ax. 4)
= S(n)   (Ax. 3)

Teorema 12: 1.n = n.
Demostración:
Por inducción. Para n = 0 vale por el axioma 5. 
Veamos que 1.n = n implica 1.S(n) = S(n).
1.S(n) = 
= 1.n + 1  (Ax. 6)
= n  + 1  (por hipótesis)
= S(n)  (Teo. 11).

Definiciones:
2 = S(1)
3 = S(2)
4 = S(3)
5 = S(4)
etc.

26.7.14

Productoria

1) Si $(a_1,\dots ,a_n)$ es una n-upla de números reales, la productoria $\prod (a_1,\dots ,a_n)$ se define, inductivamente, de esta manera:

Para $n=0$, definimos $\prod ()=1$.
Supuesto definido $\prod (a_1,\dots ,a_n)$, definimos $\prod (a_1,\dots ,a_n,a_{n+1}) = a_{n+1}\cdot \prod (a_1,\dots ,a_n)$.

2) Definimos $b^n=\prod (b,\dots ,b)$, donde b aparece n veces; en particular $b^0=\prod ()=1$. Y más en particular $0^0=\prod ()=1$.

17.6.14

Dos problemas de probabilidad

Problema 1: Una bolsa contiene 17 bolillas, de ellas 8 tienen marcada una letra A y las otras 9, una letra B. De las que tienen la letra A, 6 son rojas y 2 son negras; de las que tienen la letra B, 4 son rojas y 5 son negras. Se extrae una bolilla al azar y se observa que es roja ¿cuál es la probabilidad de que tenga inscripta una letra A?

Problema 2: Tenemos 17 bolillas, de ellas 8 tienen marcada una letra A y las otras 9, una letra B. De las que tienen la letra A, 6 son rojas y 2 son negras; de las que tienen la letra B, 4 son rojas y 5 son negras. Las bolillas que tienen la letra A son colocadas en una bolsa, las que tienen la letra B son colocadas en una bolsa diferente. Luego, se elige al azar una de las dos bolsas y de ella se extrae al azar una bolilla. Se observa que la bolilla extraída es roja ¿cuál es la probabilidad de que tenga inscripta una letra A?

28.4.14

Una ruleta paradójica


Imaginemos una ruleta "continua" capaz de detenerse con precisión absoluta en cualquiera de los infinitos ángulos comprendidos entre 0° y 360°.
Imaginemos también que mientras la ruleta gira al azar el jugador A apuesta $10 a que la flecha se detendrá en un ángulo comprendido entre 0° y 120°. ¿Cuál sería un pago justo para la apuesta de A

Por pago justo entendemos un pago tal que si A repite su apuesta una y otra vez entonces, a la larga, ganará tanto dinero como el que perderá. Ahora bien, dado que el arco de la circunferencia comprendido entre 0° y 120° representa la tercera parte de la circunferencia total, es decir, dado que la medida de ese arco es un tercio de la medida de la circunferencia, entonces la probabilidad de que A gane es 1/3. En otras palabras, A ganará más o menos una de cada tres apuestas y entonces, para que el juego sea justo, A debería recibir $20 cada vez que gana.

Pero supongamos ahora que un jugador B apuesta $10 a que la flecha quedará apuntando hacia uno de los puntos del conjunto V definido en la entrada anterior, ¿cuál sería en este caso un pago justo? Sucede que V es no medible, no tiene medida, por lo que la probabilidad de que la flecha quede apuntando hacia un punto de V no existe. En consecuencia, no hay pago justo para la apuesta de B. No importa cuánto decida la banca que debe pagar por esa apuesta, alguno de los dos (B o la banca), a la larga, perderá dinero, no hay modo en que queden "iguales".

Esta entrada participa en la Edición 5.3: Felix Klein del Carnaval de Matemáticas cuyo anfitrión es Juegos Topológicos.

27.4.14

Comentario a "...la falacia del jugador"

Esta entrada es un comentario a los comentarios escritos en "Una respuesta a la falacia del jugador".

La falacia del jugador es la creencia de que, por ejemplo, si sale negro varias veces seguidas en la ruleta entonces la probabilidad de rojo va aumentando cada vez para "compensar" (ya que, a la larga, deberá haber la misma cantidad de rojos que de negros). Esta idea es falsa (de ahí que se lo llame "falacia"), ahora bien la pregunta es: ¿cómo demostrarle a alguien que sostiene esa creencia que lo que cree y dice es falso?

Hay dos opciones, una es la que se propone en los comentarios a aquella entrada, que consiste simplemente en decirle al otro que su creencia es falsa e indicarle cuál es la idea correcta. En resumen, se le dice: "tú estás equivocado porque los libros dicen que la verdad es otra". Un argumento de autoridad, digamos.

Pero hay otra alternativa, que es la que yo propuse en la entrada (cuya intención parece que no fue comprendida por los comentaristas), y que consiste en decir: "Tu creencia falsa porque, de hecho, es autocontradictoria". La intención en este caso no es decir "mi lógica es superior a la tuya", sino penetrar en la lógica del otro, comprenderla y poner a la vista sus errores internos. En resumen, lo que la entrada muestra es que si se sostiene la creencia de que "si sale negro varias veces seguidas en la ruleta entonces la probabilidad de rojo va aumentando porque deben compensarse", a partir de esa misma premisa también se concluye que la probabilidad de rojo no cambia, es decir, se deduce que esa probabilidad al mismo tiempo sigue siendo siempre la misma; en conclusión, la premisa es autocontradictoria y por ende, falsa.

26.4.14

La duplicación de la circunferencia

El famoso teorema de Banach-Tarski dice que es posible cortar una esfera en una cantidad finita de partes, las cuales, convenientemente reordenadas (y sin que sean deformadas de ninguna manera), permiten armar dos esferas iguales a la original.

Mi intención en esta entrada es mostrar un resultado parecido al teorema de Banach-Tarski; un resultado que, aunque menos espectacular, es tan paradójico como él. En esta entrada voy a mostrar cómo se puede cortar una circunferencia en una cantidad infinita numerable de partes que, convenientemente reordenadas, permiten armar dos circunferencias iguales a la original (de hecho, podría armarse una cantidad infinita numerable de circunferencias iguales a la original).

Obviamente, el aspecto paradójico del teorema de Banach-Tarski consiste en que nuestra intuición nos dice que si cortamos un cuerpo en una cantidad finita de partes y las reordenamos entonces el volumen total debería conservarse. El aspecto paradójico del resultado que aquí mostraré es similar ya que, quizás no nuestra intuición, pero sí los axiomas de la medida nos dicen que la longitud debería igualmente conservarse si una curva es cortada en una cantidad numerable de partes y estas son reordenadas.

Sea C entonces una circunferencia; vamos a comenzar definiendo en ella una relación de equivalencia. Para ello, para cada número racional q con $0\leq q < 1$ consideramos el movimiento que consiste en girar todos los puntos de C un ángulo de q.360° en sentido contrario al de las agujas del reloj. A todos los movimientos así definidos los llamaremos giros válidos.
Definimos entonces la siguiente relación: dos puntos P y Q de C están relacionados si y sólo si es posible llegar de P a Q mediante un giro válido. No es difícil probar que se trata, en efecto, de una relación de equivalencia.

Llamemos V a un sistema de representantes de la relación, es decir, V contiene exactamente un punto de cada una de las clases de equivalencia determinadas por la relación definida más arriba. Una consecuencia de esta definición es que cada punto P de la circunferencia C existe un único punto Q de V tal que se puede llegar de Q a P mediante un giro válido; y ese giro también es único.

A continuación, para cada número racional q con $0\leq q < 1$ llamamos Vq al conjunto que se obtiene aplicando simultáneamente a todos los puntos de V el giro válido de q.360°. Por ejemplo V1/3 se obtiene girando los puntos de V 120° en sentido antihorario (nótese que V0 = V). De lo dicho más arriba se deduce, por un lado, que C es la unión de todos los Vq y, por el otro, que no hay puntos que pertenezcan simultáneamente a dos Vq diferentes.

Dado que el conjunto de todos los números racionales es numerable, entonces la circunferencia C ha quedado partida en una cantidad igualmente numerable de partes Vq disjuntas dos a dos. Tenemos así definidas, entonces, cuáles son las partes en que la circunferencia es cortada, veamos ahora cómo reordenarlas para completar la duplicación.

Para comenzar con la duplicación, notemos en primer lugar que dos cualesquiera de las partes en que hemos cortado a C pueden obtenerse, una de la otra, mediante un giro válido. Por ejemplo, V1/2 resulta de girar 60° a V1/3. Separamos entonces las partes que hemos definido y, aprovechando el hecho de que los racionales son numerables, las numeramos 1, 2, 3, 4,… (la imagen se sale de marco porque sigue infinitamente hacia la derecha).
A continuación separamos las partes, colocando por un lado las partes “pares” y por el otro las “impares”.
Finalmente aplicamos, tanto en la fila superior como en la inferior de la imagen, un “corrimiento” al estilo hotel de Hilbert. Con más precisión, en la fila superior de la imagen giramos la parte número 3 de modo que ocupe el lugar de la parte 2 (es decir, rotamos V1/3 para transformarla en V1/2), al mismo tiempo rotamos la parte 5 para que ocupe el lugar de la 3, y así sucesivamente hasta “llenar todos los espacios en blanco”. El resultado final es una copia de la circunferencia C. Luego repetimos el mismo proceso en la fila inferior; giramos la parte número 2 para que ocupe el lugar de la 1, la 4 para que ocupe el lugar de la 2, y así sucesivamente. Logramos así construir una segunda copia de la circunferencia C, la cual, en consecuencia hemos duplicado.

No es difícil modificar la idea (véase aquí) de tal modo que se pueda obtener una cantidad infinita numerable de copias de la circunferencia C. Y con mínimas variantes puede aplicarse también para lograr la multiplicación de un círculo al que le falte su centro (para esto último, a cada punto de conjunto V le adjuntamos el radio que lo une con el centro del círculo, aunque sin incluir al centro en sí mismo).

De modo que, si así lo desean, pueden multiplicar hasta el infinito, sin costo de material, toda su colección de discos compactos… aunque, claro, tal vez la música registrada en ellos quede un poco alterada.

Esta entrada participa en la Edición 5.3: Felix Klein del Carnaval de Matemáticas cuyo anfitrión es Juegos Topológicos.