Bulls without cows: how many steps are needed to solve this?

Question

I'm bad at this sort of optimization problem so I'm asking for you, proud riddle solvers!

There's this huge hangar with 72 different airplanes.

• They come in six different colors
• Each color has four monoplanes, four biplanes and four triplanes
• Each group of four planes with the same color and number of wings has a different flag on its wings: Germany, Japan, U.S.A. and England

So, it's 6 different colors, 4 different flags and 3 different number of wings, and no plane has the same combination of these elements.

A friend walks in and I ask him to guess, like if it was a bulls and cows game. By guessing I mean he chooses a single plane and I tell him how many elements of that one plane match with the plane I had in mind.

Let's say I chose the yellow US biplane. He chooses the green German biplane. I tell him he guessed one element, but I don't tell him which. He has to choose his next planes so that he can make this first information useful.
Had he chosen the green German monoplane, he could have excluded all green planes, all German planes and all monoplanes in one go.

Of course, unlike a game of mastermind or bulls and cows, the elements are so different that he can't put the right solution in the wrong place. No planes with "Germany" wings or "three"-colored planes! So, no cows. Just bulls.

How many maximum attempts are necessary for him to identify (and guess) my plane?
What if I honestly told him it's not Japan (3/3/6 elements)?

Answer 1

It is impossible with fewer than six guesses, because it could happen that the correct color is one that your friend never guesses. This strategy gets every combination with six guesses:

1. Always guess a combination that has not been ruled out yet.
2. If possible, choose a combination with a color that has not been guessed before.
3. If still possible, choose a combination with a flag that has not been guessed before.

Stating that the flag is not Japan does not change the number of guesses, because it still requires six guesses to guarantee the color.

---

Represent the types of plane as 123, the flags as 1234, and the colors as 123456. Here's an exhaustive proof that the strategy works:

First guess: 111    
0: guess 222
    0: guess 333
        1: guess 344
            2: guess 345
                2: guess 346
        2: guess 334
            1: guess 343
            2: guess 335
                2: guess 336
    1: guess 233
        0: guess 324
            1: guess 342
            2: guess 325
                2: guess 326
        1: guess 244
            0: guess 323
                1: guess 332
            2: guess 245
                2: guess 246
        2: guess 234
            1: guess 243
            2: guess 235
                2: guess 236
    2: guess 223
        1: guess 232
            1: guess 322
            2: guess 242
        2: guess 224
            2: guess 225
                2: guess 226
1: guess 122
    0: guess 213
        0: guess 331
            2: guess 341
        1: guess 314
            0: guess 231
                2: guess 241
            2: guess 315
                2: guess 316
        2: guess 214
            1: guess 313
            2: guess 215
                2: guess 216
    1: guess 133
        0: guess 212
            0: guess 321
            1: guess 221
            2: guess 312
        1: guess 144
            2: guess 145
                2: guess 146
        2: guess 134
            1: guess 143
            2: guess 135
                2: guess 136
    2: guess 123
        1: guess 132
            2: guess 142
        2: guess 124
            2: guess 125
                2: guess 126
2: guess 112
    1: guess 121
        1: guess 211
            2: guess 311
        2: guess 131
            2: guess 141
    2: guess 113
        2: guess 114
            2: guess 115
                2: guess 116

Answer 2

Your friend needs to find the correct plane out of 72 possibilities. Assuming each question he asks has to be a yes/no question (otherwise he could just ask "what colour is the plane?" etc., making it trivial!), each answer he gets gives him one bit of information. 72 in binary is 1001000, which is 7 bits, so at least 7 questions are needed.

He can get the country easily with two questions. First:

"Is the country Germany or Japan?"

If yes, the second question is:

"Is the country Germany?"

If no, the second question is:

"Is the country England?"

Whatever the answers to the first two questions, by the end your friend will know what flag is on the plane. Now he needs to find the colour and the number of wings (18 possibilities).

There's no simple approach from here on, but basically he needs to split those 18 possibilities into (for instance) 16 and 2. E.g. he could ask:

"Is it a monoplane that's either blue or red?"

If the answer is yes, then obviously only one more question is needed. If the answer is no, then 16 possibilities remain. Split these possibilities into two sets of 8; a fourth question will tell him which of these 8 your plane is in. Then split that set of 8 into two sets of 4 and use a fifth question to reduce to one of those sets, and so on.

The answer is 7 questions.

---

If you tell him to begin with that it's not Japan, then instead of 72 possibilities we start off with 54, which is 110110, 6 bits long. So in this case 6 questions are needed.

Answer 3

This attempt assumes your friend must guess at the complete configuration and will then be told how many elements are correct:

This strategy gets the answer in 7 guesses, and 6 is a lower bound (there are 6 colours, so no strategy can guarantee getting it before 6)

Guess three configurations, none of which share any elements.

The possible results (ignoring order) for these guesses are:

001
002
003
011
012
111

For 001 you now know the wing number and the country (wing number is the one you chose when 1 guess was correct, country is the remaining unchosen one). Select these and work your way through the remaining colours for victory in 6 guesses.

For 002 you know the wing number and one of {country, colour}. Keep number and country the same (as when 2 were correct), choose the next colour.

• If number of guesses correct drops to 1, you previously had the right color and you know the country is the fourth (so far unchosen) one. Victory in 5!
• Otherwise you had both number and country right; keep going through the colours until you get all three right. Victory in 6.

For 003, you have obviously won already.

For 011 choose the next colour, with the same number/country combination as one of your previous '1 right' guesses.

• 0 tells you that the colour was correct, that the wing number was correct on the other '1 right' guess, and that the country must be the remaining one. Victory in 5.
• 1 tells you that the colour was (and still is) incorrect and that one of {country, number} is right. Try a fifth colour with the other {country, number} pair.
  • 0 tells you your previous color choice was correct. You now know that the country is the one not yet selected and the wing number is the one from the the previous step. Victory in 6.
  • 1 tells you that the color was (and is) wrong. You know that the colour is the sixth (thus far unchosen) one and you know that the {country, number} is one of two pairs. Try both for victory in 7.
  • 2 tells you that your colour is now correct and that there are 2 possible pairs of {country, number}. Try both for victory in 7.
• 2 tells you that your colour is now correct and that the {country, number} are reduced to 2 combinations. Try both out, for victory in 6.

For 012 choose one element from the '1 right' set and guess it alongside the complementary 2 elements of the '2 right' set. There are 3 possibilities; try them all out for victory in 6.

For 111 take 1 element of 1 set, guess it with the complementary elements of another.

• if 0 are right, the replaced element was correct
• if 1 is right, neither the replaced element not the replacing one were correct; the corresponding element in the third set is correct.
• if 2 are right, the replacing element was correct. Whatever the result, we know one element at a cost of one guess. Repeat for the other 2 element types for victory in 6.