# Interesting but difficult board game question?

I have a 3 by 3 board game. A black marble is randomly place in one of the nine squares. Distance between squares is measured as one if either diagonal or horizontal/vertically next each other, and two otherwise (so max distance of two). With an initial black marble, all squares within distance one of this black marble contains a blue one. The rest of the squares are then filled with a red marble. All 9 squares are covered. How many minimum cups (and which ones) do I need to look at in order to figure out where black marble is?

\begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array}

So my thinking is that the center one will be blue with probability $8/9$ and black with probability $1/9$. If the black marble is one the corners (probability $4/9$), then $e$ must be blue and two of $b, d, f, h$ must be blue. This seems to be a lot of case work, but I get that the minimum is 4? Has to be symmetric?

-

You can do it in $3$ guesses.

Look at $a$. If it’s black, you’re done. If it’s blue, the black marble is $b,d$, or $e$, and you can locate it with two more guesses. (For instance, look at $b$; if it’s black, you’re done, and if not you can look at $d$, after which you’ll know whether the black marble is $d$ or $e$.) If it’s red, the black marble is $c,f,g,h$, or $i$. Look at $i$; if it’s black, you’re done. If it’s blue, the black marble is $f$ or $h$, and one more guess will locate it. If it’s red, the black marble is $c$ or $g$, and one more guess will locate it.

Starting with $b$ works equally well and sometimes better. If $b$ is blue, the black marble is $a,c,d,e$, or $f$, and looking at $a$ will either show you the black marble, tell you that it’s $d$ or $e$, or tell you that it’s $c$ or $f$. If $b$ is red, the black marble is $g,h$, or $i$, and looking at $g$ will tell you where it is.

-
Im curious, what is the long run proportion of blue, red, and black marbles? So $1/9$ must be black and then for blue its $\frac{4}{9}(3/9) + \frac{1}{9} (9/9) + \frac{4}{9} (5/9) = \frac{41}{81}$ And so red marbles are one minus those two combined? – lordflies Sep 16 '13 at 3:25
@bob: You mean if all arrangements are equally likely? On average you have $1$ black marble, $\frac{32}9$ red marbles, and $\frac{40}9$ blue marbles. Your calculation for black should be $\frac49(1/9)+\frac19(1/9)+\frac49(1/9)=1$. Dividing by $9$ gives you the expected fraction (rather than number) of each color. Your method yields that directly, and yes, you can subtract the first two from $1$ to get the figure for red, but you’ve an error in the middle term of the figure for blue: it should be $\frac19(8/9)$. – Brian M. Scott Sep 16 '13 at 3:36

This game allows to look at $3$ fixed squares (without game tree, etc) to know where is black marble.

For example, squares $a,f,h$.

If one of them is black, then black marble is find already, and game stops.

I'll show cases, when they all are not black: $$\begin{array}{c} \color{red} {\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{red} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{red} {\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \mbox {impossible};$$

$$\begin{array}{c} \color{red} {\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{red} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \begin{array}{c} \color{red} {\blacksquare}\;\color{red}{\blacksquare}\;\color{red}{\blacksquare}\\ \color{blue}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{red} {\blacksquare}\\ \color{black}{\blacksquare}\;\color{blue} {\blacksquare}\;\color{red}{\blacksquare} \end{array};$$

$$\begin{array}{c} \color{red} {\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{red}{\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \begin{array}{c} \color{red} {\blacksquare}\;\color{blue}{\blacksquare}\;\color{black}{\blacksquare}\\ \color{red}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{red}{\blacksquare}\;\color{red} {\blacksquare}\;\color{red}{\blacksquare} \end{array};$$

$$\begin{array}{c} \color{red} {\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \begin{array}{c} \color{red} {\blacksquare}\;\color{red}{\blacksquare}\;\color{red}{\blacksquare}\\ \color{red}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{red}{\blacksquare}\;\color{blue} {\blacksquare}\;\color{black}{\blacksquare} \end{array};$$

$$\begin{array}{c} \color{blue} {\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{red} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{red}{\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \mbox{impossible};$$

$$\begin{array}{c} \color{blue} {\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{red} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \begin{array}{c} \color{blue} {\blacksquare}\;\color{blue}{\blacksquare}\;\color{red}{\blacksquare}\\ \color{black}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{red} {\blacksquare}\\ \color{blue} {\blacksquare}\;\color{blue} {\blacksquare}\;\color{red}{\blacksquare} \end{array};$$

$$\begin{array}{c} \color{blue}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{red} {\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \begin{array}{c} \color{blue} {\blacksquare}\;\color{black}{\blacksquare}\;\color{blue}{\blacksquare}\\ \color{blue}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{red} {\blacksquare}\;\color{red} {\blacksquare}\;\color{red}{\blacksquare} \end{array};$$

$$\begin{array}{c} \color{blue}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\\ \color{gray}{\blacksquare}\;\color{gray}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{gray}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{gray}{\blacksquare} \end{array} \implies \begin{array}{c} \color{blue}{\blacksquare}\;\color{blue}{\blacksquare}\;\color{blue}{\blacksquare}\\ \color{blue}{\blacksquare}\;\color{black}{\blacksquare}\;\color{blue} {\blacksquare}\\ \color{blue}{\blacksquare}\;\color{blue} {\blacksquare}\;\color{blue}{\blacksquare} \end{array}.$$

So, strategy can be so easy.

-