With Flying Colors

[plainglazed]

After safely landing and partially thawing in Yellowknife, the logicians returning from the ACofL Fresh Air/Fresh Ideas annual seminar began to settle their nerves as they settled down in the airport bar before continuing onto the next leg of their journey. As would be expected, not too many drinks later, one of the logicians pulled out their deck of complimentary playing cards. She cut the deck exactly in half, and proposed to the others: "Tell me the color of each of these twenty-six cards in succession. For each try, I'll tell you how many you have gotten correct. What is the fewest number of trials before I'm guaranteed to say, 'twenty-six'"?

[EventHorizon]

What if our search idepends on the previous responses somehow? If we hear that there are X black cards, can we use that information to modify our strategy?

I assume this is in reponse to my statement about order doesn't matter. I did explain that statement in post #21. The search does depend on the set of previous guesses and responses (just not on the order of them to get to that point) to decide the next sequence of cards to guess. So if we guess all red, and we get a response (which tells us the total red and total black cards)... the search should definitely be different based on the response given (though perhaps not initially in that exact scenario... I'm not sure yet).

[Time Out]

or less]

Guess all black initially,then for the next8 trials change 3 consecutive cards to red.

For each…..

-3 = 3 blacks

+3 = 3 reds

-1 = 1 red, 2 blacks

+1 = 2 reds, 1 black

+3 / -3 requires no further trials

+1/-1 may need 2 more trials, using the appropriate mix . If after 1^st or 2nd trials you aren’t scoring +3 then the 3^rd untried position has to be it.

The colors of the last 2 cards can be easily worked out.

Incorporate any “untried positions” into the first trial on the final 2 cards.

[plainglazed]

So sometimes/more often than not you would do better than 27 trials but no guarantee. This is actually more along the lines of what i was thinking of to reduce the number of trials. Can fairly simply guarantee in at most twenty one trials, the order of the twenty six cards. As for EH's 14-ish, starting to get a better grip on the ideas but as far as my high speed population counter - am still processing...

[phil1882]

so for 26 cards, a guess of all black, an answer of 13 leaves the most possibilities. (roughly 10 million.)

then guessing 13 black, 13 red, leaves 2.9 million in the worst case. (an answer of 12 or 14. surprizingly, an answer of 13 is impossible.)

then guessing 00000001111110000001111111 leaves 831,348 possibilities (an answer of 12 or 14.)

then guessing 00001110001110001110001111 leaves 233,051 possibilites.

then 00110010110010110010110011 leaves 64,170

then 01010101010101010101010101 leaves 17,225.

asumming an answer of 12 after each level becides the first one,

here are the potentail answers left.

carddata2.txt

[plainglazed]

hey phil - still cant see if or to what extent this method will reduce the number of trials. the last four alone can take three trials as far as i can tell. also, tho suspect its true at least initially, is leaving the most possibilities and working that result alone necessarily the case requiring the most trials?