Números de Fibonacci en dos conjuntos

Question

¿Existe una manera de dividir todos los números naturales (sin cero) en dos conjuntos, de manera que no dos elementos del mismo conjunto suman un número de Fibonacci? Hice un programa en c++ y funcionó para los primeros 100'000 números naturales. Así que tiene que haber una prueba para eso...

Answer 1

Me encanta el argumento elemental presentado en el artículo de Erdos, Alladi y Hoggatt, que demuestra inductivamente que los números de Fibonacci, o de hecho cualquier recurrencia lineal del tipo Fibonacci, proporciona una partición de los enteros que es libre de suma con respecto a ese subconjunto, y de hecho la partición es única. Lo que voy a hacer es presentar el resultado y la prueba de Erdos, donde resumo los pasos clave y dejo los detalles ocultos para los lectores interesados. El argumento es elemental y realmente agradable como lectura.

Resultado : Que $u_n$ sea una secuencia dada por $u_1 = 1$ , $u_2 = b>1$ y $u_{n+2} = u_{n+1} + u_n$ , $n >0$ . Existen subconjuntos únicos $A_1,A_2 \subset \mathbb N$ tal que

• $A_1 \cap A_2 = \emptyset$ y $A_1 \cup A_2 = \mathbb N$ .
• Para $i=1,2$ y $a , b\in A_i$ , $i=1,2$ tenemos $a+b \notin \{u_j\}$ .

La prueba de Erdos es una prueba existencial. Resulta que tenemos descripciones explícitas para la secuencia de Fibonacci, según las secuencias A005652 y A005653 de la OEIS.

---

De todos modos, la prueba comienza con la construcción de la $A_i$ y demostraremos por inducción que no hay $u_i$ es la suma de dos elementos del mismo $A_i$ .

• Para empezar, ¿por qué cada uno de $u_1,u_3,...$ y $u_2,u_4,...$ ser partes de diferentes subconjuntos?

Por supuesto: si $u_1$ está en uno de los conjuntos, entonces $u_2$ no puede estar ahí porque $u_1+u_2 = u_3$ será una contradicción. Entonces $u_3$ no puede estar en el mismo subconjunto que $u_2$ De lo contrario, $u_2 + u_3 = u_4$ es una contradicción, por lo que $u_1$ y $u_3$ están en el mismo subconjunto. El argumento continúa.

Ahora suponemos que $b$ es par y $b = 2a$ .

• Todos los $1,2,...,a-1,a$ deben estar en el mismo conjunto (tomado como $A_1$ wlog). Más concretamente, si $c <a$ entonces $c,c+1$ deben estar en el mismo conjunto. (Pista: Considera qué subconjunto $d = b-c$ entraría).

¿En cuál iría? Tenemos $d+c = u_2$ y $d+(c+1) = u_2 + 1 = u_3$ así que $d$ no puede estar en el mismo subconjunto que $c$ o $c+1$ . Si $c,c+1$ pertenecen a diferentes subconjuntos, no tendríamos donde encajar $d$ ¡!

• Por supuesto, entonces $\{a+1,...,2a\} \subset A_2$ .

$b = (a-x) + (a+x)$ para cualquier $x<a$ por lo que no podemos tener $a-x,a+x$ en el mismo subconjunto.

Bien, ahora veamos $b = 2a+1$ impar.

• Utilice un razonamiento similar al anterior para obtener que $\{1,...,a-1\}$ pertenecen al mismo subconjunto , wlog $A_1$ .

• $a \in A_1$ . (Sugerencia: estudiar dónde $a+1$ y $a+2$ puede ir)

Si $a \in A_2$ Debemos tener $a+1 \in A_2$ como $a+a+1 = b$ . Pero ahora $a+2 + a = b+1$ y $a+2 + a-1 =b$ significa $a+2$ ¡no puede ir a ninguna parte!

• Ahora con un argumento similar al anterior, $\{a+1,a+2,...,2a+1\} \subset A_2$ .

---

Esto ordena todo hasta $u_2$ para los casos impar e incluso. Ahora, la parte posterior $u_2$ se propone lo siguiente como construcción de la $A_i$ . Es de naturaleza inductiva.

• Elige un $n > u_2$ . Si $n$ es uno de los $u_i$ ya sabemos dónde está. De lo contrario, hay un único $u_m < n < u_{m+1}$ . Sea $i = n - u_m$ . ¿Por qué es $i < u_{m-1}< n$ ?

La segunda es obvia, la primera de $u_{m-1} + u_m = u_{m+1} > n$ y restar $u_m$ de ambos lados.

Ahora $i$ ya se ha asignado, según la acumulación inductiva. Tenemos dos partes para esto :

• Si $i$ nunca es la mitad de ningún elemento de $\{u_i\}$ entonces pon $n$ en el mismo subconjunto que $i$ .

• Si $i = \frac{1}{2} u_{k-1}$ para algunos $k>1$ entonces $ m> k-1$ (¿por qué?) así que si $m \neq k$ , poned $n$ y $i$ en el mismo subconjunto, sino ponlos en subconjuntos diferentes.

---

Por último, tenemos que demostrar que esto funciona. Cada número entero positivo se ha colocado exactamente en un subconjunto, así que eso no es un problema. Lo que tenemos que mirar es la segunda propiedad.

Supongamos que $\{1,2,...,n-1\}$ se han clasificado en dos subconjuntos $A_1$ y $A_2$ de la forma anterior, de manera que no haya dos elementos del mismo subconjunto que sumen algún $u_i$ . Demostramos que cuando $n$ se inserta según nuestra regla, entonces la propiedad se mantiene.

Hay un único $m$ con $u_m \leq n < u_{m+1}$ .

• $n = u_m$ no es un problema. (Sugerencia: ¿cómo puede $u_m$ se haga para sumar algún $u_i$ con sólo elementos menores que $u_m$ ?)

Sólo hay $u_m + u_{m-1} =u_{m+1}$ como una posibilidad, pero estos ya pertenecen a subconjuntos diferentes.

• Entonces tenemos $u_m < n < u_{m+1}$ . Sea $a<n$ . Entonces las únicas posibilidades de $a+n$ siendo algunos $u_i$ son $a+n= u_{m+1}$ y $a+n = u_{m+2}$ .

Por supuesto, $a+n > u_m$ pero $a+n < 2n < u_{m+1} + u_{m+2} = u_{m+3}$ por lo que sólo podemos obtener dos valores para $a+n$ .

Nos dividimos en los casos $a+n = u_{m+1}$ y $a+n = u_{m+2}$ y queremos demostrar que para cualquier $a$ en el mismo subconjunto que $n$ ninguna de las dos cosas sucederá. Básicamente, la cuestión es: para $n$ , ni $u_{m+1}-n$ o $u_{m+2} -n$ debe estar en el mismo subconjunto que $n$ .

---

Dejemos que $a+n = u_{m+1}$ y $i = n-u_m < n$ .entonces $a+i = u_{m-1}$ .

• Si $a = i$ entonces $n$ y $a$ están en diferentes subconjuntos.

Entonces $a=i = \frac 12 u_{m-1}$ están en el mismo subconjunto pero según las reglas, $n$ y $i$ están en diferentes subconjuntos.

• Si $a=i$ entonces $a,n$ están en diferentes subconjuntos.

Bueno, en ese caso $i \neq \frac 12u_{m-1}$ así que pase lo que pase, las reglas dicen que $n$ y $i$ están en el mismo subconjunto. $a$ y $i$ no puede ser desde $a+i = u_{m-1}$ y son distintivo .

Así que de cualquier manera, este caso está hecho.

---

Dejemos que $a+n = u_{m+2}$ . Utilicemos el caso $1$ : $n$ y $u_{m+1} - n$ pertenecen a diferentes subconjuntos de allí.

• $u_{m+1} - n$ y $u_{m} + (u_{m+1}-n)$ pertenecen al mismo subconjunto. (Sugerencia : deja que $I = u_{m+1} - n$ entonces $N= u_{m} + (u_{m+1}-n) = u_m + i$ así que $N- u_m = I$ . Nuestras normas dicen que $N$ y $I$ pertenecen al mismo subconjunto a no ser que ocurra algo, ¡pero eso no ocurre en realidad!)

Sí, $N$ y $I$ pueden pertenecer a diferentes subconjuntos , pero para que eso ocurra debemos tener $I = \frac 12 u_{m-1}$ . Pero entonces $u_{m+1} - n = \frac 12 u_{m-1}$ y multiplicar por dos y reordenar para obtener $2n= u_{m+2} = a+n$ así que $a = n$ un problema.

Pero acabamos de demostrar que $u_{m+1} - n$ y $u_{m} + (u_{m+1}-n) = u_{m+2}-n$ pertenecen al mismo subconjunto. $n$ no pertenece al mismo subconjunto que el primero por si acaso $1$ por lo que no pertenece al mismo subconjunto que $u_{m+2} - n = a$ ¡tampoco!

En consecuencia, ¡hemos terminado!

---

Unicidad : Demostramos por inducción que esto se cumple. Sin embargo, podemos omitir algunos números.

• El caso base queda claro en la prueba, sólo hay una forma de asignar todo hasta $u_2$ . Además, el $u_i$ se asignan de forma única también a partir de la prueba de nuevo.

• Para cualquier $n$ , dejemos que $u_m < n < u_{m+1}$ . Entonces $j = u_{m+1} - n < n$ y $n$ no están en el mismo subconjunto, así que como $j$ se asigna de forma única, $n$ también se asigna de forma única.

Esto completa la prueba del resultado.