combinatoriek 3

Opgave - IMOSL 1998 vraag 24

Kaarten genummerd 1 tot en met 9 worden willekeurig in een rij geschikt. Tijdens een beweging mag men elke blok van opeenvolgende kaarten waarvan de getallen in stijgende of dalende volgorde liggen nemen en dat blok omdraaien. Zo mag je bijvoorbeeld $9\ 1\ \underline{6\ 5\ 3}\ 2\ 7\ 4\ 8$ veranderen in $9\ 1\ \underline{3\ 5\ 6}\ 2\ 7\ 4\ 8$. Bewijs dat men met maximum 12 bewegingen, alle kaarten in ofwel stijgende ofwel dalende volgorde kan schikken.