Let N be equal to 2^1999. Is there a positive integer, multiple of N, whose decimal representation does not contain the digit 0? How would you construct such an integer or prove that it doesn't exist?

We shall fight them one by one!As Tomfr says, N is equal to 2^1999. Let K(x) be the number of digits in the decimal representation of x and let Z(x) be the position of the rightmost zero in the decimal representation of x counted from the right[*] starting from 0, so K(1024) = 4 and Z(1024) = 2, and it will be convenient to define Z(x) = K(x) if the decimal representation of x does not contain the digit 0, so that Z(512) = 3Observe, that if x is a power of 2 and y = x + x * 5^Z(x), then Z(y) > Z(x).Build a sequnce of multiples of N: x1 = N, x2 = x1 + N* 5^Z(x1), ... until either Z(xk) > 1999 or K(xk) = Z(xk).In the latter case, we have found a multiple of N which does not contain the digit 0.In the former case let M be the element of the sequence such that Z(M) > 1999. Now we can patch the zeros in the decimal representation of M by adding a multiple of 10^1999 as follows.If Z(M) < K(M), then let y1 = M + 10^Z(M). The number y1 is a multiple of N since 10^Z(M) is and K(y1) = K(M).If we continue this process we end up with a sequence y1, y2 = y1 + 10^Z(y1), ... This increasing sequence of numbers terminates since K(yi) = K(M). The last element of this sequence does not contain the digit 0 in its decimal representation.[*] was "leftmost zero in the decimal representation of x counted from the left" which is wrong, as pointed out by zerdna

QuoteLet K(x) be the number of digits in the decimal representation of x and let Z(x) be the position of the leftmost zero in the decimal representation of x counted from the left starting from 0, so K(1024) = 4 and Z(1024) = 2, and it will be convenient to define Z(x) = K(x) if the decomal representation of x does not contain the digit 0, so that Z(512) = 3Observe, that if x is a power of 2 and y = x + x * 5^Z(x), then Z(y) > Z(x)I think, you are counting digits from the left starting from count 1, not zero. That is consistent with K(1024)=4 as well. In any event, Z(4096)=2 in your definition as well. OK, then 4096*(1+5^2)=106496, and Z(y)=Z(x) unlike what you are saying. Not only that, it's easy to come up with Z(y)< Z(x), for examplex=2^17=131072, Z(x)=4, y = x*(1+5^4)=82051072, Z(y) = 3 < Z(x)

Thank you, I have to correct this mistake. The intended definition of Z(x) is the position of the RIGHTmost zero counted from the RIGHT, starting from 0, so that Z(512) = 3, Z(4096) = 2,Z(11111101) = 1, Z(2^17) = 2 and Z(2^17 * 26) = Z(3407872) = 4.

Hi Tomfr,N=2^1999For N, the first and last digit will not be zero and the last digit can only be 2, 4, 6 or 8. I assume that there are some zeros in between the first and last digit of N. N is of the form xxx0…x0x…0xx.L: No. of non zero digits counting from the left of N’ before hitting a zero.R: No. of non zero digits counting from the right of N’ before hitting a zero.Z(k): be of the form 10…01 where Z(0) = 11, Z(1) =101, Z(2)=1001, Z(3)=10001 etc.Let the first N’=N. Check for L & R and then multiply N’ with Z(min(L,R)-1) to get the new N’. Check for L & R again and then multiply N’ with Z(min(L,R)-1) to get another new N’. Do this iteratively, I think it will get rid of the zeros in N’. And the multiple that we are looking for is just the multiplication of all the Z.Do you think that this will work? Thanks.CK

Answer is yes, and we can work from right to left. Starting with N, notice that its rightmost digit is not zero. Let the rightmost zero be in the Kth position. Then if we add (10^K)*N (ie N shifted over K positions), that digit is changed without affecting any digit to the right of it. Now we can find the next zero, and again add (10^J)*N for some appropriate J. Going on, with each iteration, the rightmost zero moves further to the left. We continue until the rightmost zero is at least 1999 places to the left (or there are none). Now our integer is (10^1999)*A + B, where B has no zeros. Subtracting off (10^1999)*A = (2^1999)*(5^1999)*A, we are left with B, which is a multiple of (2^1999) with no zeros in its decimal representation.

Hi Tomfr,You start from right to left, pushing the zero towards the left. Whereas, I was trying to push the zero towards the centre.I have a question. For the second iteration, when you look for the rightmost zero, do you look at N or ((10^K)+1)*N for the rightmost zero since you have already added (10^K)*N to N? I thought the multiple will just be the multiplication of a series of ((10^Ki)+1).Thanks.CK

Ok, ok, not only was there an error in my writing, but it was also incomprehensible altogether.And comparing it with Tomfr's solution, where given a number of the form 10^1999*A + B, where B has no zeros, 10^1999*A is subtracted off, the latter is certainly nicer.Tomfr, could you tell where does this problem come from.

xanuda,This problem was given to me by a friend and he wouldn't divulge its source. I guess it has to do with the year 1999 as I recently saw similar brainteasers using the number 2005, so maybe you'll manage to find a version of this problem based on that year (I used to cover a "brainteaser database" from UCSD but it has now closed).