Progresiones aritméticas finitas

Question

Hace unos años, alguien me contó un problema encantador. Sospecho que puede haber algo más (que me interesaría aprender), y me gustaría mucho encontrar una referencia, me incomoda usarlo en clase sin poder señalar su fuente.

El problema es el siguiente. Pondré la solución que conozco, que es la razón por la que me gusta, como respuesta, para dar un poco de oportunidad a la gente que lo lea y quiera pensar en ello sin que se lo estropeen.

Supongamos que los números naturales se dividen en un número finito de progresiones aritméticas. Entonces dos de estas progresiones deben tener la misma diferencia común.

Answer 1

Este era uno de mis problemas favoritos en el instituto. Mi demostración era la siguiente: si consideras el problema módulo n, donde n es el mínimo común múltiplo de las diferencias de las progresiones aritméticas, puedes reformular el problema de la siguiente manera: si los vértices de un n-gon regular se dividen en k-gons regulares centrados en el origen, dos de ellos tendrán el mismo tamaño. Para demostrarlo, se dispone el n-gono regular de modo que tenga vértices en las raíces n-ésimas de la unidad en el plano complejo y se asigna el polinomio mónico a cada k-gono individual cuyas raíces sean exactamente los vértices del polígono. De esta forma obtendremos la expresión $x^n-1=(x^{k_1}-\zeta_1)(x^{k_2}-\zeta_2)\cdots$ . Multiplicando el lado derecho vemos que si $k_1$ es el menor de los $k_i$ entonces la única manera de cancelar el término de $x^{k_1}$ de la RHS es tener otra $k_i=k_1$ probar la reclamación.

Answer 2

Asignar a cada progresión $A_i=(a_i+kb_i\mid k\in{\mathbb N})$ , $1\le i\le n$ su serie generadora, $f_i(x)=\sum_{k=0}^\infty x^{a_i+kb_i}$ . Entonces $f_i(x)=x^{a_i}/(1-x^{b_i})$ . Obsérvese que la serie converge para $|x|<1$ .

Ahora bien, dado que el $A_i$ partición ${\mathbb N}$ tenemos $\sum_{i=1}^n f_i(x)=1/(1-x)$ . Si todos los $b_i$ son diferentes, dejemos que $b$ sea la mayor, y fijar una primitiva $b$ -enésima raíz de la unidad $\zeta$ . Ahora dejemos que $x\to\zeta$ para llegar a una contradicción.

Esto demuestra que el mayor de las diferencias comunes deben aparecer al menos dos veces.

Answer 3

Probablemente estés pensando en la prueba, mediante funciones generadoras, debida a D J Newman. No tengo la referencia de la primera aparición impresa, pero está en su libro, A Problem Seminar, problema 90, en la página 18, con solución en la página 100.

Supongo que al plantear el problema debe requerir finitamente muchos pero al menos dos progresiones aritméticas.

Answer 4

Capítulo uno del Libro matemático para colorear discutir este problema. Allí encontrará encontrará algo de su historia. Aparentemente fue conjeturado por Erdös en 1950 y demostrado (pero no publicado) unos meses más tarde por Donald Newman y Leon Misrky.

Answer 5

Esto es "lo mismo" que la prueba de la función generatriz, pero no utiliza funciones generatriz explícitamente. Se toma la mayor diferencia común en cualquiera de las secuencias, digamos n, y se elige $\zeta$ una raíz n-ésima primitiva de la unidad. Para cada entero positivo $m$ asociar el número complejo $\zeta^m$ . Obsérvese que en cualquier secuencia aritmética con diferencia común menor que n, la suma sobre sus entradas de $\zeta^m$ permanece acotada, mientras que para una secuencia aritmética de diferencia común n, crece ilimitadamente. Dado que la suma sobre todos los enteros permanece acotada, tiene que haber una segunda secuencia de diferencia común n para equilibrar la primera.