I assume that most of us are familiar with the board game Mastermind. Someone selects a secret code using colored pegs, and you have to guess the code. After every guess, you are given the number of pegs that are in the right position (indicated with black pegs) and the number of letters that are correct, but in the wrong position (indicated with white pegs).

The minimum number of guesses to arrive at the solution is, of course, 1. Is there a mathematical formula that will tell you what the maximum number of guesses would be, given N colours and M positions? To prevent someone from making the same wrong guess over and over (in which case the maximum would be infinity), I’ll postulate that each of your guesses has to be consistent with the information you’ve received from your previous guesses. But I’m not assuming that the codebreaker is trying to use the best algorithm - instead, let’s pretend that I’m trying to take as many turns as possible to break the code.

I’ll also postulate that the code can contain duplicates (pegs of the same color can appear in more than one spot in the code), but “blanks” are not allowed. (Allowing blanks would be the same as adding a color to the possible list of peg colors present in the code.)

Example:

Suppose I allow six peg colours (represented by letters) and the code has four positions. In the sample game listed below, 9 (nine) guesses were needed to find the solution, with each guess being consistent with the information from the previous guesses. (the "b"s and "w"s represent the black and white pegs telling me how many are correct in my guess.)

```
COLOURS: 6
a b c d e f g
SPOTS: 4
SOLUTION fgfg
9 fgfg 4b 0w - solved
8 gfgf 0b 4w
7 ffgg 2b 2w
6 ffff 2b 0w
5 eeee 0b 0w
4 dddd 0b 0w
3 cccc 0b 0w
2 bbbb 0b 0w
1 aaaa 0b 0w
```