31st Turkish Mathematical Olympiad

Answer: 17. A subsequence of $S$ consisting of $k$ consecutive digits will be called a $k$-block. First of all, let us show that there are two differently located 16-blocks such that the sequences obtained by the restriction of $S$ to these blocks coincide. Since the first two balanced integers are $123456789$ and $123456798$ there exists a 16-block $$2345678912345679$$ Consider the location of the balanced integer $234567891$. Since the next balanced integer is $234567918$ the 16-block constituted by the 9 digits of the first and 7 digits of the second balanced integer is again $2345678912345679$.

Now we show that there are no two differently located 17-blocks such that the sequences obtained by the restriction of $S$ to these blocks coincide. We start with the following

Claim: Let $D_1,D_2$ be two consecutive balanced integers in $S$ and $k\le 8$ be an integer. Let $P_1$ and $P_2$ be numbers constituted by the first $k$ digits of $D_1$ and $D_2$, respectively. If the set of digits of $P_1$ and the set of digits of $P_2$ coincide then $P_1=P_2$.

Proof: Assume the contrary: suppose that the set of digits $P_1$ and $P_2$ coincide but $P_1\ne P_2$. Among $k$ digits, let $l$ be the very first digit from the left when corresponding digits of $P_1$ and $P_2$ are different. Since $P_1$ and $P_2$ are consecutive, $l$-th digits of $P_1$ and $P_2$ should be $j$ and $j+1$, respectively. By definition, $1\le l\le k-1$. Since $D_1$ and $D_2$ are consecutive, by erasing of first $l$ digits of $D_1$ we should get a maximal possible number and by erasing of first $l$ digits of $D_2$ we should get a minimal possible number. Let $p$ be the last digit of $D_1$. Then in $D_2$, $p$ should be just after $j+1$. This contradicts with the fact that the set of digits of $P_1$ and the set of digits of $P_2$ coincide. Thus, $P_1=P_2$. $\square$

Suppose that there are two differently located coinciding 17-blocks, say $a$ and $b$. Any 17-block totally contains some balanced integer, otherwise its length is at most $8+8=16$. Let $K_1$ and $K_2$ be balanced integers contained in these two 17-blocks, respectively. Since 17-blocks are differently located, $K_1\ne K_2$. Moreover, $K_1$ and $K_2$ should share some digits, otherwise the block would consist of at least $9+9=18$ digits. Let the common part of $K_1$ and $K_2$ be $u_2$. Let $alb$ be the concatenation of $a$ and $b$. Without loss of generality, let us represent $K_1$ and $K_2$ by the following concatenations: $K_1=u_1|u_2$ and $K_2=u_2|u_3$. Thus, the sequence $u_1|u_2|u_3$ is a subsequence of both $a$ and $b$. Moreover, since both $u_1$ and $u_3$ contain digits not represented in $u_2$, $u_1$ and $u_3$ have the same length and same set of digits.

$K_1=u_1|u_2$ is a balanced integer starting with $u_1$. Since the next balanced integer starts as $u_3$, we get $u_1=u_3$.

The balanced integer preceding $K_2=u_2|u_3$ ends with $u_1$. Let us represent it as $v|u_1$. Therefore, $v|u_1$ and $u_2|u_3$ are consecutive balanced numbers. Since $u_1=u_3$, the digits of $v$ and $u_2$ coincide: $v=u_2$. Hence $v|u_1=u_2|u_3$. On the other hand, two consecutive balanced integers cannot coincide, contradiction. Thus, there are no two differently located 17-blocks such that the sequences obtained by the restriction of $S$ to these blocks coincide. Done.