MathDB

Let

k\ge 1

be a positive integer.
We consider

4k

chips,

2k

of which are red and

2k

of which are blue. A sequence of those

4k

chips can be transformed into another sequence by a so-called move, consisting of interchanging a number (possibly one) of consecutive red chips with an equal number of consecutive blue chips. For example, we can move from

r\underline{bb}br\underline{rr}b

r\underline{rr}br\underline{bb}b

where

r

denotes a red chip and

b

denotes a blue chip.
Determine the smallest number

n

(as a function of

k

) such that starting from any initial sequence of the

4k

chips, we need at most

n

moves to reach the state in which the first

2k

chips are red.

Problem Statement