9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ A deceptively simple problem. If a counterexample exists, it must be odd. $\endgroup$ – user156970 Jan 7 '15 at 22:13
  • $\begingroup$ @Anthony: Why must a counterexample be odd? $\endgroup$ – Jason DeVito Jan 7 '15 at 22:16
  • 1
    $\begingroup$ @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. $\endgroup$ – user156970 Jan 7 '15 at 22:33
  • 1
    $\begingroup$ @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$. $\endgroup$ – Jason DeVito Jan 7 '15 at 23:54
  • $\begingroup$ @Andres: I believe number-theory tag is appropriate for this (at least based on one answer)... $\endgroup$ – Aryabhata Jan 8 '15 at 19:54
5
$\begingroup$

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/

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.