Combinatorics and game of bingo

72 Views Asked by At

2000 dots on placed on a circle and may be colored either black or grey. If we see 2 black dots next to each other then we say bingo. if we see 2 grey dots are two apart (i.e. one black dot or one grey dot in between) then we also say out loud bingo bingo. What is the minimum number of times we can shout bingo with this constraint.

1

There are 1 best solutions below

0
On

I think the answer is that for $n$ dots the minimum number of bingos is $\lceil \tfrac{1}{4}n \rceil$ (for $n \ge 5$). This is achievable, by using $\lceil\tfrac{1}{4}n\rceil$ pairs of Bs and inserting between them either single or double Gs to make up the total. This is the minimum, because three Gs in a row can always be changed, whatever flanks them, in a way which decreases the number of bingos, so it is never desirable to have more than 2 Gs in a row. Also, GBG, with a single B between two Gs, can always be replaced by BBG or GBB without increasing the number of bingos, so it is never necessary to have a single B to achieve the minimum.