Minimum Guesses to Solve Mastermind Puzzle w/ 4 Digits

[Wilmer]

This reminds me of the old mastermind puzzle.

Computer picks (at random) a 4-digit number.
The number will contain only the digits 1, 2, 3, and 4:
the digits may be used more than once: 1111 to 4444.
You input a guess as to what the number is.
If your guess has at least 3 digits in their correct positions, you
will be told so by the computer; else you will be told "try again!"
Example: computer's number is 2334; you enter 2314:
3 digits are in correct position: 23-4, 23-4
Of course if you entered 2334, you would also get the message.

What is the minimum number of numbers you need to enter
before you get the "correct 3 positions" message?

Any hints?
I'm having fun trying to solve that...

 

[Greg]

1 :)
244 :(

 

[Wilmer]

Very funny Greg!
I will reword the question:

What is the minimum number of numbers you need to enter
before you ARE SURE to get the "correct 3 positions" message?

As example, if you get to the point where you know that these
3 numbers are the only ones left:
1124
1324
1424
then you are SURE to get the message by entering 1224,
as 1-24 will be in correct positions.

Making it 2digit number with at least 1 digit in correct position:
we have 11, 12, 21 and 22 only.
You are not SURE your 1st number entered will be ok:
you:computer
11 : 22
12 : 21
21 : 12
22 : 11
So you need to enter a 2nd number.

 

[Greg]

If the only numbers remaining are 1124, 1324 and 1424 you've already entered 1224.

 

[Wilmer]

If the only numbers remaining are 1124, 1324 and 1424 you've already entered 1224.

Whoops...sorry...you'd enter any of the 3: 1124 or 1324 or 1424, of course,
and you're guaranteed SUCCESS!

Btw, a number does not need to be entered to be eliminated; each number entered
getting a "no" response eliminates 13 numbers: itself plus 12 others; the "12 others"
did not need to be entered.

So, after entering my 1st number and getting a "no", there are 256-13=243
numbers left.

From this point on, keep in mind that the "12 others" may contain numbers
already eliminated, so reducing by 13 is not automatic.

As example (I'll use 3digit numbers 111 to 333 requiring 2 digits in correct
position), if I enter 113 and get a "no", these 7 (same way as the 13)
are eliminated:
111*, 112, 113, 123*, 133, 213, 313 : so left = 27-7 = 20
Then if I enter 121, 2 are duplicates:
111*, 121, 122, 123*, 131, 221, 321 : so left = 20 - 5 = 15

See why this is giving me a migraine?!

Btw, you as excited with the Blue Jays as I am?

 

[Wilmer]

I really should have used 3digit numbers; less confusing:
....................
Computer picks (at random) a 3-digit number.
The number will contain only the digits 1, 2, and 3:
the digits may be used more than once: 111 to 333.

You input a guess as to what the number is.
If your guess has at least 2 digits in their correct positions,
will be told "correct", else you will be told "no".

Example: computer's number is 233; you enter 213:
2 digits are in correct position: 2-3, 2-3.
Of course if you entered 233, you would also get the "correct" message.

What is the minimum number of numbers you need to enter
before you get the "correct" message?
.....................
So we have 27 numbers (not 256!):
1:111, 2:112, ..., 26:332, 27:333

However, still quite confusing; only Greg can solve it!

 

[Greg]

I love the Jays. I watch just about every game. :)

Good luck with your puzzle!

 

[Opalg]

Let $X$ be the set $\{1,2,3,4\}^4$ with the Hamming metric. The computer picks a point in $X$. Each time you pick a point in $X$, the computer will react positively if the Hamming distance from its point to yours is $\leqslant1$. In other words, you will win if the computer's point is in the Hamming ball of radius $1$ centred at your point. To ensure that you win, you must select a number of points such that the unit balls centred at those points cover the entire set $X$. So one way of formulating the problem is: what is the least number of unit balls needed to cover $X$? This is a Hamming covering problem.

Unfortunately, I know nothing about coding theory (the subject barely existed back in the days when I was a student), so I do not know whether this reformulation of the problem will help towards solving it. A search for Hamming covering problem shows that there has been a lot of work on this area, but I could not find a solution to this particular problem. The expression NP-complete seems to occur often enough in the references to make it seem that such problems may not be straightforward.

 

[Wilmer]

Thanks Opal. I'll try and "digest" that "new to me" stuff.

Been trying along "elimination" method;
but can't seem to get to a "bang bang" solution.

Do you think it's possible using the Nim style?

Nim Strategy

 

[Opalg]

Having read a bit about Hamming distance and error-correcting codes, I came up with this list: $$\begin{matrix}1111&3111 \\ 2412 & 4412 \\ 1413 & 3413 \\ 2114 & 4114 \\ 2221 & 4221 \\ 1322&3322 \\ 2323&4323 \\ 1224&3224 \\ 2331&4331 \\ 1232&3232 \\ 2233&4233 \\ 1334&3334 \\ 1441& 3441 \\ 2142&4142 \\ 1143&3143 \\ 2444&4444 \end{matrix}$$ I believe that this set of $32$ numbers has the property that if you choose any four-digit number using the digits $1,2,3,4$, then you can find a number in the above list that has at least three of its four digits in their correct positions.

I don't really have a proof of that claim, so challenge number 1 is either to prove it or to disprove it.

Assuming that my claim is correct, then challenge number 2 is to find a list of fewer than 32 numbers that will do the same job. As mentioned in comment #5 above, there are 256 possible numbers, and each number on the list covers 13 of them. So the list necessarily contains at least $\left\lceil \dfrac{256}{13}\right\rceil = 20$ numbers. There is plenty of gap between 20 and 32, but my guess is that the minimum size of the list must be closer to 32 than to 20.

 

[Wilmer]

I'm pretty sure solution is 24.

https://books.google.co.uk/books?id...#v=onepage&q=hamming covering problem&f=false

Shown somewhere in that site.