On the board a 20-digit number which have 10 ones and 10 twos in its decimal form is written. It is allowed to choose two different digits and to reverse the order of digits in the interval between them. Is it always possible to get a number divisible by 11 using such operations?
Problem
Source: Kyiv mathematical festival 2016
Tags: Kyiv mathematical festival, combinatorics, Digits, Divisibility
13.09.2016 01:17
We’ll prove by induction that if there are $2n$ ones, and $2n$ twos, we can perform some operations and get a multiple of $11$, where $n$ is a positive integer. Define $poles$ to be a pair of digits that are used to perform the problem’s operation. Base case $n=1$ is easy, as $1122$, $1221$, $2112$ and $2211$ are all multiples of $11$, and $1212$ and $2121$ can be rearranged into $1122$ and $2211$ by taking the endpoints as poles. Assume it works for $n=k$. Let $N$ be a number with $2k+2$ ones and $2k+2$ twos, $B$ the number formed by the last $4$ digits of $N$, and $A$ the remaining number. Define the $middle$ of $A$ as the number formed by removing the first digit of $A$. Clearly, if at some point $B$ has $2$ ones and $2$ twos, we are done by the induction hypothesis. Assume $WLOG$ that there are more twos than ones in $B$. Therefore, $A$ has at least $3$ ones and we have three cases: Case 1: $B = 2122$, $2212$ or $2221$. There are clearly $2k+1$ ones in $A$, and they can’t all be at the leftmost endpoint. Therefore, take the digit to the left of the rightmost one in $A$ and the second digit of $B$ as poles, perform the operation, and $B$ will have $2$ ones and $2$ twos, done. Case 2: $B = 1222$ There are clearly $2k+1$ ones in $A$, and they can’t all be at the leftmost endpoint; and there are $2k-1$ twos in $A$. If there are no pairs of consecutive ones, all ones in $A$ must have a two or nothing to their left, but this is impossible, as this means there are at least $2k$ twos in $A$, but we know there are only $2k-1$ of them. Therefore, there must be a pair of consecutive ones somewhere in $A$. If there are $2$ ones in the middle of $A$ that are consecutive, then we are done, as we take the digit to the left of that pair as a pole and the second $2$ in $B$ as the other one, perform the operation, and $B$ will have $2$ ones and $2$ twos, done. If there is no such pair in the middle of $A$, this implies that $A$ must start with $2$ ones. As there are no other pairs of ones in $A$, the other ones in $A$ must have a two to their left. As these ones appear $2k-1$ times in $A$, and so do all twos in $A$, $A = 11212121 \dots 21$. But then $N = 11212121 \dots 211222$, and we get a pair of ones that is not at the leftmost point, which consists of $A$’s rightmost one and $B$’s leftmost one (and clearly, $A$’s rightmost one is not in the first position). We perform the operation by taking $A$ rightmost two and the third digit of $B$ as poles, and $B$ will have $2$ ones and $2$ twos, done. Case 3: $B = 2222$ There are clearly $2k+2$ ones in $A$ and $2k-2$ twos in $A$. If there are no pairs of consecutive ones, all ones in $A$ must have a two or nothing to their left, but this is impossible, as this means there are at least $2k+1$ twos in $A$, but we know there are only $2k-2$ of them. Then there is a pair of consecutive ones somewhere in $A$. If such pair is in the middle of $A$, we take the digit to the left of such pair as a pole, and the third two in $B$ as poles, and we are done, as $B$ will have $2$ ones and $2$ twos. If no such pair exists in $A$, then $A$ must start with $2$ ones, and the $2k$ remaining ones must have a two to their left, which is a contradiction, as there are only $2k-2$ twos. Therefore, take $n = 5$ and the problem is solved.