# 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

• A deceptively simple problem. If a counterexample exists, it must be odd. – user156970 Jan 7 '15 at 22:13
• @Anthony: Why must a counterexample be odd? – Jason DeVito Jan 7 '15 at 22:16
• @Jason: Wow, this is such a deep, fascinating problem. As I think more about it, I realize that I can only rule out numbers that are not 3-smooth. If $n = 2^j$ then all you have to do is clump the zeros together at the end. If $n = 3^k$ then any arrangement with a one as most significant works. And if $n = 2^j 3^k$, any arrangement with a one as most significant and a zero as least significant works. – user156970 Jan 7 '15 at 22:33
• @Anthony: Agreed. I think for you last sentence, you need to trail with at least $j$ $0$s, not just one at the end. Incidentally, does anyone know what number works when $n = 7$? The next case which requires any work at all is $n=11$. – Jason DeVito Jan 7 '15 at 23:54
• @Andres: I believe number-theory tag is appropriate for this (at least based on one answer)... – Aryabhata Jan 8 '15 at 19:54

## 1 Answer

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/

• The set could be a multiset. – Aryabhata Jan 8 '15 at 2:34