not really nice, but anyway not too hard, if one doesn't forget something at the end. ok, it are all numbers not divisible by 20. actually, it is clear that there is no alternating multiple of them since the last two digits are always even. so, let's first do powers of 2 and 5. in both cases start with the number 25252525...2525 for 5 with "enough" digits(or 101010...1010 for 2). in the k-th step, change the k-th digit such that the new number is divisible by $2^{k+1}$(respectively $5^{k+1}$) if the number is not divisible by that term before(where even digits stay even and odd digits stay odd). if inductively follows that this is actually possible, so we get a alternating number which is divisible by $2^n$(respectively $5^n$) and has an odd digit at the end. now, take a power of 2 times an odd number not divisible by 5. take the alternating number divisible by the power of 2 several times to get by fermat a number divisible by the number we want to. now, take (10 times a) power of 5 times an odd number not divisible by 5. take the number divisible by to the power of 5 several times to get a number divisible by the power of 5 times the odd number not divisible by 5. add a 0 at the end if the number is divisible by 10. so, we have everything since numbers divisible by 20 have no alternating multiple. i hope the main argument gets clear. Peter

I think this problem is very similar to the 'wobbly number' problem from ISL 1994. Do you agree with me?

mozilla: I have in front of eyes the five problems of the Israel Mathematical Olympiad 1994. I find no similarities with IMO2004/6. To which problem do you refer? Kantor.

ISL means Imo short-list, not Israel Pierre.

Oops, I am sorry!! ISL is the code for Isreal at IMOs

ISL 1994 http://www.kalva.demon.co.uk/short/sh94.html A wobbly number is a positive integer whose digits are alternately zero and non-zero with the last digit non-zero (for example, 201). Find all positive integers which do not divide any wobbly numbers.

I just want to say this problem was proposed by Iran

Peter Scholze wrote: in the k-th step, change the k-th digit such that the new number is divisible by $2^{k+1}$(respectively $5^{k+1}$) if the number is not divisible by that term before(where even digits stay even and odd digits stay odd). if inductively follows that this is actually possible, so we get a alternating number which is divisible by $2^n$(respectively $5^n$) and has an odd digit at the end. I don't follow the induction step... (is it an induction step?)

I can't believe that such easy problem is a number 6 at IMO! I solved it in 15 minutes!

Worse still, it's very unoriginal. (I solved this problem by using the same idea in ISL 1994.) IMO should never use unoriginal problems.

mozilla wrote: Worse still, it's very unoriginal. (I solved this problem by using the same idea in ISL 1994.) IMO should never use unoriginal problems. I agree. And by looking at the cut offs for the medals this year it seems to be one of the easier IMO in recent years.

There are two parts to the solution: to construct the alternating end bit $c$ digits long which divides $2^c$ or $5^c$ (because $c+1$th digit and up, it'll have a place value of $10^c$), and to construct the front bit such that the whole number divides any number $k$ coprime to 2 and 5, so that the whole number divides $k*2^c$ or $k*5^c$. For $2k*5^c$ case, just add a 0 behind the $k*5^c$ case. To construct the end bit, its all basically the same idea, but it will require a bit of modification. the easiest case is the $5^c$ case. Start with $x = 5^c$. Find the first time is not alternating. let say its in the $k$th digit place. If $k<c$, add $5^c*10^k$ to $x$. It will change the parity of the $k$th digit place, such that it will alternate. Repeat until $k\geqq$. Then one can discard all the digits in front, and the end bit c digits long is what you want. In the $2^c$ case, start with $x=2^c$. Find the first time it is not alternating. let say its in the kth digit place. If $k<c$, add $5^c \cdot 10^{k-1}$ to $x$. It will not change the parity of the (k-1)th digit place. There are two subcases. if the second last digit of $2^c$ is even, enough adding of $5^c \cdot 10^{k-1}$ will create a carry of 1, such that the parity of the kth digit will change, such that it will alternate. if the second last digit of $2^c$ is odd, you can add $5^c \cdot 10^{k-1}$ until there is no carry of 1 (it cannot always carry, otherwise the $(k-1)$th digit, bounded $\geq 0$ will have decrease monotonically). So do it until $k\geq c$. Then one can discard all the digits in front, and the end bit c digits long is what you want. To get the front to be any mod k you want. let $10^m = 1 \pmod k$. then $10^{2m} = 1 \pmod k$. The idea is to create an alternating j $2m$ digits long, first digit even, last digit odd. This will ensure that wherever you put you jjjjjjj..., not only is this alternating, but each "j" would contribute the -same- amount $\pmod k$. For example, let first $j$ be on the $p$th digit. the next $j$ will be on the $(2m+p)$th digit. The next $j$ will be on the $(4m+p)$th digit and so on. So jjjj...j, will contribute $j \cdot 10^p + j \cdot 10^{2m+p}+\cdots +j \cdot 10^{2(a-1)m+p} = aj \cdot 10^p \pmod k$. If $j$ is coprime to $k$, since $10^p$ is coprime to $k$, we can vary a to reach any mod we like. so we look at the end bit, take it $\pmod k$, and we vary a such that the sum is $0 \pmod k$. Thus the existence of $j$ solves the problem. So let $j = \frac{10^{2m} - 1}{99} + 2t \cdot 10^{2m-1}$, $t=1,2,3$ and $t \neq (1 - 10^{2m}) \cdot (198 \cdot 10^{2m-1})^{-1} \pmod 3$ and $\pmod 11$ thus 3 and 11 both do not divide $j$. This is in the form of 2010101010..., or starting with 4 or 6. First we note that $$\gcd \left( \frac{10^{2m} - 1}{99}, 2t \cdot 10^{2m-1} \right) \mid \gcd(10^{2m} - 1, t \cdot 10^{2m}) \mid 3$$ (it cannot be 2 because the former number is odd). Thus, since if $\gcd (a,b) = c$, then $\gcd (a+b,a) \mid c$ and $\gcd (a+b,99a)|99c$, thus $\gcd (j, 10^{2m} - 1) \mid 297$ but 3 or 11 does not divide the former. thus. $\gcd (j , 10^{2m} - 1) = 1$ and since $k \mid 10^{2m} - 1$, $\gcd (j, k) = 1$. As needed. So the proof is basically building the back bit. Then if the first digit is even, add jjjj...jjj in front such that it is $0 \pmod k$, and if the first digit is odd, add a 0, then add a jjj...jjj in front such that it is $0 \pmod k$.

and here is my soln 6.... it looks so ugly...

hmm, you just made my j irrelavant

mozilla wrote: Worse still, it's very unoriginal. (I solved this problem by using the same idea in ISL 1994.) IMO should never use unoriginal problems. I can't agree it anymore. I saw the problem before: Prove that there exists a number n which has k digits such that 5^k|n, and all of the k digits are odd. I think it's just the same with the problem.

Dawsen wrote: Prove that there exists a number n which has k digits such that 5^k|n, and all of the k digits are odd. That was from USAMO 2003/1

billzhao wrote: Dawsen wrote: Prove that there exists a number n which has k digits such that 5^k|n, and all of the k digits are odd. That was from USAMO 2003/1 According to what you have said above, it should be a well-known and unoriginal problem. Didn't any leaders say it when they chose the problem? Although I solved the problem and thus just at the gold line, I think it's quite not good, because I lost a chance to try my best.

Yes. Zuming Feng, the USA teamleader, argued strongly against the problem for exactly those reasons. However, the other leaders thought "he doesn't like it... it must be too hard for the US team", and picked it anyway. Quite ironic, because it was on that problem that we gained our advantage over other teams. And yes, I feel the same way about that problem. "Dawsen wrote: Didn't any leaders say it when they chose the problem? Although I solved the problem and thus just at the gold line, I think it's quite not good, because I lost a chance to try my best.

Alison wrote: Yes. Zuming Feng, the USA teamleader, argued strongly against the problem for exactly those reasons. However, the other leaders thought "he doesn't like it... it must be too hard for the US team", and picked it anyway. Quite ironic, because it was on that problem that we gained our advantage over other teams. And yes, I feel the same way about that problem. "Dawsen wrote: Didn't any leaders say it when they chose the problem? Although I solved the problem and thus just at the gold line, I think it's quite not good, because I lost a chance to try my best. The problem is that there are not many number theorists in the Jury, and possibly also not in the problem selection committee. That is why they do not always pick the best number theory problems for the IMO. It is not the first time that the number theory problem in the IMO is quite unoriginal and can be solved in a rather straightforward way.

I agree , problem 6 was not difficult , usually problem 6 is the hardest ... However if somebody didn't come up with the answer quite fast I'm not sure whether it's so obvious , my solution to this problem is close to kueh's , the difference is that I checked the situation for n where $gcd(n,10)=1$ and then just combined $2^k,5^l,n$ , I hope it will appear at the official Polish mathematical olimpiade website. Another problem is to write down the solution in the easiest way .

Still, compared to some of the recent #6's in the IMO, this was definitely a disappointment.

Peter Scholze wrote: not really nice, but anyway not too hard, if one doesn't forget something at the end. ok, it are all numbers not divisible by 20. Peter Can you show how did you get this one Abdurashid

"IMO Compendium" has a slightly different solution for the case n = 2^r * k, where (k, 10) = 1. There is a claim that there exists an alternating number with 2r digits that is divisible by 2^(2r + 1). However, for the (r + 1)th step, one chooses N(r+1) = N(r) + m*10^(2r), where m can be 10, 12, 14, 16. But this is possible only when the first digit of N(r) is odd, and we don't know if it is odd or even. So, is the proof given by Djukic wrong?

If $20 \mid n$, then clearly $n$ has no alternating multiple since the last two digits are both even. We will show the other values of $n$ all work. The construction is just rush-down do-it. The meat of the solution is the two following steps. Claim: [Tail construction] For every even integer $w \ge 2$, there exists an even alternating multiple $g(w)$ of $2^{w+1}$ with exactly $w$ digits (leading zeros allowed). there exists an even alternating multiple $h(w)$ of $5^{w}$ with exactly $w$ digits (leading zeros allowed). (One might note this claim is implied by the problem, too.) Proof. We prove the first point by induction on $w$. If $w = 2$, take $g(2) = 32$. In general, we can construct $g(w+2)$ from $g(w)$ by adding some element in $$10^w \cdot \{10, 12, 14, 16, 18, 30, \dots, 98\}$$ to $g(w)$, corresponding to the digits we want to append to the start. This multiple is automatically divisible by $2^{w+1}$, and also can take any of the four possible values modulo $2^{w+3}$. The second point is a similar induction, with base case $h(2) = 50$. The same set above consists of numbers divisible by $5^w$ and covering all residues modulo $5^{w+2}$ Careful readers might recognize the second part as essentially USAMO 2003/1. $\blacksquare$ Claim: [Head construction] If $\gcd(n,10) = 1$, then for any $b$, there exists an even alternating number $f(b \bmod n)$ which is $b \pmod n$. Proof. A standard argument shows that $$10 \cdot \frac{100^m-1}{99} = \underbrace{1010\dots10}_{m\ 10\text{'s}} \equiv 0 \pmod n$$ for any $m$ divisible by $\varphi(99n)$. Take a very large such $m$, and then add on $b$ distinct numbers of the form $10^{\varphi(n)r}$ for various even values of $r$; these all are $1 \pmod n$ and change some of the $1$'s to $3$'s. $\blacksquare$ Now, we can solve the problem. Consider three cases: If $n = 2^k m$ where $\gcd(m,10) = 1$ and $k \ge 2$ is even, then the concatenated number $$10^k f\left( -\frac{g(k)}{10^k} \bmod m \right) + g(k)$$ works fine. If $n = 5^k m$ where $\gcd(m,10) = 1$ and $k \ge 2$ is even, then the concatenated number $$10^k f\left( -\frac{h(k)}{10^k} \bmod m \right) + h(k)$$ works fine. If $n = 50m$ where $\gcd(m,10) = 1$, then the concatenated number $$100 f\left( -\frac{1}{2} \bmod m \right) + 50$$ works fine. Since every non-multiple of $20$ divides such a number, we are done.

For this solution, the meaning $n$-digit will allow leading $0$s, so the number $35$ can be considered to be $7$-digit. Lemma 1: Let $r$ be a positive integer. Then, there exists an alternating $r$-digit multiple of $2^r$. Also, there exists an odd alternating $r$-digit multiple of $5^r$. Proof: First, we solve the problem for $2^r$. We're actually first show that for odd $r$, there exists an alternating $r$ digit number that has $\nu_2$ exactly equal to $r$. We proceed by induction, with the base case of $r=1$ being obvious, as we can take $2$. Now suppose we have an $r$-digit alternating multiple of $2^r$, call it $x2^r$ (again, $r$ is odd). Note that $x$ is odd, since $\nu_2(2^rx)=r$. For any alternating odd two digit number $a$, we can construct the number $y=10^ra+2^rx$, which will still be alternating and will have now have exactly $r+2$ digits. We see that $$y=2^r(5^ra+x).$$ We want to pick an $a$ such that $\nu_2(5^ra+x)$, or that $5^ra+x\equiv 4\pmod{8}$. Note that $a$ covers everything odd mod $8$, so we pick $a\equiv 5^{-r}(4-x)\pmod{8}$ to finish. Now, to solve the problem for even $r$, pick an alternating number with $r+1$ digits that is divisible by $2^{r+1}$, and simply delete the first digit. Since this removes an even number times $10^r$, the remaining number is divisible by $2^{r+1}$, so it is certainly divisible by $2^r$. Let's now solve the problem for $5^r$. We will induct on $r$, with the base case of $r=1$ being obvious as we can pick $5$. Now, suppose we have an odd alternating $r$-digit multiple of $5^r$, call it $5^rx$. Depending on the parity of $r$, we can consider the number $y=5^rx+10^rd$ where either $d\in\{0,2,4,6,8\}$ or $d\in\{1,3,5,7,9\}$. Regardless, both these sets are complete residue sets mod $5$, so we can choose $d$ such that $x+2^rd$ is divisible by $5$, which completes the induction, and thus the proof of the lemma. $\blacksquare$ Lemma 2: Suppose $\gcd(n,10)=1$. Then, for any integer $m$, there exists an even alternating number $x$ and an odd alternating number $y$ such that $x\equiv y\equiv m\pmod{n}$. Proof: Let $\alpha_0$ be the $2n\phi(n)$ digit number whose digits alternate $1010\cdots 10$ and let $\alpha_1$ be the $2n\phi(n)$ digit number whose digits alternate $0101\cdots 01$. Note that $$\alpha_1=\sum_{k=0}^{n\phi(n)}100^k\equiv n\sum_{k=0}^{\phi(n)}100^k\equiv 0\pmod{n}$$ and $\alpha_0=10\alpha_1$ is similarly divisible by $n$. Now, let $\beta_0=\alpha_0+20$ and $\beta_1=\alpha_1+2$, which we can see are both alternating numbers with $2n\phi(n)$ digits, but now $\gcd(n,\beta_0)=\gcd(n,\beta_1)=1$. Suppose we concatenate $\beta_i$ with itself $g$ times. Since the number of digits of $\beta_i$ is a multiple of $\phi(n)$, by the same Euler's theorem argument, we see that the number we get is $g\beta_i\pmod{n}$. Since $\gcd(\beta_i,n)=1$, by varying $g$, we are able to hit every residue class mod $n$, for each $i$, as desired. This completes the proof of the lemma. $\blacksquare$ Now, suppose $n=2^rN$ where $\gcd(N,10)=1$. Pick $x$ by Lemma 1 such that $x$ has $r$ digits, is alternating, and is divisible by $2^r$. Now, pick $y$ alternating and a multiple of $N$ such that $y\equiv -10^{-r} x\pmod{N}$, which we can do by Lemma 2, and let $z=x+10^ry$. Choose the parity of $y$ such that $z$ is alternating, and note that $2^r\mid z$ and $N\mid z$, so $N\mid z$, which shows that $n$ has an alternating multiple. Now, suppose that $n=5^rN$ where $\gcd(N,10)=1$. We can repeat the exact same argument as above, but we can further enforce that $x$ is odd, so we see that $n$ has an odd alternating multiple. The only case left is when $10\mid n$. If $n=10k$, where $k$ is odd, then $k=5^rN$ where $\gcd(N,10)=1$. We can pick an odd alternating multiple of $k$ by the above, so $10$ times that is still alternating. Now, we've shown that if $20\nmid n$, then $n$ has an alternating multiple. However, it's clear that any multiple of $20$ has its last two digits even, so $20\mid n$ has no alternating multiple. Thus, the answer is $\boxed{20\nmid n}$.

Another terrible write up The answer is all numbers $n$ which is not a multiple of $20$. For all odd $(n,5) = 1$, consider the set $S$ the set of values $a_n$ can obtain where $$a_0 = 1$$ $$a_n = 100a_{n - 1} + 1 \ \forall n \in \mathbb{N}$$ There must exists $k$ such that $n | a_k$. To prove this consider all elements of $S$ modulo $k$. Since $|S| = \infty$,then there must exists two elements $a_i$ and $a_j$ such that $a_i \equiv a_j \ (\text{mod} \ k )$. Therefore, $a_{i - j} \equiv 0 \ (\text{mod} \ k)$ For the case $\nu_2(x) \ge 2$ and $\nu_5(x) \ge 1$, this means that $x$ is divisible by $20$, which makes the last two digits even. Now, we need to consider two cases. $\textbf{Case 01.}$ $\nu_2(x) = 1, 0$ and $\nu_5(x) \ge 1$. For this case, we just need to prove that there exists an alternating multiple of $5^a$ that ends in an odd number. We'll prove this by induction. For $a = 1, 2, 3$, $125$ clearly satisfies. Suppose that $w$ is an $k$ digit number that is divisible by $5^k$. We'll construct an additional digit in front of $w$ such that it is divisible by $5^{k + 1}$. Let $w = 5^k \cdot m$. Let the additional digit be $c$. Now, notice that $$5^{k + 1} | 10^k c +5^k m$$ $$5 | 2^k c + m$$ Let $2^k c \equiv nc \ (\text{mod} \ 5)$. Notice that $n$ couldn't be $0$ mod $5$ as $2^k$ is not divisible by $5$. Therefore, we have $5 | nc + m$, notice that there are two solution $c$, which is $-\frac{m}{n}$ and $-\frac{m}{n} + 5$, both of which satisfy the condition, but different in parity. So we could choose the satisfying digit and so on. Therefore, this case is finished. $\textbf{Case 02.}$ $v_2(x) \ge 1$ and $\nu_5(x) = 0$. We'll prove that such we can construct an $\textit{alternating}$ multiple of $2^a$. We'll prove this by induction. We'll prove that we can control $\frac{10^{k - 1} x + 2^{k - 1} \cdot m}{2^k}$ to be either odd or even every time. Notice that if this and $\frac{10^{k - 1} \cdot (x \pm 2) + 2^{k - 1} \cdot m }{2^k} = \frac{10^{k - 1} x + 2^{k - 1} \cdot m}{2^k} \pm \text{odd}$ will be different in parity. $256$ handles the case of $a = 1, 2, 3$. Now, as the same way as before, suppose there exists $k$ such that the number is $k$ digit and an alternating multiple of $2^k$. Now, to construct the next digit, $$2^k | 10^{k - 1} x + 2^{k - 1} \cdot m$$ We could find a suitable $x$ by the previous claim. Now, we are left to construct the number $n = 5^a \cdot x$ or $n = 2^a \cdot y$ where $\nu_5(x) = \nu_2(y) = 0$. Notice that the above method works for $a_{n} = 10^k a_{n - 1} + 1$ as well. Since there exists an alternating multiple of $5^a$ with $a$ digit and there exists an index $m$ such that $x | a_m$. Therefore, if this alternating multiple of $5^a$ starts and end with different parity, just consider $k = a$. Otherwise, consider $k = a + 1$. Then multiply the two numbers. Now, for the case $n = 2^a \cdot y$. We can always make sure that the alternating multiple of $2^a$ must start with an odd number (just take the alternating multiple of $2^{\text{even}}$ with even digits. There must exists an index $m$ such that $y|a_m$ as well. Therefore, take $k = a + 1$, if $a$ is odd and take $k = a$ if $a$ is even. Then multiply the two numbers. The case of $n = 5^a \cdot 2x$ is similar to $5^a \cdot x$, just add an extra '0' at the end of the number, we are hence finished.

Solved with eisirrational, goodbear, Th3Numb3rThr33. The answer is $20\nmid n$; it is straightforward to show no multiple of $20$ is alternating. Lemma: [Powers of five] For each $k$, there is an odd $k$-digit alternating multiple of $5^k$. Proof. Induct on $k$, starting with $5$. To construct a $(k+1)$-digit multiple of $5^{k+1}$, there are five choices for the leading digit before appending the $k$-digit multiple of $5^k$; one of these must work. $\blacksquare$ Lemma: [Powers of two] For even $k$, there is an even $k$-digit alternating multiple of $2^{k+1}$. Proof. Repeat the above proof, but add two digits at a time. $\blacksquare$ Claim: [Relatively prime with 10] For every $m\perp10$ and $r$, there is an even alternating number and an odd alternating number equivalent to $r$ modulo $m$. Proof. First we show odd alternating numbers are surjective modulo $m$. Define $$f(k):=\underbrace{1010\cdots1}_{k\text{ ones}}=1+10^2+\cdots+10^{2(k-1)}=\frac{10^{2k}-1}{99}.$$ Then take $\varphi(99m)\mid k$ to achieve $r=0$. To achieve $r\equiv2j\pmod m$, take $$f\big(j\varphi(99m)\big)+2\cdot\left(10^{\varphi(99m)}+10^{2\varphi(99m)}+\cdots+10^{j\varphi(99m)}\right);$$ that is, take $f(k)$ where $k$ is a sufficiently large multiple of $\varphi(99m)$, and turn some of the 1's into 3's. To show even alternating numbers are surjective modulo $m$, just take each odd alternating number and multiply by 10. $\blacksquare$ Finally, we need to settle $n$ not relatively prime with 10: in what follows, $m\perp10$. An odd multiple of $5^{\varphi(99m)}\cdot m$ is achieved by taking $10^{\varphi(99m)}A+B$, where $A$ is odd and chosen so that the expression is $0\pmod m$, and $B$ is an odd $\varphi(99m)$-digit multiple of $5^{\varphi(99m)}$. An even multiple of $2^{\varphi(99m)}\cdot m$ is achieved by taking $10^{\varphi(99m)}A+B$, where $A$ is even and chosen so that the expression is $0\pmod m$, and $B$ is an even $\varphi(99m)$-digit multiple of $2^{vphi(99m)}$. An even multiple of $2\cdot5^{\varphi(99m)+1}\cdot m$ is achieved by taking the construction for an odd multiple of $5^{\varphi(99m)}\cdot m$ and multiplying by $10$. It is easy to see that any $20\nmid n$ has a multiple that is either of the form $5^{\varphi(99m)}\cdot m$, $2^{\varphi(99m)}\cdot m$, or $2\cdot5^{\varphi(99m)+1}\cdot m$, for some $m\perp10$, so we are done.

First, any multiple of 20 does not divide an alternating number since the last two digits are both even. Call a number good if it divides some alternating number. We claim that all non-multiples of 20 are good. Claim 1. For any integer $k\ge 1$, any integer $n$ coprime to 10 divides a number of the form $$1\underbrace{0\dots 0}_{\text{$k$ zeros}}1\underbrace{0\dots 0}_{\text{$k$ zeros}}1\dots \underbrace{0\dots 0}_{\text{$k$ zeros}}1.$$ Specifically taking $k=1$ we see that any integer coprime to 10 is good. Proof. By Euler's theorem there exists a positive integer $m$ satisfying $(10^{k+1}-1)n\mid (10^{m(k+1)}-1)$, so $$n \mid \frac{10^{m(k+1)}-1}{10^{k+1}-1}$$ which is in the desired form. Claim 2. Any number of the form $2^n$, $5^n$, or $2\cdot 5^n$ divides an alternating number whose first (can be 0) and last digits have different parity. Proof. We will first prove this for $2^n$ using induction. Start from $A_1=16$, which is divisible by $2^3$. Suppose we have an alternating number $A_n$ with $2n$ digits that's divisible by $2^{2n+1}$, we add a two-digit number in $\{10,12,14,16,18\}$ to the front of $A_n$ to form $A_{n+1}$. Since $$A_{n+1}=\{10,12,14,16,18\}\cdot 10^{2n} + A_n = 2^{2n+1}(5^{2n}\cdot \{5,6,7,8,9\} + \text{something}),$$ it's possible to choose an element in the set to make the number in parenthesis divisible by 4. This gives $2^{2n+3}\mid A_{n+1}$, and the first and last digits of $A_{n+1}$ are of different parity. This completes the induction. The process is similar for the $5^n$ case: start from $A_1=5$, which is divisible by $5^1$. Suppose we have an alternating number $A_n$ with $n$ digits that ends with an odd number, and $5^n\mid A_n$, we add a residue modulo 5 to the front of $A_n$ to form $A_{n+1}$. Since $$A_{n+1}=\{0,1,2,3,4\}\cdot 10^{n} + A_n = 5^{n}(2^{n}\cdot \{0,1,2,3,4\} + \text{something}),$$ it's possible to choose an element in the set to make the number in parenthesis divisible by 5. Furthermore since there are two digits of distinct parity for each residue mod 5, we can choose $A_{n+1}$ to be alternating. Finally since every $A_i$ ends with 5, we can add a leading zero if necessary. Finally we consider the $2\cdot 5^n$ case. The above paragraph enables us to take an alternating $A_{n-1}$ divisible by $5^{n-1}$ that ends with an odd number. Consider $10A$ and add a leading 1 if necessary. Return to the original problem. Write $n$ as $pq$ where $\gcd(p,10)=1$ and $q\in\{2^k,5^k,2\cdot 5^k\}$. By Claim 2, we can find an alternating $A$ such that $q\mid A$ and the first and last digits of $A$ are of different parity. Suppose $A$ has $a$ digits including leading zero. Take $k=a-1$ in Claim 1 to get a number $B$ of the form $$1\underbrace{0\dots 0}_{\text{$a-1$ zeros}}1\underbrace{0\dots 0}_{\text{$a-1$ zeros}}1\dots \underbrace{0\dots 0}_{\text{$a-1$ zeros}}1.$$ Now, since $p\mid B$, $q\mid A$, and $AB$ is alternating, we are done.

Fun to solve but not fun to write up. The answer is all $n$ such that $20\nmid n.$ Note that all multiples of $20$ have even ones and tens digits, so all multiples of $20$ do not have an alternating multiple. Say a number is $\emph{primitive}$ if it is of the form $$1\underbrace{00\dots 00}_{w-1\text{ zeroes}}1\underbrace{00\dots 00}_{w-1\text{ zeroes}}1\dots 1$$ for some integer $w\ge 2.$ Let the $\emph{width}$ of a primitive number be the value of $w$ and the $\emph{length}$ be the number of digits equal to $1.$ $\textbf{Claim: }$ All powers of $5$ have an alternating multiple. $\textbf{Proof: }$ Induct on $\nu_5(n).$ For the base case, note that $5$ is an alternating multiple of itself. Assume the claim is true for $n=5^k.$ Then, there exists a positive integer $c$ and an alternating number $\overline{a_{k-1}a_{k-2}\dots a_{0}}$ such that $$5^{k}c=\overline{a_{k-1}a_{k-2}\dots a_{0}}.$$ Now let $a_k$ be a one-digit positive integer such that $$a_k\equiv\frac{-c}{2^k}\pmod{5},$$ $$a_k\equiv 1-a_{k-1}\pmod{2}.$$ We have $$\frac{\overline{a_{k}a_{k-1}\dots a_{0}}}{5^k}=c+2^{k}a\equiv 0\pmod{5}.$$ Therefore, $\overline{a_{k}a_{k-1}\dots a_{o}}$ is an alternating multiple of $5^{k+1},$ as desired. $\blacksquare$ $\textbf{Claim: }$ All numbers of the form $2\cdot 5^k$ have an alternating multiple. $\textbf{Proof: }$ Let $x$ be an alternating multiple of $5^k.$ If the last digit of $x$ is even, then $x$ is an alternating multiple of $2\cdot 5^k,$ and if the last digit of $x$ is odd, then $\overline{x0}$ is an alternating multiple of $2\cdot 5^k.$ The claim follows. $\blacksquare$ $\textbf{Claim: }$ All powers of $2$ have an alternating multiple. $\textbf{Proof: }$ We prove the following stronger claim: For all positive integers $d,$ there exists a $d$-digit alternating number $x$ such that either (1) $\nu_2(x)=d$ and $x$ starts with an even digit or (2) $\nu_2(x)>d$ and $x$ starts with an odd digit. To show this, we will induct on $d.$ Assume the claim is true for $d=k.$ Then, there exists an alternating number $\overline{a_{k-1}a_{k-2}\dots a_0}$ and a positive integer $c$ such that $$2^{k}c=\overline{a_{k-1}a_{k-2}\dots a_{0}}.$$ If $c$ is odd and $a_{k-1}$ is even, then let $a_k$ be a one-digit integer such that $a_k+c\equiv 0\pmod{4}.$ If $c$ is even and $a_{k-1}$ is odd, then let $a_k$ be a one-digit integer such that $a_k+c\equiv 2\pmod{4}.$ It is easy to check that the desired conditions hold for $\overline{a_{k}a_{k-1}\dots a_0}.$ $\blacksquare$ $\textbf{Claim: }$ If $\gcd(n,10)=1,$ then $n$ has primitive multiples of arbitrarily large even width. $\textbf{Proof: }$ Let $m$ be any multiple of $\varphi(n),$ which is even. Let $t$ be the primitive number with width $m$ and length $n.$ We have $$t=1+10^m+\dots+10^{(n-1)m}\equiv n\equiv 0\pmod{n}.$$ Therefore, $n\mid t$ regardless of $m,$ so we are done. $\blacksquare$ Now fix a positive integer $n$ not divisible by $20.$ Write $n=rs,$ where $r=2^{\nu_2(n)}5^{\nu_5(n)}.$ Let $a$ be an alternating multiple of $r,$ and let $b$ be a primitive multiple of $s$ with sufficiently large width (say $w$). Let $a'$ be an alternating number ending in $a$ with exactly $w$ digits. Since $w$ is even, $a'\cdot b$ is alternating. Additionally, since $r\mid a'$ and $s\mid b,$ we know $n\mid a'\cdot b.$ Thus, we have constructed an alternating multiple of $n,$ as needed.

Bad writeup, oh well The only $n$ that do not have such a multiple are where $20 | n$; it is easy to see that the last two digits are always even. I will prove that not only does every other number has an alternating multiple, but the number of digits in that multiple is even. Call a alternating number with even number of digits "strong-alternating". Lemma: If $n$ is a number such that neither $2$ nor $5$ divide $n$, and $d$ is also an integer, we can find some $r$ such that $n | \frac{10^{rd} - 1}{10^{d} - 1}$. Proof: For each $p_{i} | n$, let $e_{i} = v_{p_{i}}(n)$. Let $n$ have $l$ prime divisors. Then, take $$r = \prod_{i = 1}^{l} (p_{i}-1)p_{i}^{e_{i}}$$ First, observe that since $p_{i} - 1 | r$, we have $p_{i} | 10^{rd} - 1$. For each $p_{i}$, if $p_{i} | 10^{d} - 1$ then $v_{p}(10^{rd} - 1) - v_{p}(10^{d} - 1) = v_{p}(r) \geq e_{i}$. Otherwise, $v_{p}(10^{rd} -1) = v_{p}(10^{p_{i} - 1}) + v_{p}(r/(p_{i} - 1)) \geq e_{i}$. Thus, we have that this $r$ works. First we will prove numbers in the form of $5^{k}$ have (which also proves numbers in the form of $2\cdot 5^{k}$) even strong alternating multiples with more than $k+1$ digits. We do this via induction. Our base case is $k = 1$, where we take $1050$ as the even strong alternating multiple. Now, assume it was true for $5^{k}$, we will prove it for $5^{k+1}$. Let $N$ be the even strong alternating multiple of $5^{k}$. If $v_{5}(N) > k$, we are done. Otherwise, let $N = 5^{k}\cdot r$. Consider the digit that is in the $10^{k}$ place. To keep this number as strong alternating, there are $4$ other values it could take, and those $4$ values will result in adding $2\cdot 10^{k}, 4\cdot 10^{k}, 6\cdot 10^{k}, 8\cdot 10^{k}$ to $N$ modulo $5^{k+1}$. One of these will result in $N$ being $0\mod 5^{k+1}$, because we just need $r + 2, r + 4, r + 6, r + 8\equiv 0\mod 5$, which is true for one of them. Thus, we can create a strong-even alternating multiple of $5^{k+1}$, and then just add two digits at the beginning of the number (it will still be divisible by $5^{k+1}$). The above also proves that $2\cdot 5^{k}$ also satisfies the problem's condition. We will now prove that $n = 2^{k}$ also have strong alternating multiples with more than $k + 1$ digits via induction. Our base case is $k = 1$, and we can take $n = 1212$. Now, assume it is true for $k$, and let $N$ be that multiple. If $v_{2}(N) > k$ we are done, otherwise let $N = 2^{k}\cdot r$. Now, if the digit in the $10^{k}$ place is not $8$ or $9$, just add $10^{k}$ to $N$ (which will make it divisible by $2^{k+1}$), otherwise subtract $2^{k}$. This is still strong-alternating, and now just add two digits to the beginning of the number, which completes our proof that $2^{k}$ works. Finally, we will prove it for all other numbers. Our base case is $n = 1$, which has an strong alternating multiple of $12$. Now, for our inductive step, assume all $i$ such that $i < n$ and $20\not | i$ has a strong-alternating multiple, and assume $n$ is not a power of $5$, twice a power of $5$, or a power of $2$ (we already proved it for those cases). Now, if either $2$ or $5$ divides $n$, then let $n = 2\cdot 5^{t}\cdot C$, and let $M$ be the strong-alternating multiple of $2\cdot 5^{t}$ and let it have $d$ digits. Then, consider the number $$M(10^{rd} + 10^{(r-1)d} + \ldots + 10^{d} + 1) = M\cdot \frac{10^{(r+1)d}-1}{10^{d}-1}$$ Since $M$ has an even number of digits, it's beginning and ending digits have different parity, so the above number is still strong multiplying. Using our lemma, we can choose some $r + 1$ such that the above number is a multiple of $C$ (since $5, 2\not | C$), which means for that $r$ the above number is a strong alternating multiple of $n$. Otherwise, assume that $2, 5 \not | n$. Consider $$12\cdot(10^{2k} + 10^{2(k-1)} + \ldots + 10^{2} + 1) = 12\cdot \frac{10^{2(k + 1)} - 1}{10^{2} - 1}$$ Choose some $k$ such that the above number is a multiple of $n$ (by our lemma), which gives the strong alternating multiple. Therefore, we are done with our induction, and we conclude that for all $20\not | n$ there exists such a multiple.

Ok then @above. Solution with awang11 and VulcanForge. The idea is to abuse the fact $$\frac{100^k-1}{99}=1010101\dots.$$ The solutions are all $n$ which do not end with $k0_{10}$ where $k$ is even: that is, all $n$ not divisible by $20$. It is trivial to see that if $20\mid n$, there is no alternating multiple of $n$. First, we provide a proof in the case that $5\nmid n$. Let $\nu_2(n)=c$. Then we construct an alternating number $N$ with an even number of digits $d$ divisible by $2^c$. Let $d=c$. Start with the number $$\underbrace{10101010\dots 10}_{10\mbox{ occurs }c\mbox{ times}}.$$ Then add $+2$ to the $1$s digit if the number is not already divisible by $4$, next add $+2$ to the $10$s digit if the number is not already divisible by $8$, and so on. Since the initial number has $2c$ digits, we will eventually get such $N$. Then consider the numbers $$N\cdot \frac{10^{kd}-1}{10^d-1}$$ and use Euler's Totient Theorem on the part of $n$ not divisible by $2$. In the case that $5\mid n$, proceed similarly with $\nu_5(n)=c$, and adding one of $+0,+2,+4,+6,+8$ to each digit as necessary. Remark that the approach in this case also preserves whether $2$ divides the number.

We claim that all positive integers $n$ except multiples of $20$ have a multiple that is alternating. If $n$ is a multiple of $20$, then the units digit is $0$ and the tens digit is a multiple of $2$, so both digits are even. Now, we will prove that if $20\nmid n$, then there is a multiple of $n$ that is alternating. We claim that there exists a $2k$ digit alternating integer that is a multiple of $2^{2k+1}$ and there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$. We will prove this by induction. Base Case: $k=1$ We can let the number be $16$. Inductive Step: Let $a$ be a $2k-2$ digit alternating number such that $2^{2k-1}\mid a$. Since $a$ is even, this means that the first digit of $a$ is odd. Let $b\cdot2^{2k-1}\equiv a\pmod{2^{2k+1}}$, where $b\in\{0,1,2,3\}$. Let $x=16-2b$. We see that $x$ is alternating, so the number $x\cdot10^{2k-2}+a$ is also alternating. We also have $x\equiv-2b\pmod8$. Since $a\equiv b\cdot2^{2k-1}\pmod{2^{2k+1}}$, this means that we have $$\begin{align*} x\cdot10^{2k-2}+a&\equiv x\cdot10^{2k-2}+b\cdot2^{2k-1}\pmod{2^{2k+1}}\\ &\equiv2^{2k-2}\left(x\cdot5^{2k-2}+2b\right)\pmod{2^{2k+1}}\\ &\equiv2^{2k-2}\left(-2b\cdot5^{2k-2}+2b\right)\pmod{2^{2k+1}}\\ &\equiv -b\cdot2^{2k-1}\left(5^{2k-2}-1\right)\pmod{2^{2k+1}}.\end{align*}$$ Since $4\mid5^{2k-2}-1$, this means that $x\cdot10^{2k-2}+a\equiv0\pmod{2^{2k+1}}$, so $x\cdot10^{2k-2}+a$ is a $2k$ digit alternating number that is a multiple of $2^{2k+1}$. Now, we will prove that there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$. Base Case: $k=1$ We can let the number be $0$. Inductive Step: Let $a$ be a $k-1$ digit alternating number such that $2\cdot5^{k-1}\mid a$. Let $S$ be the set of digits such that $x\cdot10^{k-1}+a$ is alternating. We see that either $S=\{0,2,4,6,8\}$ or $S=\{1,3,5,7,9\}$. In each possible set, each $\mod5$ residue appears exactly once. Let $a=2\cdot5^{k-1}\cdot b$. Then, $x\cdot10^{k-1}+a=2\cdot5^{k-1}\left(x\cdot2^{k-2}+b\right)$. Therefore, there exists an $x$ such that $2\cdot5^k\mid x\cdot10^{k-1}+a$, so there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$. If $k$ is even, then $0\not\in S$, so it has exactly $k$ digits. Now, let $n=2^a\cdot5^b\cdot m$. Then, if $20\nmid n$, then $a<2$ or $b=0$. If $b=0$, then there exists a $2a$ digit alternating integer $x$ that is a multiple of $2^{2a+1}$. Consider the sequence $a_i=x\cdot\frac{10^{2ai}-1}{10^{2a}-1}$. Then, the decimal representation of $a_i$ is the result when $x$ is written $i$ times. For any prime $p$ that divides $n$, if $p\mid10^{2a}-1$, then $\nu_p\left(10^{2ai}-1\right)=\nu_p\left(10^{2a}-1\right)+\nu_p(i)$, so $\nu_p(a_i)=\nu_p(x)+\nu_p(i)\geq\nu_p(i)$. Therefore, there exists an $i$ such that $p^{\nu_p(n)}\mid a_{ci}$ for all $c$. If $p\nmid10^{2a}-1$, then if $i=\phi(n)$, then $p^{\nu_p(n)}\mid10^{2ai}-1$ if $p\neq2,5$. Since $5\nmid n$, this means that we only need to make sure $2^a\mid x\cdot\frac{10^{2ai}-1}{10^{2a}-1}$. Since $2^{2a+1}\mid x$, this means that this is true, so if $5\nmid n$, then there exists a multiple of $n$ that is alternating. If $a<2$, then there exists an alternating integer $x$ with exactly $2b$ digits that is a multiple of $2\cdot5^{2b}$. Then, the first digit of $x$ is odd. Let $a_i=x\cdot\frac{10^{2bi}-1}{10^{2b}-1}$. Then, if $p\mid10^{2b}-1$, then $\nu_p(a_i)\geq\nu_p(i)$, so there exists an $i$ such that $p^{\nu_p(n)}\mid a_i$. If $p\nmid10^{2a}-1$, then we can let $i=\phi(n)$, so $p^{\nu_p(n)}\mid a_i$. If $p=5$, then $5^b\mid5^{2b}\mid x$, and if $p=2$, then $a=0,1$, so $p^a\mid x$. Therefore, $n\mid a_i$ for some $i$. Therefore, all positive integers except multiples of $20$ have an alternating multiple.

The answer is $\boxed{20\nmid n}$. Clearly if $20\mid n$, then last two digits are always even. It suffices to show everything else has an alternating multiple. Case 1: $\gcd(n,10)=1$. We consider $k$ so that $99n\mid 100^k-1$. Clearly such $k$ must exist as $99n$ is relatively prime to $100$. Then the alternating number $\frac{100^k-1}{99}$ (it is $1010101\cdots 101$) is a multiple of $n$. Case 2: $n$ is a power of $5$. We will show that there exists an alternating multiple of $5^k$ with exactly $k$ digits. We induct. Base cases $5, 25, 125, 8125, 78125$. Suppose $5^k$ has an alternating multiple with $k$ digits. We will show $5^{k+1}$ has an alternating multiple with $k+1$ digits. We place one digit in front of the alternating multiple of $5^k$. Call that digit $d$ and the alternating multiple $m$. Then we want $10^k\cdot d$ to be $-m\pmod{5^{k+1}}$. We know that $-m\equiv \{0,5^k, 2\cdot 5^k, 3\cdot 5^k, 4\cdot 5^k\}\pmod{5^{k+1}}$. Now the five choices for $10^k\cdot d$ produce those $5$ residues $\pmod {5^{k+1}}$ in some order. So we can choose $d$ so that $10^k\cdot d\equiv -m\pmod{5^{k+1}}$ and the induction is complete. $\blacksquare$ Case 3: $n$ is a power of $5$ times something relatively prime to $10$. Suppose $n=5^k\cdot l$. If $k$ is odd, consider an alternating multiple of $5^{k+1}$ with $k+1$ digits. If $k$ is even, consider an alternating multiple of $5^k$ with $k$ digits. Now we know $l$ has a multiple of the form $\frac{10^{kd}-1}{10^k-1}$ (basically generalized version of the $\frac{100^d-1}{99}$ in case 1). Now we have $\frac{10^{kd}-1}{10^k-1}$ is $100\cdots 0001000\cdots 1\cdots 000\cdots 000 1\cdots$ with $k-1$ zeroes in between each pair of consecutive ones. If $k$ is even multiply this number by the alternating multiple of $5^k$, and we get the digits of the alternating multiple of $5^k$ repeated many times. Since it has an even number of digits, it will be alternating. For example, $81258125\cdots8125$ or $252525\cdots25$. If $k$ is odd, replace $k$ with $k+1$ throughout this paragraph and multiply $\frac{10^{(k+1)d}-1}{10^{k+1}-1}$ by $5^{k+1}$ to get an alternating multiple of $n$. So we have covered all odd numbers. Case 4: $n$ is $10$ times an odd number. Note that all our alternating multiples for odd numbers had last digit odd. We can simply take the alternating multiple of $\frac{n}{10}$ and place a $0$ at the end. Now we have covered all multiples of $5$. Case 5: $n$ is a power of $2$. We will show there exist an alternating multiple of $2^k$ with $k$ digits. To be more precise, we will show that for even $k$, there exists an alternating multiple of $2^{k+2}$ with $k$ digits and for odd $k$ there exists some alternating number $2^k\pmod{2^{k+1}}$ with $k$ digits. Part 1 of the induction: Suppose we have an alternating multiple of $2^{k+2}$ with $k$ digits, where $k$ is even. We will show that there exists a some alternating number $2^{k+1}\pmod{2^{k+2}}$ with $k+1$ digits. We need to add an even digit, call it $d$ so that $10^k\cdot d\equiv 2^{k+1}\pmod{2^{k+2}}$. Clearly adding $2$ or $6$ works. Part 2 of the induction: Suppose we have an alternating number that is $2^k\pmod{2^{k+1}}$ with $k$ digits, where $k$ is odd. We will show that there exists some alternating multiple of $2^{k+3}$ with $k+1$ digits. Call the alternating multiple of $2^k$ $"m"$, and the digit we add $d$. We have $-m\equiv \{2^k, 3\cdot 2^k, 5\cdot 2^k, 7\cdot 2^k\}\pmod{2^{k+3}}$. We need $10^k\cdot d\equiv -m\pmod{2^{k+3}}$. Note that $d$ is odd. The only two values of $d$ for which $10^k\cdot d$ are the same mod $2^{k+3}$ are $1$ and $9$ (because we need their difference to be divisible by $2^3$). This gives $4$ distinct residues of $10^k\cdot d$, which are the same as the residues of $-m$ mod $2^{k+3}$. So we can choose $d$ so that $10^k\cdot d\equiv -m\pmod{2^{k+3}}$, which completes the induction. $\blacksquare$ Case 6: $n$ is a power of $2$ times an odd number. Note that that odd number is relatively prime to $10$ as we have already covered all multiples of $5$. Since we can construct a multiple of $2^k$ with $k$ digits, we can do the exact same thing we did with powers of $5$ times something relatively prime to $10$. The multiple will still be alternating. For example, $12161216\cdots 1216$ or $161616\cdots 16$. We have covered all positive integers with $20\nmid n$, so we are done.

All multiples of $20$ end with two evens, which means they are not alternating. Let $n\in \mathbb{Z^+}: 20\nmid n.$ Trivially all divisors of an alternating positive integers are also alternating. WLOG $n$ is even. Lemma: If $n=2^p$ or $n=2\cdot 5^p,$ where $p\in \mathbb{Z^+},$ then exists a multiple $m(n)$ of $n$ such that $m(n)$ is alternating and has $n$ digits. Proof.Set $k=(10^{n+1}-10)/99= \underbrace{101010\dots 10}_{n \text{ digits}}.$ For all $i=0,1,\dots ,n-1,$ there exists a sequence $s_0,s_1,\dots,s_i \in \{0,2,4,6,8\}$ such that $$\begin{align*} &2^{i+2}| L+\sum_{j=0}^{i} s_j\cdot 10^j ~~~~\text{ if }n \text{ is of the form }2^p. \\ & \text{or } 2\cdot 5^{i+1}|L+\sum_{j=0}^{i} s_j\cdot 10^j ~~~~\text{ if } n\text{ is of the form } 2\cdot 5^p. \end{align*}$$ This is easy to see by induction on $i.$ Particularly exists a sequence $s_0,s_1,\dots, s_{n-1} \in \{0,2,4,6,8\}$ such that $$m(n)=k+\sum_{j=0}^{n-1}s_j\cdot 10^j.$$ This $m(n)$ is alternating and has $n$ digits. We prove the following. Sub-Claim: $n|m(n).$ Proof. Write $n$ in the form $n'k,$ where $n'=2^p$ or $n'=2\cdot 5^p$ and $\text{gcd}(k,10)=1.$ Let $c\geq n'$ be an integer such that $10^c\equiv 1\pmod{k}.$ Let $L$ be the series of interconnection of $1010\dots$ and $m'(n).$ Since $m(n')$ is alternating with $n'$ digits, $L$ is also alternating. Since $n'\geq p \implies n'|L.$ Also $$\text{gcd}(2,k)=1\implies \exists i \in \{0,1,2,\dots,k-1\}: L \equiv -2i\pmod{k}.$$ Set $$m(n)=L+\sum_{j=1}^i 2\cdot 10^{cj}.$$ It is clear that $k|m(n).$ Also observe that $n'|10^{n'}, 10^{n'}|10^c$ and $10^c>m(n)\implies n'|m(n) \implies n|m(n).$ $\blacksquare$

I solved this problem at least 3 months before writing it up The answer is any $20 \nmid n$. Clearly if $20 \mid n$, the last two digits of any multiple of $n$ are even, so such $n$ fail. Note that if $n$ works, then so do all of its divisors, so we only have to consider the following two cases (explanation later): Case 1: $n=2^km$ with $\gcd(m,10)=1$ and $k\geq 3$ odd. First, I will prove that $2^k$ has an alternating multiple $m_2(k)$ with exactly $k-1$ digits (allowing leading zeroes). For $k=3$, just take $m_2(k)=32$. Now, to go from $k$ to $k+2$, add $\varepsilon \in \{10,12,14,16\}$ to the left side of $m_2(k)$, resulting in $10^{k-1}\varepsilon+m_2(k)$. The resulting number is always divisible by $2^k$, and since $\varepsilon/2$ spans a complete residue set $\pmod{4}$, we can pick an appropriate value of $\varepsilon$ to make $10^{k-1}+m_2(k)$ by $2^{k+2}$ as well, and also evidently alternating. Thus just set $m_2(k+2)$ equal to Now, to extend this to $2^km$, note that concatenating $m_2(k)$ $x$ times results in an alternating number with value $$m_2(k)\cdot \frac{10^{(k-1)x}-1}{10^{k-1}-1}.$$ Picking $x$ such that $\varphi((10^{k-1}-1)m) \mid x$ then makes the above expression divisible by $m$. Since it's also divisible by $2^k \mid m_2(k)$, this works. Case 2: $n=2\cdot 5^km$ with $\gcd(m,10)=1$ and $k$ even. I will prove that $2 \cdot 5^k$ has an alternating multiple $m_5(k)$ with exactly $k$ digits, again allowing leading zeroes. This is equivalent to proving that $5^k$ has an alternating multiple which is even. We use the same process as shown in case 1, by setting $m_5(2)=50$, and adding $10^k\varepsilon$ to $m_5(k)$, where $\varepsilon \in \{10,12,14,16,18,30,\ldots,98\}$, since $\varepsilon$ thus spans a complete residue set $\pmod{25}$. Then, concatenating $m_5(k)$ a suitable number of times results in an alternating multiple of $2\cdot 5^km$, which is the desired result. Any non-multiple $n$ of $20$ either satisfies $\nu_5(n)=0$ or $\nu_2(n)\leq 1$. If the former is true, then it divides $2^km$ for some $m$. Otherwise, it divides $2 \cdot 5^km$ for some $m$. Thus, the two cases above cover all multiples of non-multiples of $20$, so we're done. $\blacksquare$

The answer is all $n$ not divisible by $20$. If it is divisible by $20$ then clearly any multiple has tens digit and units digit both even. $~$ Case 1: $\gcd(n,10)=1$. Then, we claim that for large enough $k$, $$n\mid \frac{(10^r)^k-1}{99}=\underbrace{10\dots 010\dots 01\dots 01\underbrace{0\dots 0}_{r-1\text{ zeroes}}1}_{k \text{ ones}}$$ which is alternating when $r=2$. Note that for primes $p$ coprime to $10$, $$\nu_p\left(\left(100^{p-1}\right)^k-1^k\right)=\nu_p\left(100^{p-1}-1\right)+\nu_p(k)$$ is unbounded, which proves our claim. $~$ Case 2: $n=2^k$ or $5^k$. Then, we can start with $0$ and $5$ respectively and inductively construct alternating numbers with more and more digits that it is divisible by $2^k$ or $5^k$. If it is divisible by $10$ then we can add a zero at the end of the $5^k$ construction. $~$ Case 3: $\gcd(n,10)\neq 1$. Then, take the construction from the first case, pick a suitable $r$, and repeat that a suitable amount of times which gets us something divisible by the portion of $n$ coprime to $10$ and by all the $2$s and $5$s.

pretty easy for a P6 but whatever, it's mainly just time consuming because so many annoying cases, most of them don't even require a good intuition, basically just induction spam, i hope problems like this low quality never appear on IMO again In fact, you'll notice they were so similar I wrote a computer algorithm to format in the exact same sentence formats. We claim $n$ works iff $20\nmid n$; the necessity is evident since the last two digits would be even if 20|n. Call an alternating multiple of n a(n).If gcd(n,10)=1, then clearly $n\mid\frac{(10^2)^i}{99}=1010...101$ works because for any primes p|n, $\nu_p(n)=j$, we can find $i\equiv0\pmod{j\frac{p-1}2},i=kj\frac{p-1}2:\nu_p((10^2)^i-1)=\nu_p((10^{p-1})^{kj}-1^{kj})=\nu_p(100^{p-1}-1)+\nu_p(kj)$, so by CRT we can find suitable i equiv 0 mod that thing, since the power of p is then clearly sufficient. Now, we consider when $n=2^k,5^k,5^k2$. Case 1: $n=2^k$. We proceed by induction, manually checking base cases with inductive hypothesis that for even k, $a(2^{k+2})$ is defined with k digits, and for odd k, $\exists a(2^k)\equiv2^k\pmod{2^{k+1}}$ with k digits. Indeed, if k is even, we can append a 2 or a 6, since $10^kd\equiv2^{k+1}\pmod{2^{k+2}}$, establishing k+1 odd. On the other hand, if k is odd, then we want $10^kd\equiv-m\pmod{2^{k+3}}$. But this is evident, as for each $-m\equiv\{2^k,2^k3,2^k5,2^k7\}$, there is a d that can match up ($d\in\{\{1,9\},3,5,7\}$ yields the four needed distinct residues). Case 2: $n=2^ij,\gcd(j,10)=1$. By the same $\nu_p$ reasoning as before, there exists a multiple of j of the form $\frac{10^{k2\lceil\frac i2\rceil}-1}{10^i-1}=100...00100...001...1$ where there are $2\lceil\frac i2\rceil-1$ 0s. Then simply multiply by $a(2^2\lceil\frac i2\rceil)$ to get the desired number! For example, it could go 12161216...1216 for i=3 and/or 4. Case 3: $n=5^k$. We proceed by induction, assuming there's an $m=a(5^k)$ with $k$ digits, and base case manually checked. The way we'll do this is by appending a digit d at the start; we want $10^kd\equiv-m\pmod{5^{k+1}}$. But this is evident, as for each $-m\equiv\{0,5^m,5^m2,5^m3,5^m4\}$, there is a d that can yield these residues. Note that if d has the same sign as the leading digit of m (which makes it not alternating), simply take d+5 (mod 10), since it's the same mod 5 but changes sign. Case 4: $n=5^ij,\gcd(j,10)=1$. By the same $\nu_p$ reasoning as before, there exists a multiple of j of the form $\frac{10^{k2\lceil\frac i2\rceil}-1}{10^i-1}=100...00100...001...1$ where there are $2\lceil\frac i2\rceil-1$ 0s. Then simply multiply by $a(5^2\lceil\frac i2\rceil)$ to get the desired number! For example, it could go 81258125...8125 for i=3 and/or 4. Case 5: $n=5^i2j,\gcd(j,10)=1$. In this case, just take $a(\frac n{10})$ and add a 0, which CLEARLY works (divisible by $\frac n{10}$ by our earlier cases, is alternating since $\frac n{10}$ ended in odd and adding 0 ended in even, and divisible by 10). ok ok i see u hazard u solve p5 i solve PROBLEM 6 how about that. and ok awesomeming u solve 98g5 on discord i solved G8 or whatever it was how about that.

This is peak NT construct. I'm gonna edit this later with details. The main part of this problem is evidently to construct examples for $2^n$ and $5^n$ with an even number of digits. WLOG let $n$ be odd (we can just take $n+1$ otherwise). For $2^3$ use $16$. Let the construction for $2^k$ be $M$ for odd $k$. Assume $M$ has $k-1$ digits (this will hold up in the end) For $2^{k+2}$ use $10^{k-1}N + M$ for some (unique) $N$ in the set $\{16, 36, 14, 34\}$ (ah yes insert 1434 joke). The key fact is that the elements of this set are distinct $\pmod 8$. Thus: $$8|N + M/{2^{k-1}}$$ necessarily has a unique solution in this set. Proceed fairly similarly for $5^k$, except there are $25$ residue classes to deal with, which can be dealt with using the 25 two-digit numbers in the form $\{1, 3, 5, 7, 9\} \times \{0, 2, 4, 6, 8\}$, which are distinct mod $25$.

We claim that $$\boxed{\text{$n$ works iff $20 \nmid n$}}$$ Obviously if $20 \mid n$, then one can see why it does not work as the last two digits will always be even. We will prove the converse now, which is broken into three parts. Part A: $n$ is power of $2$ We will prove that there is a $m$ digit alternating multiple of $n=2^m$ and we proceed through induction. Let $X_m$ denote the corresponding multiple. See that the base cases $m=1$ works since one can take $X_1=6$. Now assume this is true for all m=$1,2,\dots,2k-1$ where $\nu_2(X_{2k-1})=2k-1$ and $\nu_2(X_{2k-2})>2k-2$. So what we construct $$\begin{align*} &X_{2k}=10^{2k-1} \cdot a+X_{2k-1}\\ &X_{2k+1}=10^{2k} \cdot b + X_{2k} \\ \end{align*}$$ Where $a$ is an odd digit and $b$ is an even digit. And see that we can do this since we can find such $a$ and $b$ as we have $$10^{2k-1} \cdot a+X_{2k-1} \equiv 0 \pmod {2^{2k+1}} \iff a+\text{something odd} \equiv 0 \pmod 4$$ $$10^{2k} \cdot b+X_{2k} \equiv 2^{2k+1} \pmod {2^{2k+2}} \iff b+\text{something even} \equiv 0 \pmod 4$$ and so the $v_2$ conditions are still preserved, basically $\nu_2(X_{2k})>2k$ and $\nu_2(X_{2k+1})=2k+1$ and so the induction step is complete as we have successfully created an alternating multiple of both $2^{2k}$ and $2^{2k+1}$. Part B: $n$ is power of $5$ or twice a power of $5$ See that we are going to create an odd alternating multiple for the power of $5$ and then just multiplying by $10$ resolves the case for the other set of numbers. Again we are going to induct on $n=5^m$, by creating an $m$ digit alternating multiple of $5^m$. Let the corresponding number be $Y_m$. For base case $m=1$, take $Y_1=5$ (haha). Now we will prove it for $m=k+1$ assuming we have found $Y_k$. Just let $Y_{k+1}=10^{k} \cdot c+Y_k$ and we can find an appropriate $c$ because we want $$10^k \cdot c+Y_k \equiv 0 \pmod {5^{k+1}}$$ which gives a solution for $c$ modulo $5$ and then we have an even choice of $c$ and an odd one, where we can choose appropriately. Remark Even if we have to choose $c=0$, we are fine since we can assume it is a $m$ digit multiple, as it is still tautologically fine Now take $Z_{m}=10 \cdot Y_{m-1}$ for $n=2 \cdot 5^m$ (where $Y_0=1$) and we are fine. Part C: all other numbers Let $n=A \cdot N$ where $A$ is the part which only contains the powers of $2$ or $5$ and let $W_{\ell}$ be its counterpart from the previous sections; and make sure $\ell$ is even, if it is not consider the next alternating multiple (for example if $n=12$, then we choose $X_2$ or if $n=30$, then we would have chosen $Z_1$ but we choose $Z_2$.) Now just let the alternating multiple be $$W_{\ell} \cdot \left(\frac{10^{\ell \cdot \varphi{((10^{\ell}-1)N})}-1}{10^{\ell}-1} \right)=\overline{W_{\ell}W_{\ell} \dots W_{\ell}}$$ and see that the reason we made sure $\ell$ is even, is that when we \emph{repeat} the blocks of $W_{\ell}$, the last digit from a block and the first digit from the next block are of different parity.

Say such an integer $n$ is flippy if that is the case. We claim that all $n$ that aren't multiples of $20$ are flippy. Multiples of $20$ can be checked to not work since the last two digits don't alternate. Else, suppose $20 \nmid n$. If $10 \mid n$ we can just solve the case of $\frac{n}{10}$, so assume not. Claim: If $n$ is flippy, then $c \cdot n$ is flippy for any $\gcd(10n, c) = 1$. Proof. Suppose $n$ is flippy with some multiple $m$. Then append $c \cdot \varphi(c)$ copies of $10$ or $01$ to the front to preserve alternating. We can then turn every $\varphi(c)$th $1$ into a $2$, which increases the residue $\pmod{c}$ by $k \cdot 10^{\varphi(c)} \equiv k \pmod{c}$ for some constant $k$ which is coprime to $c$. Since we can do this up to $c$ times, we are done by choosing a specific number of times. $\blacksquare$ We thus need to solve the cases where $n$ is a power of $2$ or $5$ and show they are flippy. For powers of $5$, we can mimic a USAMO problem by inducting on the exponent. If $m = c \cdot 5^k$ works and has $k$ digits, then we can consider $m + i \cdot 10^k, m + (5 + i) \cdot 10^k$ and one of them must work for $5^{k+1}$ and be alternating. For powers of $2$, we do something similar. We first try appending $10^k$ or $2 \cdot 10^k$ to maintain alternating this. However, if this makes the sum $2^k \pmod{2^{k+1}}$, then we increase the sum by $t \cdot 10^{k-1}$ where $t \le 4$ is chosen such that $t \cdot 10^{k-1} \equiv 2^k \pmod{2^{k+1}}$ to finish.