¿Puedes probar [math] f: \ mathbb {N} \ times \ mathbb {N} \ to \ mathbb {N} [/ math], con [math] (m, n) \ mapsto \ frac {(m + n ) ^ 2 + 3m + n} {2} [/ math] es inyectivo?

Answer 1

Así es como abordaría esto. No es la solución más corta y eficiente, pero creo que es natural, clara, reveladora y en realidad le brinda más de lo que esperaba.

Ante casi cualquier problema, lo primero que debe hacer es jugar con él. Aquí tenemos una función concreta de dos variables; Intentemos ver qué hace . Simplemente elija algunos valores simples y vea lo que obtiene.

[matemáticas] (0,0) \ a 0 [/ matemáticas]

Con eso quiero decir que si [matemática] m [/ matemática] y [matemática] n [/ matemática] son ​​ambas [matemática] 0 [/ matemática] entonces el valor de [matemática] f [/ matemática] es [matemática] 0 [/ matemáticas] también. Sigamos:

[matemáticas] (0,1) \ a 1 [/ matemáticas]

[matemáticas] (1,0) \ a 2 [/ matemáticas]

[matemáticas] (0,2) \ a 3 [/ matemáticas]

[matemáticas] (1,1) \ a 4 [/ matemáticas]

[matemáticas] (2,0) \ a 5 [/ matemáticas]

Los valores de la derecha son tan ordenados como podríamos imaginar. Esta es su pista principal y la clave para resolver el problema (y más).

Por supuesto, tal vez hubieras intentado cosas en un orden diferente, como tal vez hubieras marcado [matemáticas] (0,2) [/ matemáticas] antes de [matemáticas] (1,0) [/ matemáticas]. Pero el patrón agradable que hemos encontrado es realmente difícil de omitir: si organiza los valores en una tabla, con columnas para [math] m [/ math] y filas para [math] n [/ math], obtendrá algo como esta:

0 2
1

y luego esto:

0 2 5
1 4
3

y entonces:

0 2 5 9
1 4 8
3 7
6 6

Claramente, la función opera por “diagonales”, emitiendo secuencialmente los números naturales a medida que la entrada [math] (m, n) [/ math] escanea todas las combinaciones posibles diagonal por diagonal. Primero tenemos esos valores de [math] (m, n) [/ math] donde [math] m + n = 0 [/ math], luego aquellos donde [math] m + n = 1 [/ math], y así en. Dentro de cada diagonal, estamos escaneando de izquierda a derecha, es decir, aumentando el valor de [math] m [/ math], y la salida siempre es simplemente el siguiente número natural disponible.

Si tenemos razón y este patrón persiste, hemos terminado: la función es claramente inyectiva, ya que nunca produce la misma salida dos veces. Además, también es sobreyectivo: cubre todos los números naturales. En otras palabras, esta pequeña y linda función establece una biyección explícita entre pares de números naturales y números naturales individuales , y lo hace simplemente usando la aritmética básica.

Esto lo convierte en una función realmente importante: enriquece el poder expresivo del lenguaje aritmético de primer orden para hablar no solo de números individuales sino también de pares y más. Georg Cantor lo usó por primera vez en 1878, y se ha convertido en una técnica estándar utilizada también por Turing, Gödel y otros. Incluso hay un teorema en el sentido de que es la única biyección polinómica de segundo grado entre pares y números.

De todos modos, volviendo a la prueba: debemos demostrar que nuestra función realmente hace lo que creemos que hace. Comprobar cosas con unos pocos valores pequeños no es suficiente.

¿Cómo debemos formalizar nuestra hipótesis? Bueno, se supone que hemos encontrado una regla simple que describe [matemáticas] f [/ matemáticas], así que veamos si realmente podemos escribirla. Si te preguntara qué es [matemática] f (7,10) [/ matemática], ahora que presumiblemente entiendes qué es [matemática] f [/ matemática], ¿cómo responderías? Trata de pensarlo primero.

Okay. Dijimos que [math] f [/ math] funciona “en diagonal”. El punto [math] (7,10) [/ math] se encuentra en la diagonal [math] m + n = 17 [/ math], por lo que se supone que el valor de [math] f [/ math] es lo que sea en la parte inferior de la diagonal, es decir, en [matemáticas] (0,17) [/ matemáticas], y luego solo necesitamos agregar [matemáticas] m [/ matemáticas] a eso, porque esto es lo que [matemáticas] f [/ matemáticas] parece estar haciendo a medida que avanzamos por la diagonal.

¿Cuál es este valor en la parte inferior de la diagonal? Solo mira la primera columna de la tabla que hiciste:

0 0
1
3
6 6
10
…

Puede reconocer estos números, pero si no puede ver que hacen lo que deben hacer: crecen en [matemáticas] 1 [/ matemáticas], luego en [matemáticas] 2 [/ matemáticas], luego en [matemáticas] 3 [ / matemáticas] y así sucesivamente, para acomodar la longitud creciente de las diagonales.

Entonces, si estamos en diagonal [matemática] d [/ matemática], lo que significa que cuando [matemática] m + n = d [/ matemática], el valor al pie de la diagonal [matemática] (0, d) [/ matemática] se supone que es la suma [matemática] 0 + 1 + 2 + \ ldots + d [/ matemática], que es [matemática] d (d + 1) / 2 [/ matemática]. Vamos a ver eso:

[matemáticas] \ displaystyle f (0, d) = \ frac {d ^ 2 + d} {2} [/ matemáticas]

Perfecto, justo lo que necesitamos. Finalmente, debemos confirmar que [math] f (m, n) [/ math] es exactamente [math] m [/ math] más que [math] f (0, m + n) [/ math]. Y he aquí, he aquí

[matemáticas] \ displaystyle f (0, m + n) = \ frac {(m + n) ^ 2 + (m + n)} {2} [/ matemáticas]

[matemáticas] \ displaystyle f (m, n) = \ frac {(m + n) ^ 2 + (m + n) + 2m} {2} [/ matemáticas]

que es exactamente [matemáticas] m [/ matemáticas] más. Hecho: [matemáticas] f [/ matemáticas] hace lo que esperábamos que hiciera.

Con esta prueba, puedes ver literalmente por qué [math] f [/ math] es inyectiva y, de hecho, biyectiva. Puede ver que la prueba sigue una estructura típica: verifique casos pequeños, identifique un patrón, forme una conjetura, pruebe la conjetura. Esto es mucho más fácil aquí que intentar directamente demostrar que [matemáticas] f (m, n) = f (m ‘, n’) [/ matemáticas] fuerzas [matemáticas] (m, n) = (m ‘, n’) [/matemáticas]. Y dado que comprende lo que realmente es esta [matemática] f [/ matemática], también puede olvidar su fórmula y reconstruirla en cualquier momento en el futuro, simplemente volviendo sobre su lógica. Entonces todo está bien.

Answer 2

Deje que [math] t_n = \ frac {1} {2} n (n + 1) [/ math] denota el [número matemático] n [/ math] th triangular . Entonces [matemáticas] t_ {n + 1} – t_n = n + 1 [/ matemáticas].

Notamos eso

[matemáticas] f (\ big ((m, n) \ big) = \ dfrac {(m + n) ^ 2 + (m + n) + 2m} {2} = t_ {m + n} + m [/ matemáticas] [matemáticas], \ ldots (\ estrella) [/ matemáticas]

y

[matemática] 1 \ le m

Suponga que [math] a, b, c, d [/ math] son ​​enteros positivos tales que [math] f \ big ((a, b) \ big) = f \ big ((c, d) \ big) [/ matemáticas]. Así

[matemáticas] t_ {a + b} + a = t_ {c + d} + c \ ldots (\ star \ star) [/ math]

es un número entero positivo que se encuentra entre números triangulares consecutivos [matemática] t_ {a + b}, t_ {a + b + 1} [/ matemática] y también números triangulares consecutivos [matemática] t_ {c + d}, t_ {c + d + 1} [/ matemáticas]. Se deduce que [matemática] a + b = c + d [/ matemática], y por lo tanto [matemática] a = c [/ matemática] de la ecuación. [matemáticas] (\ estrella \ estrella) [/ matemáticas]. Así [matemáticas] b = d [/ matemáticas]. Esto prueba que [matemática] f [/ matemática] es inyectiva . [matemáticas] \ blacksquare [/ matemáticas]

Answer 3

Sea [math] n = N [/ math] y [math] m = 0 [/ math]:

\ begin {align} f (0, N) & = \ frac {N ^ 2 + N} 2 \\ & = \ tfrac12N (N + 1) \ end {align}

Esto significa que [math] f (0, N) = \ sum_ {k = 1} ^ Nk [/ math], es la suma de los primeros números [math] N [/ math].

Mantengamos [math] m + n = N [/ math], pero cambiemos [math] m [/ math] para cualquier valor [math] 0 \ le m \ le N [/ math]. Entonces [matemáticas] n = Nm [/ matemáticas]:

\ begin {align} f (m, Nm) & = \ frac {N ^ 2 + 3m + (Nm)} 2 \\
& = \ frac {N ^ 2 + N-2m} 2 \\
& = \ tfrac12N (N + 1) + m \\
& = f (0, N) + m
\ end {alinear}

Dentro de la familia [math] m + n = N [/ math], la función [math] f (m, n) [/ math] es inyectiva.

Para [matemática] m = N [/ matemática] con [matemática] m + n = N [/ matemática], tenemos que [matemática] f (N, 0) = f (0, N) + N [/ matemática] .

Comparemos con [math] f (0, N + 1) [/ math] y tenemos que \ begin {align}
f (0, N + 1) & = \ tfrac12 (N + 1) (N + 2) \\
& = \ tfrac12N (N + 1) + (N + 1)
\ end {alinear}

Entonces podemos ver que [matemáticas] f (0, N + 1) = f (N, 0) +1 [/ matemáticas], por lo tanto [matemáticas] f (0, N + 1)> f (m, Nm) [ / math] para todos [math] n \ in \ mathbb N, m \ le N [/ math],
y dado que [matemáticas] f (m_1, N + 1-m1) = f (0, N + 1) + m_1 [/ matemáticas] entonces [matemáticas] f (m, Nm)

No hay dos pares [matemática] (m_1, n_1) \ neq (m_2, n_2) [/ matemática] como [matemática] f (m_1, n_1) = f (m_2, n_2) [/ matemática].

Answer 4

Aquí hay un boceto de una prueba: si [math] m_1 + n_1, m_2 + n_2 [/ math] son ​​lo suficientemente grandes, entonces la única forma de

[matemáticas] \ displaystyle \ frac {(m_1 + n_1) ^ 2 + 3m_1 + n_1} {2} = \ frac {(m_2 + n_2) ^ 2 + 3m_2 + n_2} {2} [/ matemáticas]

es si [matemáticas] m_1 + n_1 = m_2 + n_2 [/ matemáticas]. Esto se debe a que si [math] m_1 + n_1 \ leq m_2 + n_2 – 1 [/ math], la cantidad de la izquierda será automáticamente menor que la cantidad de la derecha.

Sin embargo, dado esto, notamos que al restar múltiplos de [math] m_1 + m_2 [/ math] en ambos lados, obtenemos [math] m_1 = m_2 [/ math], que resuelve el asunto.

Todo lo que queda es determinar exactamente qué tan grande es “lo suficientemente grande” y mostrar que no hay pequeños contraejemplos (que deberían ser posibles simplemente por fuerza bruta).

Answer 5

Aquí hay una solución de ‘prueba por contradicción’.

Sea [math] f (m, n) = f (p, q) [/ math]. Luego, simplemente escriba la fórmula explícita de [math] f [/ math] para llegar a esta ecuación: [math] (m + npq) (m + n + p + q + 1) = 2 (pm) [/ math]

Claramente, [matemáticas] | pm | <| m + n + p + q + 1 | [/ matemáticas], entonces, [matemáticas] | m + npq | = 0, 1 [/ matemáticas]. Si es 0, entonces [matemática] p = m [/ matemática] y obtenemos [matemática] (m, n) = (p, q) [/ matemática]. Si es 1, entonces tenemos dos casos. Si [math] m + npq = 1 [/ math], entonces [math] 2 (pm) = m + n + p + q + 1 [/ math], y de las dos ecuaciones obtenemos [math] 2 (pm ) = 2 (p + q + 1) [/ math], claramente una contradicción. Entonces [math] m + npq [/ math] debe ser -1. Entonces [matemática] 2 (mp) = m + n + p + q + 1 [/ matemática] y obtenemos [matemática] m = 2p + q [/ matemática], que da [matemática] n = -1-p [ / math], que está fuera del dominio de [math] f [/ math]. Por lo tanto demostrado.

Answer 6

1. Si ambos [matemática] m, n [/ matemática] par, ambos impares, uno par uno impar, todos podemos mostrar que RHS es entero. Si [math] n, m \ ge 0, [/ math] entonces [math] f (n, m) \ ge 0, [/ math] así que para probar inyectiva, solo necesitamos probar one-one.
2. Si [matemática] f (m, n) = f (m, n_0), [/ matemática] [matemática] n, n_0, m \ in \ mathbb {N} [/ matemática] entonces [matemática] n = n_0: [ / matemáticas] [matemáticas] n ^ 2 + 2mn + m ^ 2 + 3m + n = n_0 ^ 2 + 2mn_0 + m ^ 2 + 3m + n_0, [/ matemáticas] if [matemáticas] n \ ne n_0, m = \ dfrac {(n-n_0) (n + n_0) + (n-n_0)} {2 (n_0-n)} = \ dfrac {- (n + n_0) -1} {2}, [/ matemáticas] [matemáticas ] m [/ math] es negativo, lo cual es una contradicción, entonces [math] n = n_0. [/ math] Hemos probado 2.
3. Si [math] f (m, n_0) = f (m_0, n), [/ math] [math] n, n_0, m, m_0 \ in \ mathbb {N} [/ math] entonces [math] n = n_0 [/ matemática] y [matemática] m = m_0: [/ matemática] [matemática] f (m, n) – f (m, n_0) = f (m, n) – f (m_0, n) [/ matemática] , [matemática] (n-n_0) (n + n_0 + 1 + 2m) = (m-m_0) (m + m_0 + 3 + 2n), [/ matemática] si [matemática] m \ ne m_0, \ dfrac { n-n_0} {m-m_0} = \ dfrac {m + m_0 + 3 + 2n} {n + n_0 + 1 + 2m} = \ dfrac {m + m_0 + 3 + n + n_0} {n + n_0 + 1 + m + m_0} [/ matemáticas], deje que [matemáticas] n-n_0 = n_1 [/ matemáticas], [matemáticas] m-m_0 = m_1 [/ matemáticas], [matemáticas] X = n + n_0 + 1 + m + m_0 [/ math], tenemos [math] \ dfrac {n_1} {m_1} = \ dfrac {X + 2} {X}, [/ math] obviamente [math] n_1> m_1 [/ math], y el único Las posibilidades para [matemáticas] m_1 [/ matemáticas] son ​​[matemáticas] m_1 = X, [/ matemáticas] o [matemáticas] m_1 = X / 2, [/ matemáticas] pero [matemáticas] m_1 \ lt X / 2 [/ matemáticas] (ambos [matemática] n, m \ gt m_1 [/ matemática]), lo cual es una contradicción, entonces [matemática] m = m_0. [/ matemática] De 2. [matemática] n = n_0. [/ matemática] Tenemos Probó el problema.