A positive integer $n$ is Mozart if the decimal representation of the sequence $1, 2, \ldots, n$ contains each digit an even number of times. Prove that: 1. All Mozart numbers are even. 2. There are infinitely many Mozart numbers.
Problem
Source: MEMO 2016 T7
Tags: number theory, number theory proposed, Parity, Digits
25.08.2016 19:28
2.Consider $n=10T$ where $T=2...2$ ($\text{2k's 2}$)
26.08.2016 16:57
30.08.2016 00:56
Solution for 1: Claim: If $n$ is odd, then the number of digits in the sequence $1,2,\ldots,n$ is odd. Thus $n$ cannot be a Mozart number. The proof by induction is simple. The claim is true for $n=1$. If the sequence $1,2,\ldots, 2k-1$ has an odd number of digits, the sequence $1,2,\ldots, 2k+1$ also has an odd number of digits (note that $2k$ and $2k+1$ have exactly the same number of digits!). Solution for 2: Claim: Every number $n$ that is a multiple of 20 and has an odd number of 0s and an even number of other digits is a Mozart number. Clearly there are infinitely many such numbers $(220, 440, 660, 880, 10100, 11000, 11220, \ldots)$. Proof: The 19-long sequence $1,\ldots,19$ contains an odd number of 0s and an even number of all the other digits. We now check 20-long sequences $j, \ldots, j+19$ for any $j$ with $j\equiv 0\mod 20$ (i.e. sequences 20-39, 40-59, 60-79, 80-99, 100-119, 120-139 and so on). Each of these 20-long sequences clearly has an even number of all digits 0-9. Note that all the 20 numbers in such a 20-long sequence are identical in all their digits except for the last two (ones, tens). Thus for ALL numbers $k\equiv 19 \mod 20$ the sequence $1,\ldots, k$ contains an odd number of 0s and an even number of all the other digits. This proves the claim since we just have to add to such a sequence a successor $n=k+1$ that has an odd number of 0s and an even number of all the other digits. New question: Are there Mozart numbers that are not a multiple of 20?
30.08.2016 02:24
Yes. 122 is a Mozart number.
30.08.2016 19:23
The proof that looks at multiples of 20 can very easily be adapted to characterize all Mozart numbers by considering each (even) residue modulo 20 separately and getting a similar restriction on odd and even digit counts in the candidate number.