Proof of Formula for maximum of binary changes in a two colored chain

Question

This question possibly could be stated more formal in better mathematical terms but sadly I don't have the knowledge needed for this yet. First we consider a chain of balls of length $n$ (where $n$ is the number of balls and defined to be the "length" of the chain) and where the balls are either black or white. (Specific color doesn't really matter. It is just important that they can have two different colors and each ball only one at the same time.) Now given any random combination of how the balls are colored in the chain. What are the maximum of changes in color one has to perform to get a perfect alternating chain. I conjecture that for a given length $n$ of the chain the maximum number of changes needed to get a perfect alternating (in colors) chain of balls is given by the following function $f$:

$f(n)=\lfloor(n/2)\rfloor$

Sadyl I haven't been able to prove this myself. I have thougth of the chain being a bernoulli chain over some probability space where the colors are either a 50% chance for event B or event A. If someone could say to what topics my question is related or could state it in a more formal way in better mathematical terms I would be very happy. Also if someone has suggestions on how I migth be able to prove this I would be very happy.

Answer 1

It's easier to see if you switch the colours of, say, the odd-numbered balls. Then you want the maximum number of changes needed to get all the balls with the same colour. But that's obvious: either switch all white balls to black, or all black balls to white, whichever there are fewer of.

More formally: suppose your balls are $x_1$ to $x_n$, with, say, $+1$ for black and $-1$ for white. Let $y_i = (-1)^i x_i$, so $x_i$ alternating corresponds to $y_i$ all black or all white. If $\sum_i y_i \le 0$, switch all $y_i$ with $y_i = +1$ to $-1$, if $\sum_i y_i \ge 0$, switch all $-1$ to $+1$.

Answer 2

There are two ways to get an alternating chain. You can have either black-white-black-white-..., or white-black-white-black-... . Suppose it takes $k$ changes to turn the chain into the first option. Then it would take $n-k$ changes to turn the chain into the second option, since you would need to change the opposite set of balls.

For any $k\in \{0,1,\dots,n\}$, the smaller of $k$ and $n-k$ is at most $\lfloor n/2\rfloor$, which implies that $\lfloor n/2\rfloor$ changes always suffice. This is indeed the worst case, which occurs when $\lfloor n/2\rfloor$ balls match the black-white-... pattern, while the remaining $\lceil n/2\rceil$ match the white-black-... pattern. n