Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.