Skip to main content
Puzzling

Return to Answer

Post Timeline

added 258 characters in body
Source Link
noedne
noedne
  • 27.3k
  • 1
  • 80
  • 156
  1. How does the minimal maximum number of guesses change when the number of possible colors changes?
    What if there are five colors? 5 guesses
    Seven colors? 6 guesses
    k colors? unknownunknown, but see below for bounds when k is large
    For this problem, hold the length of the secret code constant at 4.
  2. How does the minimal maximum number of guesses change when the length of the secret code changes?
    What if it is length three? 5 guesses
    Five? unknownunknown
    n? unknownunknown
    For this problem, hold the number of possible colors constant at 6.

In Theorem 1, the authors also prove that if we hold the length of the secret code constant at 3 and have k colors where k ≥ 5, the minimal maximum number of guesses is ⌊(k - 1)/3⌋ + 4.following:

  1. If we hold the length of the secret code constant at 3 and have k colors where k ≥ 5, the minimal maximum number of guesses is ⌊(k - 1)/3⌋ + 4.
  2. If we hold the length of the secret code constant at 4 and have k colors where k ≥ 16, the minimal maximum number of guesses is between ⌊k/4⌋ + 4 and ⌊k/4⌋ + 6.
  1. How does the minimal maximum number of guesses change when the number of possible colors changes?
    What if there are five colors? 5 guesses
    Seven colors? 6 guesses
    k colors? unknown
    For this problem, hold the length of the secret code constant at 4.
  2. How does the minimal maximum number of guesses change when the length of the secret code changes?
    What if it is length three? 5 guesses
    Five? unknown
    n? unknown
    For this problem, hold the number of possible colors constant at 6.

In Theorem 1, the authors also prove that if we hold the length of the secret code constant at 3 and have k colors where k ≥ 5, the minimal maximum number of guesses is ⌊(k - 1)/3⌋ + 4.

  1. How does the minimal maximum number of guesses change when the number of possible colors changes?
    What if there are five colors? 5 guesses
    Seven colors? 6 guesses
    k colors? unknown, but see below for bounds when k is large
    For this problem, hold the length of the secret code constant at 4.
  2. How does the minimal maximum number of guesses change when the length of the secret code changes?
    What if it is length three? 5 guesses
    Five? unknown
    n? unknown
    For this problem, hold the number of possible colors constant at 6.

In Theorem 1, the authors also prove the following:

  1. If we hold the length of the secret code constant at 3 and have k colors where k ≥ 5, the minimal maximum number of guesses is ⌊(k - 1)/3⌋ + 4.
  2. If we hold the length of the secret code constant at 4 and have k colors where k ≥ 16, the minimal maximum number of guesses is between ⌊k/4⌋ + 4 and ⌊k/4⌋ + 6.
Source Link
noedne
noedne
  • 27.3k
  • 1
  • 80
  • 156

Gerold Jäger and Marcin Peczarski answer some of these questions in The number of pessimistic guesses in Generalized Mastermind.

Table 1, reproduced below, gives the minimal maximum number of guesses for many combinations of pegs and colors (the number of pegs is the length of the code). For example, the standard variant of 4 pegs and 6 colors has a minimal maximum number of 5 guesses as shown by Knuth. These values were computed using a computer program described in the paper.

1 color 2 colors 3 colors 4 colors 5 colors 6 colors 7 colors 8 colors 9 colors 10 colors
1 peg 1 2 3 4 5 6 7 8 9 10
2 pegs 1 3 3 4 4 5 5 6 6 7
3 pegs 1 3 4 4 5 5 6 6 6 7
4 pegs 1 4 4 4 5 5 6 6 7 7
5 pegs 1 4 4 5 5
6 pegs 1 5 5 5
7 pegs 1 5 5
8 pegs 1 6

Bolded values are new contributions.

Using the table, we can answer some of the questions:

  1. How does the minimal maximum number of guesses change when the number of possible colors changes?
    What if there are five colors? 5 guesses
    Seven colors? 6 guesses
    k colors? unknown
    For this problem, hold the length of the secret code constant at 4.
  2. How does the minimal maximum number of guesses change when the length of the secret code changes?
    What if it is length three? 5 guesses
    Five? unknown
    n? unknown
    For this problem, hold the number of possible colors constant at 6.

In Theorem 1, the authors also prove that if we hold the length of the secret code constant at 3 and have k colors where k ≥ 5, the minimal maximum number of guesses is ⌊(k - 1)/3⌋ + 4.