Take the 2-minute tour ×
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.

Sequence X consists of N pegs each randomly assigned on of M colours. One each go, the player places N coloured pegs in a line. If they exactly match sequence X, the game terminates. Otherwise, the player is told how many pegs in their sequence are the same colour as the pegs in the same position in sequence X, and how many of their pegs have a colour which is one of the coulours contained in sequence X.

On average, after how many goes would the game end, assuming perfect play?

share|improve this question
    
Are you assuming perfect play? –  Peter Taylor Dec 13 '11 at 13:14
add comment

2 Answers

up vote 5 down vote accepted

There is unlikely to be a simple formula for general $N$ and $M$ though there will be bounds.

The standard version has $N=4$ pegs drawn from $M=6$ colours, with repeats allowed. Koyama, K. and Lai, T. W. "An Optimal Mastermind Strategy." J. Recr. Math. 25, 251-256, 1993 provides an algorithm with an average of 4.340 guesses and a maximum of 6, and another with an average of 4.341 and a maximum of 5.

share|improve this answer
add comment

There is a paper by Chvatal that provides asymptotically tight bounds for $\ k <= n^{(1-\epsilon)}$ .

There is a recent paper by Doerr et al that improves the upper bound for larger values of $\ k$ .

share|improve this answer
add comment

Your Answer

 
discard

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.