Let $n$ be a positive integer. $2n+1$ tokens are in a row, each being black or white. A token is said to be balanced if the number of white tokens on its left plus the number of black tokens on its right is $n$. Determine whether the number of balanced tokens is even or odd.
Problem
Source: Spain Mathematical Olympiad P2
Tags: combinatorics, Parity, Spain
sbealing
17.03.2018 20:01
Consider an initial configuration where the first tokens are $\text{black}$ and the rest are $\text{white}$. It is clear exactly one colour has $\geq n+1$ tokens so there is exactly $1$ balanced token. We will prove this parity stays invariant. Consider jumping a black token over a white token going from $\cdots BW \cdots \rightarrow \cdots WB \cdots$. $B$ is balanced iff $W$ is balanced . If they are both balanced then they both become unbalanced and if they are both unbalanced then either nothing changes or they both become balanced. Hence the parity remains unchanged so it is always $\boxed{\text{Odd}}$
M.Shahverdi
14.10.2020 09:50
We prove this using induction on $n$. The base case is obvious. Consider the statement is true for $k-1$ and we are trying to prove it for $k$. If all the tokens are the same color there exists exactly one balanced token so consider we have both white and black tokens then there exist two consecutive tokens with different colors so if we delete them and use the induction hypothesis the statement would be clear.