Problema fácil o difícil

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.

28 comentarios sobre “Problema fácil o difícil

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

  2. 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?

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

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

  5. 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.»

  6. :| 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.

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

  8. 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!

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

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

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

    ¿Cómo? Sí más abajo, cuando mostrás la matriz de 4×4 estás incluyendo una de 3×3 válida…

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *