MEMO Szeged

Solution:

If $3 \mid k$, then for any $n \in \mathbb{N}$ of the form $n=3k+1$, the sum of the digits of all positive integers up to $n$ gives remainder 1 modulo 3. As a positive integer is divisible by 3 if and only if the sum of its digits is divisible by 3, no matter how we glue $1,2, \ldots, n$, the resulting number is not divisible by 3, hence also not by $k$. So no appropriate $N_{k}$ can be chosen.

If $3 \nmid k$, write $k=2^{a} 5^{b} \cdot m$ with $\gcd(m, 10)=1$. Let $\ell \geq \left\lfloor \log_{10}(m) \right\rfloor + 2$ be an integer divisible by $\phi(m)$, so $10^{\ell} \equiv 1 \pmod{m}$ by Euler-Fermat. By the size constraint of $\ell$, we can choose $a_{i} \in \mathbb{N}$ for $0 \leq i < m$ such that $a_{i} \equiv i \pmod{m}$ and $a_{i}$ has $\ell$ digits. Note that all $a_{i}$ are different and can also be chosen to be different from $10^{\max(a, b)}$. Take $N_{k} \geq \max \left(10^{\max(a, b)}, 10^{\ell}\right)$. For $n \geq N_{k}$ we glue $1,2, \ldots, n$ the following way:

(a) We put $10^{\max(a, b)}$ at the end of the glueing, so the glued number ends with $\max(a, b)$ zeros, ensuring that the number is divisible by $2^{a} 5^{b}$.

(b) At the beginning of the number we put $a_{0}$, then the number 1, then $a_{1}, a_{2}, \ldots, a_{m-1}$ in this order.

(c) We put the remaining numbers in the middle, in an arbitrary order.

Let $G_{0}$ be the number given by this glueing, and for $1 \leq i < m$ let $G_{i}$ be the number we get from the same glueing, except for swapping $a_{0}$ and $a_{i}$. We show that at least one of the integers $G_{0}, G_{1}, \ldots, G_{m-1}$ is divisible by $m$, and as all of them are divisible by $2^{a} 5^{b}$, one of them will be divisible by $k$, finishing the proof.

Let $d$ be the number of digits of $G_{0}$ (and hence of $G_{1}, \ldots, G_{m-1}$ as well). Then

$$G_{i} - G_{0} = 10^{d-\ell}(a_{i} - a_{0}) + 10^{d-\ell-1-\ell \cdot i}(a_{0} - a_{i}) \equiv 10^{d-1} \cdot (a_{i} - a_{0}) \cdot (10-1) \equiv i \cdot 9 \cdot 10^{d-1} \pmod{m}.$$

So if $i$ is such that $-G_{0} \equiv i \cdot 9 \cdot 10^{d-1} \pmod{m}$, then $m \mid G_{i}$. This choice of $i$ is possible, as $m$ is coprime to both 9 and 10, so the inverse of $9 \cdot 10^{d-1}$ exists modulo $m$. Therefore $G_{i}$ is a gluing of $1,2, \ldots, n$, divisible by $k$.