“Dados los N enteros, siempre podemos encontrar dos enteros distintos cuya diferencia de cuadrados es un múltiplo de 1000”. ¿Cuál es el valor entero más pequeño de N que haría que la afirmación sea verdadera?

Answer 1

Digamos que tenemos dos enteros [matemáticas] a [/ matemáticas] y [matemáticas] b [/ matemáticas]. La declaración

“[matemáticas] a ^ 2 – b ^ 2 [/ matemáticas] es un múltiplo de 1000”

es lo mismo que decir

“[matemáticas] a ^ 2 – b ^ 2 \ equiv 0 \ pmod {1000} [/ matemáticas]”

que es lo mismo que

“[matemáticas] a ^ 2 \ equiv b ^ 2 \ pmod {1000} [/ matemáticas]”

En particular, si [math] a \ equiv b \ pmod {1000} [/ math], entonces lo anterior es ciertamente cierto. Si [math] N = 1001 [/ math], entonces debemos tener dos enteros que sean congruentes mod 1000, por lo que funciona.

Pero no solo estamos buscando cualquier valor de [math] N [/ math] que funcione, estamos buscando el más pequeño. ¿Cómo hacemos para encontrar eso?

Bueno, lo que realmente queremos es averiguar cuántos valores posibles de [matemáticas] a ^ 2 [/ matemáticas] puede haber mod 1000. Si supiéramos este número, llámelo [matemáticas] M [/ matemáticas], entonces nosotros sabría que el valor más pequeño posible de [matemática] N [/ matemática] que satisface la declaración del problema sería [matemática] M + 1 [/ matemática].

Para ver esto, digamos que reemplazamos “1000” en la declaración del problema con “8”. Solo hay 3 residuos posibles cuando dividimos un cuadrado entre 8: 0, 1 y 4. Entonces, en este caso tenemos [matemática] M = 3 [/ matemática]. Eso significa que si tomamos [math] N = 3 [/ math], entonces podríamos encontrar algún conjunto de enteros que no tenga la propiedad deseada; por ejemplo, [math] \ {2, 4, 7 \} [/ math] funciona. Sin embargo, si tomamos [matemática] N = 4 [/ matemática], entonces dos de nuestros enteros deben tener el mismo mod cuadrado 8, lo que significa que su diferencia será un múltiplo de 8.

Entonces, ¿cuántos cuadrados posibles hay mod 1000? Desafortunadamente, no existe una fórmula fácil para calcular eso; El único método obvio, que es calcular los cuadrados mod 1000 para todos los enteros entre 1 y 1000, es básicamente el único método. Hay algunas formas de reducir el espacio de búsqueda: por ejemplo, en realidad solo necesita calcular los cuadrados de 1 a 500, ya que [math] (1000 – n) ^ 2 \ equiv n ^ 2 \ pmod {1000} [/ math ] Pero en realidad no hay una manera significativamente más fácil. Si tiene una computadora, puede escribir un programa simple para hacerlo, o será la entrada número 1000 en la secuencia A000224 en el OEIS.

De todos modos, resulta que hay 159 cuadrados distintos mod 1000. Entonces, la respuesta final es [matemáticas] 160 [/ matemáticas].