Blog de Javier Smaldone

Todos los días se aprende algo viejo

Artículos recientes

Comentarios recientes

  • Raul en Si esto no es innovación... (perdón, Microsoft)
  • ruben en Genial trampa para mosquitos
  • maria en Fibertel, una porquería
  • gabriel en Fibertel y su proxy transparente
  • Pedro López Azcuénaga en Fibertel y su proxy transparente

Artículos al azar

Problema fácil o difícil

Publicado por  Javier el 9 de Agosto de 2006  

Con el siguiente problema tuve varias experiencias curiosas. Distintas personas a las que se los he planteado encontraron soluciones equivalentes, pero de maneras muy diferentes. Algunas tardaron más tiempo y encontraron la solución examinando y puliendo varias posibilidades. Alguien, en cambio, lo resolvió en un par de minutos, y la forma en que arribó a dicha solución fue metódica, simple y elegante.

El problema es el siguiente:

Disponemos de una matriz infinita, cuyos índices son los números naturales (esto es, las columnas y las filas están numeradas desde 0 en adelante). El problema consiste en completar la matriz con números naturales, de manera que cada fila y cada columna contenga una única aparición de cáda número natural.

Para comprender mejor el problema: podríamos pensar en completar la primera fila (0) con todos los números naturales, a partir desde 0, y en la segunda fila (1) “desplazarlos” una posición (ocupando el 0 la columna 1); y así sucesivamente. El problema es que no podríamos encontrar un número natural que colocar en la columna 0 de la segunda fila (el infinito no es un número, ¿verdad?), por lo cual esta estrategia no funcionaría.

En algunos días, en los cuales ojalá reciba algunas respuestas, completaré el artículo comentando la solución y las distintas formas en que me fueron presentadas.

Categoría: Lógica y Matemática

Agregar a del.icio.us

Marcar en Technorati

23 comentarios

Joserra dijo:
14 de Agosto de 2006 a las 3:59  

0 2 5 9 14
1 4 8 13
3 7 12
6 11
10 …
15

¿en diagonal?

javier dijo:
14 de Agosto de 2006 a las 10:44  

Quizás el enunciado no es lo suficientemente claro (ya algún amigo me lo hizo notar). Cada fila debe contener todos los números naturales, sin repetición, y lo mismo para cada columna.

cArmides dijo:
15 de Agosto de 2006 a las 10:39  

Acabo de leer el problema y a primera vista a lo único que llego es que se deberían poner los naturales en la diagonal principal de la matriz, ya que si:
- Dado un i fijo, para cada natural n existe un único j tal que M[i][j] = n
- Dado un j fijo, para cada natural n existe un único i tal que M[i][j] = n
por lo que para el caso particular de i=j se debe cumplir que para cada natural n, debe existir un único i=j / M[i][i] = n.
Así, tengo una forma de rellenar la diagonal principal, pero no encuentro un método de rellenar el resto. ¿Nos podrías decir si este problema tiene solución?

javier dijo:
15 de Agosto de 2006 a las 11:33  

cArmides: El problema tiene solución (no hay trucos ni trampas). Yo se de al menos una, y en ella no vale lo que has postulado sobre la diagonal principal.

Claudio dijo:
16 de Agosto de 2006 a las 2:03  

La verdad que no estoy seguro (soy un desastre para las matemáticas) pero a primera vista la solución sería simplemente “desplazar” los números como dice en la explicación del problema pero a la izquierda en vez de a la derecha. Ej.:

0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
…

Etc. Ahora, si la cuestión es que en cada fila deben estar *todos* los números naturales, lo que se me ocurre es esto:

* Escribir la primer fila desde el 0 en adelante.

* Escribir la segunda invirtiendo cada par de (cada dos) números, ej.:

0 1 2 3 4 5
1 0 3 2 5 4

* Escribir la tercera nuevamente tomando como referencia la primer fila, pero esta vez invirtiendo cada grupo de 4:

3 2 1 0 7 6 5 4 11 10 9 8

… Y así sucesivamente, tomando grupos de tamaño N, siendo N potencia de 2 (2, 4, 8, 16, 32…).

No lo he comprobado más que para 5 filas de 15 o 20 números, así que no sé si esto será válido realmente.

Antonio dijo:
23 de Agosto de 2006 a las 4:51  

Los numeros naturales no incluyen al cero

javier dijo:
23 de Agosto de 2006 a las 10:03  

Antonio:

Si no consideramos al cero como un número natural, la suma se queda sin elemento neutro y el producto sin elemento absorbente. Sin él, el álgebra de los números naturales se vuelve bastante inútil.

Y no solo eso, sino que además en muchos contextos, conviene comenzar a contar desde cero.

Gracias por tu comentario.

javier dijo:
23 de Agosto de 2006 a las 15:28  

if x=0 and y=0 then
a(x,y)=0
elseif x > 0 then
a(x,y)=a(x-1,y)+x+y
else
a(x,y)=a(x,y-1)+y+1
end if

javier dijo:
23 de Agosto de 2006 a las 15:30  

el de arriba es otro javier (no smaldone)
saludos

cArmides dijo:
23 de Agosto de 2006 a las 16:53  

Hola,
He vuelto al blog pero ahora con otra duda (asi soy de ignorante) ;). La matriz resultante, ¿tiene que tener una ocurrencia de cada natural en cada fila y en cada columna? En caso de que no fuera así, igual una solución podría ser, rellenar la diagonal principal con 0, la primera fila 0,1,2,3…, la primera columna como 0,1,2,3,… lo que podría desembocar en la “recurrencia” (o como se diga):
Para todo i,j=0,1,2,…..natural
M[i][j] = 0, si i=j
M[i][j] = M[j][i] = i+j, si i!=j

cArmides dijo:
23 de Agosto de 2006 a las 16:57  

nada, me contesto a mi mismo, como se comenta en un post anterior: “Cada fila debe contener todos los números naturales, sin repetición, y lo mismo para cada columna.”

cArmides dijo:
23 de Agosto de 2006 a las 17:57  

:| supongo q con alguna de las soluciones que des saldremos de dudas, porque este problema me parece como resolver el problema de encontrar permutaciones de infinitos elementos (los naturales). No sé si es correcto pero si la matriz se va rellenando
0 1 2 3 4
1 2 3 4
2 3 4
3 4
4
hasta llegar a infinito en la diagonal secundaria, justo por debajo de ella volveríamos a tener:
0…
0 1…
0 1 2…
0 1 2 3…
0 1 2 3 4….
Así, tendríamos que en la matriz cada natural aparece el mismo número de veces (creo). Todavía me es un difícil pensar en conjuntos numerables pero de cardinalidad infintia.

cArmides dijo:
23 de Agosto de 2006 a las 18:01  

menos mal q postear cuesta menos q hacerlo en papel, pero cuando digo por debajo de la diagonal secundaria, me refiero a
……….0
……..0 1
……0 1 2
….0 1 2 .
..0 1 2 . .
0 1 2 ..(infinito-1)

Hernan Moraldo dijo:
8 de Septiembre de 2006 a las 20:35  

Mi solución es la siguiente:

Procedo a llenar la matriz de acuerdo al siguiente procedimiento:

- Me permito llenar un valor en fila i, y columna l, solamente si todos los valores anteriores de la fila i y la columna l ya han sido llenados.

- Cada vez, escribo el menor número que no se haya repetido en la fila i, y la columna l.

- Repetir, repetir, y seguir repitiendo

Con este procedimiento, lleno la matriz sin ningún problema.

Saludos y excelente problema, muy interesante también!

Hernan Moraldo dijo:
8 de Septiembre de 2006 a las 20:41  

Ejemplo de cómo lleno la matriz de acuerdo a este procedimiento:

Empiezo por la esquina superior izquierda, no tengo opción:

0

Sigo:

012345678…
1
2
3
4
…

Sigo completando la segunda columna, recordando siempre escribir el primer número (el menor número natural) que no se repita en fila ni columna:

012345678…
10
23
32
45
54
67
…

Sigo en la tercer columna:

012345678…
103
230
321
456
547
674
…

La siguiente:

012345678…
1032
2301
3210
4567
5476
6745
…

Y así sucesivamente (si no me equivoqué al rellenar).

Y voilá, problema resuelto :)

hola dijo:
26 de Septiembre de 2006 a las 13:59  

que diablos es matriz?

diana dijo:
24 de Octubre de 2006 a las 10:43  

por fa necesito saber como se opera, recorre, ordena y llena una matriz.

andres dijo:
27 de Octubre de 2006 a las 23:02  

f(x, y) = concat ((x+1), y)

Creo que es una solución.

Saludos!

andres dijo:
27 de Octubre de 2006 a las 23:06  

Mmm… no, faltan los números 0,1,…,9

javier alvarez dijo:
2 de Noviembre de 2006 a las 12:53  

Hola, como estas javier?, hace ya casi tres meces que publicaste este post, para cuando la solucion?

Saludos.

javier dijo:
6 de Noviembre de 2006 a las 16:47  

Al fin… la soluciòn:

La respuesta de Hernán Moraldo es correcta, pero me parece más interesante aún analizar cómo podemos encontrar la solución al problema.

Una forma de enunciar la solución es como lo hizo Hernán: ponemos en cada lugar el menor número natural que no aparezca antes en esa fila ni en esa columna. Varias personas (todas ellas muy inteligentes) me dieron esta solución después de pensar un rato (entre 10 minutos y un par de días).

Una persona, sin embargo, arribó a la misma solución con un enfoque totalmente diferente (¡hola Pablito!), que me encantò por su conomía de pensamiento. Encontró la solución mediante inducción sobre los números naturales.

Primero se planteó el problema para un único número (el cero). La solución es trivial: obtenemos una matriz de 1×1 cuyo único elemento es el cero.

Luego se planteó el problema para dos elementos (0,1). Como la solución debía conservar el resultado anterior, obtuvo una matriz de 2×2 cuya primera fila es 0,1 y la segunda 1,0.

Al analizar la situaciòn considerando 3 nùmeros, vio que no existe soluciòn posible.

Luego pasó a los 4 primeros números, y obtuvo la siguiente matriz:

0,1,2,3
1,0,3,2
2,3,0,1
3,2,1,0

Claramente puede verse que se va repitiendo un patrón cuadrado.

Reitero, lo que me parece fascinante de esta soluciòn es que no requiere de ningún esfuerzo mental (no se nos tiene que “ocurrir” la soluciòn, sino que esta se encuentra razonando de forma ordenada).

Es interesante notar que muchos problemas pueden resolverse siendo muy inteligentes… pero tambièn siendo un poco ordenados.

javier alvarez dijo:
22 de Noviembre de 2006 a las 14:52  

Gracias por publicar la respuesta

mariana dijo:
24 de Mayo de 2007 a las 17:01  

HOLA

Artículo al azar

Deja tu comentario:

« El camino del monje
¡Ah, pero qué bonito! »