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.

I have to choose $k$ items out of $n$ choices, and my selection needs to be in the correct order (i.e. permutation, not combination). After I make a choice, I receive a hint that tells me how many of my selections were correct, and how many were in the correct order.

For example, if I'm trying to choose $k = 4$ out of $n = 6$ items, and the correct ordered set is $\{5, 3, 1, 2\}$, then an exchange may go as follows:

0,1,2,3
(3, 0) # 3 correct, 0 in the correct position

0,1,2,5
(3, 0)

0,1,5,3
(3, 0)

0,5,2,3
(3,0)

5,1,2,3
(4,1)

5,3,1,2
(4,4)

-> correct order, the game is over

The problem is I'm only given a limited number of tries to get the order right, so if $n = 6, k = 4$, then I only get $t = 6$ tries, if $n = 10, k = 5$ then $t = 5$, and if $n = 35, k = 6$ then $t = 18$.

Where do I start to even solve this? It almost seems like a constraint solving problem. The hard part seems to be that I only know something for sure if I only change 1 thing at once, but the upper bound on that is way more than the number of tries I get.

share|improve this question
    
If the no. of tries given is small, there may be no way to actually solve it(unless you're lucky). –  Ishan Banerjee Feb 1 '13 at 5:39
    
$t=5, n=10, k=5$ sounds awfully tight, but the others should be quite feasible with a basic strategy. Think of it as similar to binary search, where each guess allows you to throw out a certain fraction of the number of possibilities. You might find inspiration in Knuth's algorithm for a very similar game. –  Erick Wong Feb 1 '13 at 6:16

1 Answer 1

up vote 0 down vote accepted

The game is called MasterMind. http://en.wikipedia.org/wiki/Mastermind_%28board_game%29

share|improve this answer

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.