In the sequence $00$, $01$, $02$, $03$, $\cdots$, $99$ the terms are rearranged so that each term is obtained from the previous one by increasing or decreasing one of its digits by $1$ (for example, $29$ can be followed by $19$, $39$, or $28$, but not by $30$ or $20$). What is the maximal number of terms that could remain on their places?
Problem
Source:
Tags: More Sequences
jgnr
21.04.2009 16:40
Define digit parity of a number as the parity of the sum of digits of the number.
Let $ a_1,a_2,\ldots,a_{100}$ be a rearranged sequence. We claim that $ a_k$ and $ a_{k+10}$ cannot both remain on their places. There are 10 terms between them. Note that the digit parity of consecutive terms must be different. So there must be an odd number of terms between $ a_k$ and $ a_{k+10}$, contradiction. Therefore at most one of each pair $ (0,10),(1,11),(2,12),\ldots,(89,99)$ remain on its place. The answer is at most 50. The following arrangement show that 50 is indeed the maximum:
00,01,02,03,04,05,06,07,08,09,
19,18,17,16,15,14,13,12,11,11,
20,21,22,23,24,25,26,27,28,29,
39,38,37,36,35,34,33,32,31,30,
40,41,42,43,44,45,46,47,48,49,
59,58,57,56,55,54,53,52,51,50
60,61,62,63,64,65,66,67,68,69,
79,78,77,76,75,74,73,72,71,70,
80,81,82,83,84,85,86,87,88,89,
99,98,97,96,95,94,93,92,91,90.