2N digit number with exactly N ones and N zeros. Prove there exists a number divisible by N
Given a decimal number 2N digits long, but containing exactly N ones (1s) and N zeros (0s). Prove (or disprove) there exists an arrangement of the N 1s such that N is a divisor of the 2N digit number. The problem requires that the MSD always contain a 1. (Otherwise the specification of a 2N digit number would be ambiguous). Note, this is not asking if ALL arrangements of the N digits produces a 2N digit number divisible by N. Rather, it is asking if there exists SOME arrangement of the N digits causing the 2N digit number to be divisible by N.
I'm adding some thoughts I had on this.
A 1 at the ith digit (Di) represents the ith power of 10. The 2N digit number will be divisible by N if SUM(Di)=0(mod N)
Successive powers (in natural sequence) of 10 will generate all p-1 residues Mod N if 10 is a primitive root of N= p= prime number.
A full set of p-1 residues has a sum=0 (mod N=p)
In this case we need one more 1 for the full N 1 digits. It's effect can be cancelled because we have a complete set of residues. We still maintain Sum=0 mod p, by deleting one Di of them and adding 2 such that their sum = the deleted Di.
So problem is soluble when N is prime and 10 is a primitive root of N.
If 10 is not primitive (N still prime), the cycle length of successive powers is less than p-1, where cycle length is a divisor of p-1. In this case we cannot necessarily delete one and find 2 whose sum mod p is the same. That is because only a subset of residues is available.
More complications are when considering non sequential arrangements and composite N
Solution 1:
This follows from the Erdos-Ginsburg-Ziv theorem:
Any set of $2N-1$ integers, has a subset of size exactly $N$, such that the sum of elements of that set is divisible by $N$.
You can take your set to be $\{2^0, 2^1, \dots, 2^{2N-1}\}$ and the sum of the $N$ element subset will be $2N-1$ bit number with exactly $N$ ones.
A proof of that theorem can be seen here: http://uniformlyatrandom.wordpress.com/2009/01/25/the-erdos-ginzburg-ziv-theorem/