This is an excellent problem, and I found it very difficult. Here is an attempt at a solution.

Suppose first that n is an odd number that is not a multiple of 5. Then n is co-prime to 10, so by Euler's totient theorem . If then . Thus N is a palindromic number that is a multiple of n.

Even for small values of n, this produces a huge number. For example, if n=21 then N is a number with 241 digits, consisting of 21 1s, each separated by 11 0s. Compare that with the smallest palindromic multiple of 21, which is 252.

Things get harder when n is divisible by a power of 2 or 5. Here's a sketch of how to handle powers of 2. Powers of 5 would be handled by a similar procedure. Of course, n cannot be a multiple of both 2 and 5 because we are told that it is not a multiple of 10.

So suppose that , where m is odd (and not a multiple of 5). Let be the number of digits in , and suppose for convenience that . Let p denote the number obtained from by reversing the order of its digits, and let .

It may be helpful to have an example at hand. Suppose that . Then k=4, , and (=16 with the digits reversed). Also, , and . So for this example, X is the number . This is palindromic, and it is a multiple of 16. But it is not a multiple of 3.

The idea of the rest of the proof is to add numbers of the form (each of which is congruent to 1 mod m) to X so as to make it a multiple of m.

In the case of the example, that has the effect of replacing 0s by 1s in some or all of the asterisked places in the number 61*0*0*16. In this case, the number 610000016 is congruent to 2 (mod 3). So we only need to replace one of the asterisks by a 1, leaving the others as 0s. In order to keep the number palindromic, we replace the middle asterisk by 1, finally getting the number 610010016 as a palindromic multiple of 48. (As with the previous example, there are much smaller palindromic multiples of 48, such as 8448.)

Having dealt with that example I don't have the stamina to try to write out the general proof. I hope that the idea of the procedure is clear.

I cut corners at one point by assuming that . If that is not the case then you simply replace by a multiple of that is greater than .

It's a shame that the case where n has factors of 2 or 5 is so messy. I hope someone can come up with a neater argument.