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'"?

[bushindo]

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'"?

I'd like some clarification for the part in bold. My understanding of the trial is the following

Each trial consists of the player specifying a binary sequence of length 26 (each element is either Red or Black). The host then tells the player how many elements of the sequence are correct.

The player then repeats the trials, with the goal of minimizing the number of trials required in order to arrive at the correct sequence. Is this correct?

[plainglazed]

Yes, I believe so. The original sequence of the half of the deck in play never changes. First trial is basically, as you said, a binary sequence of Red and Black of length 26 with the responder stating the number of cards that are correct in color and position. The second trial would be another such sequence where presumably one or more of the elements is switched (so not necessary to repeat the first trial) and the responder again states the number of cards that are correct in color and position. Etc.

EDIT: stating the correct position and color of all twenty-six cards counts as the last trial.

[bonanova]

Guess the colored marbles, on steroids!

[plainglazed]

or the evil two-faced mega-Mastermind... tried to search to see if similar had been proferred. did i fail?

[bonanova]

or the evil two-faced mega-Mastermind... tried to search to see if similar had been proferred. did i fail?

I believe it's all new. And I'm thinking ... I'm thinking the number might be astronomical.

It's arithmetic, geometric, factorial or exponential. My money is on one of the last two.

[plainglazed]

am thinking double digits at least. but by judging the local BrainDen logicians, especially after who's to say?

[bub]

I believe the answer to be one. She states in the puzzle that she cut the deck in two. It dose not mention that she shuffled the deck. It is well known that all new decks of card come in suits, alternating betwwen red and black. with the ace of spades being the bottom card. Since you have only two suits in each deck, you should start with red count out 13 cards and then switch to black for the last 13. If she shuffled the answer would be close to 26 to the 26th power.

[Time Out]

1st trial guess all red

2nd trial change first card only to black. Result will be +/- 1 , +1 = black, - 1=red.

Repeat this for each card in turn, get them all on the 27th trial.

From the 1st trial you will know how many of each color there are. If the last two or more cards are the same color it will be concluded quicker.

(Seeing as the Big Boys/Girls haven’t chipped in yet, this answer is probably BS)

[WitchOfSecrets]

I'm not going to get the minimum, but let's try a starting guess.

First, guess black for all. This tells you the number of black and red cards.

Then guess black for the first half and red for the second half. This lets you determine how many blacks and reds are in the second half of the deck, and consequently how many are in the first half of the deck.

Example: Let's suppose we get (total black) correct the first time. There are that many black cards in the whole deck.

Then we get Y correct. This equals the number of black cards in the first half (call that B1) + the number of red cards in the second half. The number of red cards in the second half must equal 13 - B2, where B2 is the number of black cards in the second half of the deck. So we have Y = B1 + 13 - B2, and (total black) = B1 + B2. This gives us:

(total black) + Y = 2B1 + 13

B1 = [(total black) + Y - 13]/2

Then we can get B2 (and R1 and R2).

That's four questions so far.

Using a similar trick can get us the number of blacks in the first and second "quarters" of the deck. (First 6 and 7 cards). Repeating it again can get us the number of blacks in the third and fourth quarters (Last 6 and 7 cards).

Hmm... all these odd numbers look bad. A 14/12 initial split is probably better. A single question can identify the colors of one pair of cards using this kind of technique, but can't get the colors of three cards, as far as I can tell.

I'm guessing the answer's around 13-15, but I wonder if there's some sneaky combination of staggered tests (test even cards, test first half, test first and third quarters, etc) that somehow gives an answer with certainty.

Edited May 31, 2012 by WitchOfSecrets

[EventHorizon]

I'm not going to get the minimum, but let's try a starting guess.

First, guess black for all. This tells you the number of black and red cards.

Then guess black for the first half and red for the second half. This lets you determine how many blacks and reds are in the second half of the deck, and consequently how many are in the first half of the deck.

Example: Let's suppose we get (total black) correct the first time. There are that many black cards in the whole deck.

Then we get Y correct. This equals the number of black cards in the first half (call that B1) + the number of red cards in the second half. The number of red cards in the second half must equal 13 - B2, where B2 is the number of black cards in the second half of the deck. So we have Y = B1 + 13 - B2, and (total black) = B1 + B2. This gives us:

(total black) + Y = 2B1 + 13

B1 = [(total black) + Y - 13]/2

Then we can get B2 (and R1 and R2).

That's four questions so far.

Using a similar trick can get us the number of blacks in the first and second "quarters" of the deck. (First 6 and 7 cards). Repeating it again can get us the number of blacks in the third and fourth quarters (Last 6 and 7 cards).

Hmm... all these odd numbers look bad. A 14/12 initial split is probably better. A single question can identify the colors of one pair of cards using this kind of technique, but can't get the colors of three cards, as far as I can tell.

I'm guessing the answer's around 13-15, but I wonder if there's some sneaky combination of staggered tests (test even cards, test first half, test first and third quarters, etc) that somehow gives an answer with certainty.

Lets say there are 4 cards to guess, and there are 2 red and 2 black.

It still ends up with a worst case scenario of #ofcards + 1 guesses, which is the same as the approach given by Time Out. Yes, the average case is improved, but the worst case is unchanged.

Or did I misinterpret your approach?

If this is what you thought of, I thought of it first thing too

[EventHorizon]

[spoiler= ]14... and once I figure out how/why it works, I'll let you know. (cmon computer, tell me the method, not just a bunch of numbers!)

This isn't necessarily the limit, but the result of a greedy search that took 14 guesses to resolve to a single guessed possibility (assuming the response given to a guess was always the one that left the most possibilities). So it might be 15, but probably not 16. Unless a greedy search doesn't produce the best strategy, which is entirely possible, then it might be 12 or 13. So I guess I'm saying 14+/-2.

[phil1882]

i belive witchofsecrets solution works better for a larger number of cards.

lets take the example of 6 cards, with a solution of 100011.

000000 3 so 3 red, 3 black

000111 4 so 2 of the red guesses are correct.

001011 4 so the bottom half is correct, only need the top half solved

010011 4

100011 correct in 5 guesses.

with 26 i belive it will take 16 guesses tops to get a solution using this method.

also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.

[phil1882]

looking further at witchofsecrets method, i belive i have derived a method that solves it in 9 guesses 60% of the time, with a 40% chance of requireing 10. to demonstrate this idea further, lets take the case of 32 colors to guess.

the hardest string i can find is... 10010110011010010110100110010110

which can be gotten in 10 guesses.

00000000000000001111111111111111 16

00000000111111110000000011111111 16

00001111000011110000111100001111 16

00110011001100110011001100110011 16

01010101010101010101010101010101 16

10011001100110011001100110011001 16

01011010010110100101101001011010 16

and so on.

in general, the number of trials nessicary is 2*log(2) n.

[Assassin.MTS]

this is my first Post in the forum

I thought of first trial in a period of 1 and 0 like 10101010101010101010101010 and each time reverse the order of 2bits starting from the beginning if the difference between the previous answer and the last one is +2 that mean those 2bit become in a correct order... if it is -2 the 2bit was in correct order before the reverse... that give us 14 trials... but if it is 0 that mean the 2bit are of the same color... and that send me back to 27 trials... Ooops

I don't find a good answer... but I thing there is something right in this way

[EventHorizon]

i belive witchofsecrets solution works better for a larger number of cards.

lets take the example of 6 cards, with a solution of 100011.

000000 3 so 3 red, 3 black

000111 4 so 2 of the red guesses are correct.

001011 4 so the bottom half is correct, only need the top half solved

010011 4

100011 correct in 5 guesses.

with 26 i belive it will take 16 guesses tops to get a solution using this method.

also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.

First, since it is not a power of 2, you get a little more information from the second guess by virtue of the fact that the response cannot evenly divide the colors (this is where this method happens to get the extra guess reduction).

Second, since you chose the string beforehand, you are simply showing a special case and not the worst case scenario. For instance, for the guess of 010011, if the response was 2, it would leave 2 possibilities. This would require 1 more guess for the worst case (in this branch of possibilities).

These are the possibilities before that guess 001110, 001101, 100011, 010011. So the bottom half was not necessarily correct at that point.

Edit:

Looking at equivalence classes, it's easy to see that the first guess will give the same amount of useful information regardless of what is guessed. So stick with 0's, since it gives a simple human-readable answer (ie, x number of this color).

Edited June 1, 2012 by EventHorizon

[EventHorizon]

i belive witchofsecrets solution works better for a larger number of cards.

lets take the example of 6 cards, with a solution of 100011.

000000 3 so 3 red, 3 black

000111 4 so 2 of the red guesses are correct.

001011 4 so the bottom half is correct, only need the top half solved

010011 4

100011 correct in 5 guesses.

with 26 i belive it will take 16 guesses tops to get a solution using this method.

also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.

As WitchOfSecrets initially explained, he had separate tests for determining "the number of blacks in the first and second 'quarters' of the deck" and "the third and fourth quarters." So he had tests like 0000111100000000 and 0000000000001111. This initial formulation was what I responded to initially.

looking further at witchofsecrets method, i belive i have derived a method that solves it in 9 guesses 60% of the time, with a 40% chance of requireing 10. to demonstrate this idea further, lets take the case of 32 colors to guess.

the hardest string i can find is... 10010110011010010110100110010110

which can be gotten in 10 guesses.

00000000000000001111111111111111 16

00000000111111110000000011111111 16

00001111000011110000111100001111 16

00110011001100110011001100110011 16

01010101010101010101010101010101 16

10011001100110011001100110011001 16

01011010010110100101101001011010 16

and so on.

in general, the number of trials nessicary is 2*log(2) n.

WitchOfSecrets did mention staggered tests, which is what your approach consists of. This does, in fact, improve upon the worst case of Time Out's solution. It does, however, make things a little hard to see why they are working.

The result of this is how you've handled the tests after the alternating one (ie 0101010101010101010101). Running your trials through my code, I see that the initial trials nearly cut the search space in thirds. The ones after the alternating trial aren't quite as useful. They only cut out about a third in the worst case. So, it seems, any gains you've made in the first half, are given up in the second. It seems to me that you'll end up around Time Out's worst case (perhaps a little better).

Looking strictly at the search space after each guess, the first half of your approach is not optimal. It's not bad, but not optimal. It is, however, easy to replicate.

Like I said previously, removing the 0000000000000000 guess does not buy you anything. It just makes things harder to visualize.

Hopefully you don't think I'm being too harsh here. It's just thought and observations before and after testing the method with my code. And speaking of code... here it is for those who know c++.

& mask; register unsigned int tmp; tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111); return ((tmp + (tmp >> 3)) & 030707070707) % 63; } void printbin(int byte) { for (int i = 0; i < numcards; i++) { if (byte & (1 << i)) printf("1"); else printf("0"); } } vector <int> *pruneit(int guess, int goal, vector <int> *poss) { vector <int> *newposs = new vector<int>; for(int i = 0; i < poss->size(); i++) { if (getCorrect(guess,poss->at(i)) == goal) { newposs->push_back(poss->at(i)); } } delete poss; return newposs; } int getintfrombin() { char buffer[64]; memset(buffer,0,sizeof(char)*64); cin >> buffer; int thenum = 0; for(int i = 0; i < numcards; i++) { if (buffer[i] == '1') { thenum += 1<<i; } } return thenum; } int main(int argc, char *argv[]) { if (argc > 1) { numcards = atoi(argv[1]); } mask = (1<<(numcards)) - 1; vector <int> *poss = new vector <int>; vector<int> guesses; vector<int> responses; int totals[numcards+1]; int command; while (1) { if (guesses.size() > 0) { cout << endl; cout << "Guess/Response List" << endl; for(int i = 0; i < guesses.size(); i++) { printbin(guesses.at(i)); cout << " (" << guesses.at(i) << ") - " << responses.at(i) << endl; } } if (poss->size() > 0) { cout << "Possibilities left == " << poss->size() << endl; } cout << "0 - Reset." << endl; cout << "1 - Check guess." << endl; cout << "2 - Check binary guess." << endl; cout << "3 - Find best guess." << endl; cout << "4 - Enter guess and response." << endl; cout << "5 - Enter binary guess and response." << endl; cout << "6 - List Possibilities." << endl; cout << "7 - Convert bin to int." << endl; cout << "8 - Find best guess in remaining items." << endl; cout << "Enter Command: "; cin >> command; if (command == 0) { responses.clear(); guesses.clear(); poss->clear(); } if ((command == 1) || (command == 2)) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } int i; if (command == 1) { cout << "Enter guess: "; cin >> i; } else { cout << "Enter guess in binary: "; i = getintfrombin(); } memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } cout << "guess = "; printbin(i); cout << " (" << i << ")" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } } if (command == 3) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } int limit; cout << "Enter limit (0 for no limit): "; cin >> limit; if (limit > (1<<numcards)) limit = (1<<numcards); if (limit==0) limit = (1<<numcards); int best = 1<<numcards; int i; int besti=0; for(i = 0; i < limit; i++) { cout << "\r" << i; memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } int max = totals[0]; for(int j = 1; j < numcards+1; j++) { max = max > totals[j] ? max : totals[j]; } if (max < best) { best = max; cout << endl << "guess = "; printbin(i); cout << " vvvvvvvvvvvvvvvvv" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } cout << "guess = "; printbin(i); cout << " ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl; cout << "new best!!!" << endl; besti=i; } //else if (max==best) //{ // cout << "\rguess = "; // printbin(i); // cout << " (" << i << ") is equivalent." << endl; //} } i = besti; memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } cout << endl << "guess = "; printbin(i); cout << " vvvvvvvvvvvvvvvvv" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } cout << "guess = "; printbin(i); cout << " ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl; } if ((command == 4) || (command == 5)) { int guess,goal; if (command == 4) { cout << "Enter guess: "; cin >> guess; } else { cout << "Enter guess in binary: "; guess = getintfrombin(); } cout << "Enter response: "; cin >> goal; guesses.push_back(guess); responses.push_back(goal); if (poss->size() > 0) { poss = pruneit(guess,goal,poss); } else { for(int i = 0; i < 1<<numcards; i++) { if (getCorrect(guess,i) == goal) { poss->push_back(i); } } } } if (command == 6) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } for(int i = 0; i < poss->size(); i++) { printbin(poss->at(i)); cout << " (" << poss->at(i) << ")" << endl; } cout << endl; } if (command == 7) { cout << "Enter binary: "; int thenum = getintfrombin(); cout << "The number is " << thenum << endl; } if (command == 8) { if (guesses.size() == 0) { cout << "Sorry, make an initial guess first (all initials equivalent)."; continue; } int best = 1<<numcards; int i,k; for(k = 0; k < poss->size(); k++) { i = poss->at(k); cout << "\r" << (poss->size()-k); memset(totals,0,sizeof(int)*(numcards+1)); for(int j = 0; j < poss->size(); j++) { totals[getCorrect(i,poss->at(j))]++; } int max = totals[0]; for(int j = 1; j < numcards+1; j++) { max = max > totals[j] ? max : totals[j]; } if (max < best) { best = max; cout << endl << "guess = "; printbin(i); cout << " vvvvvvvvvvvvvvvvv" << endl; for(int j = 0; j < numcards+1; j++) { cout << "response " << j << " = " << totals[j] << endl; } cout << "guess = "; printbin(i); cout << " ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl; cout << "new best!!!" << endl; } } } } return 0; }

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <memory.h>

#include <vector>


using namespace std;


int numcards=26;

unsigned int mask=0;


int getCorrect(int a, int b)

{

	//MIT HackMEM method for counting bits

	unsigned int n = (~(a ^ 

First off, you can choose a number of cards up to 31 (haven't really tested past 26). I could probably get it working for 32, but... meh. You give the number of cards as a command line argument. If nothing is given, it does 26.

You need to give an initial guess/trial first, this is so that it doesn't need to have a vector of 2^cards length to start off.

And I'll give some use cases once I get back from some volleyball.

this is my first Post in the forum

I thought of first trial in a period of 1 and 0 like 10101010101010101010101010 and each time reverse the order of 2bits starting from the beginning if the difference between the previous answer and the last one is +2 that mean those 2bit become in a correct order... if it is -2 the 2bit was in correct order before the reverse... that give us 14 trials... but if it is 0 that mean the 2bit are of the same color... and that send me back to 27 trials... Ooops

I don't find a good answer... but I thing there is something right in this way

Welcome to the Den

[EventHorizon]

The binary representations are done in reverse order, so the least significant bit is on the left. I didn't put in any bounds checking, for the most part, so if you try to break the code or enter something it's not expecting, it will likely crash or hang or something (so ctrl+c it if that happens).

Most commands won't work until you've entered the first guess (either command 4 or 5).

You enter a number of cards on the command line (perhaps I should have made a menu option for it too... oh well), and then it brings you to a menu. You enter a number corresponding to the command you want.

Entering a 0 resets everything.

Entering 1 and then an integer will show what distribution of possible color sequences is produced by that guess (binary representation of that integer) from the remaining possibilities.

Entering 2 and then a binary string of 1's and 0's (autofills with 0's if you don't enter a long enough string) will do the same as command 1, but for the binary representation.

Entering 3 will search through all possible guesses and find the one that has the flattest distribution (the smallest maximum). This guess then minimizes the worst case scenario because there are fewer possibilities (ie locally greedy search, which may not necessarily be globally optimal). This can be quite slow with a lot of cards (but gets faster will less cards or less remaining possibilities). I could speed this up significantly if I use equivalency classes, but that's a lot of extra complexity to find them and use them... so maybe later.

Entering 4 and an integer or 5 and a binary string followed by the desired response will cause it to restrict the pool of possible strings to the ones that result in that response when the given guess is made.

Entering 6 will list all sequences that could still be correct given the guesses and responses made.

Entering 7 will convert a binary string to an integer. This is a remnant from before I made entering binary strings work.

Entering 8 will restrict the possible guesses to the sequences that could still be correct, and it will find the one will the flattest distribution under that restriction.

And that's about it. ctrl+c to quit since I didn't put a quit option in.

If anyone actually tests it out or uses it, let me know what you think and if you want me to add an option or change something.

Edit: Also... I have no idea how it happened, but a b was capitalized (or maybe even more errors introduced) in the line "unsigned int n = (~(a ^ & mask;" in the getCorrect method. I didn't notice any other strange capitalizations introduced, but they may be there.

Edited June 1, 2012 by EventHorizon

[phil1882]

event horizon:

no i don't think you're being harsh, think your calling it as you see it. i don't doubt your math, but have you actually put the two first trails

00000000000000000000000000000000

and

00000000000000001111111111111111

into your code to see how much search space each one reduces?

I'm pretty sure the second one slightly more optimal. it gives the extra information of where the 1's are likely to be.

i didn't write a programming approach, so getting as many cut down by a third as i did is i believe fairly good.

Edited June 1, 2012 by phil1882

[EventHorizon]

event horizon:

no i don't think you're being harsh, think your calling it as you see it. i don't doubt your math, but have you actually put the two first trails

00000000000000000000000000000000

and

00000000000000001111111111111111

into your code to see how much search space each one reduces?

I'm pretty sure the second one slightly more optimal. it gives the extra information of where the 1's are likely to be.

i didn't write a programming approach, so getting as many cut down by a third as i did is i believe fairly good.

First guesses are all equivalent in the amount of information they give.

Just verified it with the code (at least with those two). Both leave 12870 possibilities when the reponse is 8 correct when used with a 16 card deck.

Guessing 000000000 at the first is the same as guessing 000000111111 with the second half of all strings in the search space flipped 0's for 1's. Since after that operation, the search space is the same, there is no real difference between any guess. There is always an operation to make it equivalent to any other.

All guesses by themselves produce the same distribution over the whole search space, it is the combination of them that lets us figure things out. Not only that, but the order of guesses obviously doesn't matter, so an optimality proof would involve this basic distribution and how it overlaps with itself to single out lone possibilities.

Just to point it out, this distribution produced by a guess is the Nth layer of Pascal's triangle, where N is the number of cards in the deck being guessed. (eg, 12870 = 16!/8!8! = 16 choose 8 = middle element of 8th layer of Pascal's triangle)

Also, something is either optimal (ie, the best), or it is not. Something cannot be more optimal than some other optimal thing. It's sorta like saying more best. I had a professor who harped on that, and it has sorta become my pet peeve too. So, instead just say better.

[EventHorizon]

Once guesses have been made, the order to get to that point doesn't matter. But choosing which sequence to guess next is important. So I'm not saying there are 14 specific guesses that will uniquely identify every possible string. In other words, history is a set and not a sequence in this case.

Just me being paranoid about how patently bad I am at explaining myself.

[EventHorizon]

An equivalent formulation of the question is to minimize guesses for a binary string when the hamming distance to an unknown string is given in response.

You could imagine a N-dimensional hypercube (yeah, easier said than done), and the strings are its vertices. Since you can rotate the hypercube any way you want, you can see any first guess is equivalent. You are just pointing to a vertex and the other person says how far away you are following the edges.

[augustinus]

do we must answer with either red or black? can i answer with blue or some other color that will be false nevertheless, it will make the number of trials become 26 for better or worse

[plainglazed]

I believe the answer to be one. She states in the puzzle that she cut the deck in two. It dose not mention that she shuffled the deck. It is well known that all new decks of card come in suits, alternating betwwen red and black. with the ace of spades being the bottom card. Since you have only two suits in each deck, you should start with red count out 13 cards and then switch to black for the last 13. If she shuffled the answer would be close to 26 to the 26th power.

hey bub, watch where you're going. i mean, welcome to BrainDen. get your point, should have probably stated she shuffled the deck. this puzzle was kinda a continuation of a previous one so one could presume the deck to have been previously used.

1st trial guess all red

2nd trial change first card only to black. Result will be +/- 1 , +1 = black, - 1=red.

Repeat this for each card in turn, get them all on the 27th trial.

From the 1st trial you will know how many of each color there are. If the last two or more cards are the same color it will be concluded quicker.

(Seeing as the Big Boys/Girls haven’t chipped in yet, this answer is probably BS)

all true, save for that last bit. had figured this to be the logical starting point

this is my first Post in the forum

I thought of first trial in a period of 1 and 0 like 10101010101010101010101010 and each time reverse the order of 2bits starting from the beginning if the difference between the previous answer and the last one is +2 that mean those 2bit become in a correct order... if it is -2 the 2bit was in correct order before the reverse... that give us 14 trials... but if it is 0 that mean the 2bit are of the same color... and that send me back to 27 trials... Ooops

I don't find a good answer... but I thing there is something right in this way

hello Assassin.MTS - ah yes, you've pointed out the dilemna quite well and welcome to the Den.

do we must answer with either red or black? can i answer with blue or some other color that will be false nevertheless, it will make the number of trials become 26 for better or worse

and @ augustinus - welcome to you as well. had originally intended only black and red as responses but am curious as to your method mentioned above.

sorry to have apparently abandoned this thread. have had a tough end of the week. didnt quote WoS above and am still working out Phil's extension of your reply. when first working out this puzzle, seemed to think that in the worst case, a comprehensive binary reduction would still take 26 trials. am rethinking/still thinking. and at EventHorizon, not a programmer but hope to try to follow your code to hopefully gain some insight into how that works.

maybe should have worded the question differently and asked for descriptions of methods that did better than 27 trials rather than asking for the minimum number of trials. probably still would have gotten to this same place fairly quickly - i.e. in way over my head.

[EventHorizon]

I can beat bub's 1. Just ask, "wait, how many cards are there to guess for now?" And it would be 2 to the 26th power... assuming the only possible replies were "twenty-six" or "you didn't get all of them." That problem would be like a blind person trying to solve a rubik's cube, and asking "is this it?" and the other person saying "nope." (Was it the movie UHF that had that?)

all true, save for that last bit. had figured this to be the logical starting point

Agreed. I was actually writing a similar post when I noticed Time Out already did the job before my post was ready. I thought about commenting on bonanova's "factorial or exponential" comment in that post... something about needing to confiscate an EH silver star

and at EventHorizon, not a programmer but hope to try to follow your code to hopefully gain some insight into how that works.

I used the binary representation of an integer to hold the binary string guesses, and simply brute force went through each possibility. That's why it is too slow with 26 cards when going through each possible guess's value for each possible target binary string when looking for the best one (though I could speed that up if I get motivated to). I do use MIT's HackMEM method for counting the number of bits (to speed that part up), which is pretty cool. Just figured out how that works. So nothing else all that insightful in the code itself.

[WitchOfSecrets]

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?