Número de 2N dígitos con exactamente N unos y N ceros. Demuestra que existe un número divisible por N

Question

Dado un número decimal de 2N dígitos, pero que contiene exactamente N unos (1s) y N ceros (0s). Demuestre (o refute) que existe una disposición de los N 1s tal que N es un divisor del número de 2N dígitos. El problema requiere que el MSD siempre contenga un 1. (De lo contrario, la especificación de un número de 2N dígitos sería ambigua). Obsérvese que no se está preguntando si TODOS los arreglos de los N dígitos producen un número de 2N dígitos divisible por N. Más bien, se está preguntando si existe ALGÚN arreglo de los N dígitos que hace que el número de 2N dígitos sea divisible por N.

Añado algunas reflexiones que he tenido al respecto.

• Un 1 en la iª cifra (Di) representa la iª potencia de 10. El número de 2N dígitos será divisible por N si SUM(Di)=0(mod N)

• Las potencias sucesivas (en secuencia natural) de 10 generarán todos los residuos p-1 Mod N si 10 es una raíz primitiva de N= p= número primo.

• Un conjunto completo de p-1 residuos tiene una suma=0 (mod N=p)

• En este caso necesitamos un 1 más para los N 1 dígitos completos. Su efecto se puede anular porque tenemos un conjunto completo de residuos. Todavía mantenemos Sum=0 mod p, borrando uno Di de ellos y añadiendo 2 tal que su suma = el Di borrado.

• Así que el problema se resuelve cuando N es primo y 10 es una raíz primitiva de N.

• Si 10 no es primitivo (N sigue siendo primo), la longitud del ciclo de las potencias sucesivas es menor que p-1, donde la longitud del ciclo es un divisor de p-1. En este caso no podemos suprimir necesariamente uno y encontrar 2 cuya suma mod p sea la misma. Esto se debe a que sólo se dispone de un subconjunto de residuos.

• Más complicaciones hay cuando se consideran los arreglos no secuenciales y los N compuestos

Answer 1

Esto se desprende de la Erdos-Ginsburg-Ziv teorema:

Cualquier conjunto de $2N-1$ enteros, tiene un subconjunto de tamaño exactamente $N$ , tal que que la suma de los elementos de ese conjunto es divisible por $N$ .

Puedes llevar tu set a ser $\{2^0, 2^1, \dots, 2^{2N-1}\}$ y la suma de los $N$ El subconjunto de elementos será $2N-1$ número de bits con exactamente $N$ los.

Una prueba de ese teorema puede verse aquí: http://uniformlyatrandom.wordpress.com/2009/01/25/the-erdos-ginzburg-ziv-theorem/