Stamps and foreheads

[bushindo]

This is based on bonanova's puzzle

Here's a game that goes as in the following

* There is a host with 14 stamps, 7 red and 7 blue. There are five players- A, B, C, D, and E.
* In the beginning, the host affixes two stamps to each of the 5 players' head. The remaining 4 stamps go into the host's pocket. Each player can see the stamps on the remaining 4 players, but can not see his own stamps nor the four in the host's pocket.
* Starting from A to E (and then looping back to A and so on), the host asks if each player definitively knows his stamps distribution (RR, BB, or RB). If the player does not know, the host goes on to the next player. No guessing is allowed.
* The game goes as follows

1st turn- player A: I do not know
2nd turn- player B: I do not know
3rd turn- player C: I do not know
4th turn- player D: I do not know
5th turn- player E: I do not know
Host- Alright, to help you, I'll now reveal two stamps from my pocket. *At this point, the host pulls out two of the four stamps in his pocket and shows everyone. The game then continues as before*
6th turn- Player A: I do not know.
…

Question- what is the longest possible number of turns required before a player definitely knows his color?

[CaptainEd]

Wow! This is a lot of cases, and I'll probably miss some in my exhaustive enumeration. Are you suggesting that we might be able to REASON this out, rather than list many dozens of cases? Thanks for the puzzle, by the way

[bonanova]

Let the color distributions, for A B C D E (H), have a form of the type xx xy xy yy xy (yy) e.g.,
where x,y = R,B in some order and (H) refers to the two stamps exposed by the Host.

The first five answers dictate that no four players [heh] collectively have 7 similar stamps.

Else the fifth would know.

This eliminates all distributions of the form

1. xx xx xx xy yy (--)

including every permutation of the first five.

Else the yy player knows his color

After the host exposes two stamps, let's say one of each color,

A's response (response 6) precludes

1. -- xx xx xy xy (xy) and
2. -- xx xx xx yy (xy)

along with every permutation for players B-E.

Player A would be yy in each of those cases, and would know it.

If H shows stamps of similar color, these distributions are precluded.

1. (--) xx xx xy yy (xx) and
2. (--) xx xy xy xy (xx)

along with every permutation for players B-E.

Player A would be yy in each of those cases, and would know it.

That's a start.

[CaptainEd]

At player B's first turn, B is not seeing bb .. rr rr rr because if he did, he would reason

" I don't have rb, because A would correctly reason that A has bb. I don't have rr, because there aren't that many reds. Therefore, I have bb"

But he didn't say that, so by the time B says "I don't know", we all know that case

bb bb rr rr rr

is also ruled out.

[bonanova]

It may be fruitful to assume a distribution and then see how it can be determined.

It seems profitable to ask: Are any cases undecidable?

The most ambiguous case is likely xy xy xy xy xy (xy).

Everyone would see 5x and 5y and say (responses 6-10) I don't know. (idk)

Everyone knows they could be xy, therefore.

Suppose a player wonders if he is xx. Can he decide? No. At least not after responses 6-10.

If a player is xx (and sees the others are xy) he knows the others would see still see only 6 x's.

They could not therefore conclude (during 6-10) that they are yy.

After responses 6-10, no player can decide whether his colors are similar or not.

Go to the next round: Responses 11-15.

If one player is xx, (and responses 6-10 are all idk) the others can decide something.

They can decide they are not also xx: the non-xx players know they are either xy or yy.

But that's not enough to know which. Responses (11-15) will all be idk.

Go to the next round: Responses 16-20.

Every player knows the distribution might be xy xy xy xy xy (which it is)

but to be certain, he must know that he himself is xy:

he must rule out the possibility that his colors are similar.

Even If another player saw his (possible) xx, the other player could not

(during 11-15) declare his colors: he could be xy or he could be yy.

So (16-20) (which must still be all idk) must prove to at least one player that his colors are dissimilar.

For now, I don't see how. So provisionally, this case seems undecidable.

Of course, Bushindo would not do this to us. So I will think some more.

[bushindo]

Wow! This is a lot of cases, and I'll probably miss some in my exhaustive enumeration. Are you suggesting that we might be able to REASON this out, rather than list many dozens of cases? Thanks for the puzzle, by the way

There are many cases on purpose. The reasoning should be straight forward with the proper tools and elimination procedure.

[bushindo]

It may be fruitful to assume a distribution and then see how it can be determined.

It seems profitable to ask: Are any cases undecidable?

The most ambiguous case is likely xy xy xy xy xy (xy).

Everyone would see 5x and 5y and say (responses 6-10) I don't know. (idk)

Everyone knows they could be xy, therefore.

Suppose a player wonders if he is xx. Can he decide? No. At least not after responses 6-10.

If a player is xx (and sees the others are xy) he knows the others would see still see only 6 x's.

They could not therefore conclude (during 6-10) that they are yy.

After responses 6-10, no player can decide whether his colors are similar or not.

Go to the next round: Responses 11-15.

If one player is xx, (and responses 6-10 are all idk) the others can decide something.

They can decide they are not also xx: the non-xx players know they are either xy or yy.

But that's not enough to know which. Responses (11-15) will all be idk.

Go to the next round: Responses 16-20.

Every player knows the distribution might be xy xy xy xy xy (which it is)

but to be certain, he must know that he himself is xy:

he must rule out the possibility that his colors are similar.

Even If another player saw his (possible) xx, the other player could not

(during 11-15) declare his colors: he could be xy or he could be yy.

So (16-20) (which must still be all idk) must prove to at least one player that his colors are dissimilar.

For now, I don't see how. So provisionally, this case seems undecidable.

Of course, Bushindo would not do this to us. So I will think some more.

See the part in red. My calculations show that the players would definitely end the game during that phase for the starting case of all RB stamps.

[CaptainEd]

I don't feel strong enough yet, but the Den is strong...

As I pointed out, B can infer that

BB BB RR RR RR is ruled out, and, by complementation

RR RR BB BB BB

As the players continue through with this logic, by the time D is done with question 4, we've ruled out all (2 pair, 3 pair) cases. This means, if E sees (2 pair, 2 pair), he/she knows to announce RB.

[bonanova]

A list of color combinations might be helpful.

They can be solved individually.

Taxonomy of color distributions [combinations]
Colors held in some order by A B C D E

Case C40
Host colors are split 4-0 [yyyy]
Host colors exposed: [yy] gives two cases

1. xx xx xx xy yy Eliminated by Responses (1-5) bonanova
2. xx xx xy xy xy

Case C31
Host colors are split 3-1 [xyyy]
Host colors exposed: a:[xy] or b:[yy] gives six cases

1. xx xx xx yy yy Eliminated by Responses (1-5) CaptainEd
2. xx xx xy xy yy
3. xx xy xy xy xy

Case C22
Host colors are split 2-2 [xxyy]
Host colors exposed: a:[xy] or b:[yy] gives six cases

1. xx xx xy yy yy
2. xx xy xy xy yy
3. xy xy xy xy xy <= seems to be the toughest case to decide.

In Case C22, Host colors exposed: c:[xx] might be considered.

But it gives the same combinations as b:[yy]

Permutations will be needed to determine the player who first calls out his colors.

[CaptainEd]

It may be fruitful to assume a distribution and then see how it can be determined.

It seems profitable to ask: Are any cases undecidable?

The most ambiguous case is likely xy xy xy xy xy (xy).

Everyone would see 5x and 5y and say (responses 6-10) I don't know. (idk)

Everyone knows they could be xy, therefore.

Suppose a player wonders if he is xx. Can he decide? No. At least not after responses 6-10.

If a player is xx (and sees the others are xy) he knows the others would see still see only 6 x's.

They could not therefore conclude (during 6-10) that they are yy.

After responses 6-10, no player can decide whether his colors are similar or not.

Go to the next round: Responses 11-15.

If one player is xx, (and responses 6-10 are all idk) the others can decide something.

They can decide they are not also xx: the non-xx players know they are either xy or yy.

But that's not enough to know which. Responses (11-15) will all be idk.

Go to the next round: Responses 16-20.

Every player knows the distribution might be xy xy xy xy xy (which it is)

but to be certain, he must know that he himself is xy:

he must rule out the possibility that his colors are similar.

Even If another player saw his (possible) xx, the other player could not

(during 11-15) declare his colors: he could be xy or he could be yy.

So (16-20) (which must still be all idk) must prove to at least one player that his colors are dissimilar.

For now, I don't see how. So provisionally, this case seems undecidable.

Of course, Bushindo would not do this to us. So I will think some more.

See the part in red. My calculations show that the players would definitely end the game during that phase for the starting case of all RB stamps.

I'm confused, as often. I thought we were facing one particular run of this game, and we are seeking the one case and reveal for which A does NOT announce his stamps at step 6. The phrase "starting case of all RB stamps" makes me think we have to make a general solution for all runs of the game.

[bushindo]

It may be fruitful to assume a distribution and then see how it can be determined.

It seems profitable to ask: Are any cases undecidable?

The most ambiguous case is likely xy xy xy xy xy (xy).

Everyone would see 5x and 5y and say (responses 6-10) I don't know. (idk)

Everyone knows they could be xy, therefore.

Suppose a player wonders if he is xx. Can he decide? No. At least not after responses 6-10.

If a player is xx (and sees the others are xy) he knows the others would see still see only 6 x's.

They could not therefore conclude (during 6-10) that they are yy.

After responses 6-10, no player can decide whether his colors are similar or not.

Go to the next round: Responses 11-15.

If one player is xx, (and responses 6-10 are all idk) the others can decide something.

They can decide they are not also xx: the non-xx players know they are either xy or yy.

But that's not enough to know which. Responses (11-15) will all be idk.

Go to the next round: Responses 16-20.

Every player knows the distribution might be xy xy xy xy xy (which it is)

but to be certain, he must know that he himself is xy:

he must rule out the possibility that his colors are similar.

Even If another player saw his (possible) xx, the other player could not

(during 11-15) declare his colors: he could be xy or he could be yy.

So (16-20) (which must still be all idk) must prove to at least one player that his colors are dissimilar.

For now, I don't see how. So provisionally, this case seems undecidable.

Of course, Bushindo would not do this to us. So I will think some more.

See the part in red. My calculations show that the players would definitely end the game during that phase for the starting case of all RB stamps.

I'm confused, as often. I thought we were facing one particular run of this game, and we are seeking the one case and reveal for which A does NOT announce his stamps at step 6. The phrase "starting case of all RB stamps" makes me think we have to make a general solution for all runs of the game.

I see your point. The confusion is entirely my fault. I revised the OP to remove this confusion.

[bonanova]

It may be that only one distribution of colors is possible, leading to a unique answer.

We'll see.

Edit after reading revised OP:

Nope, we have to eliminate [preferably] or analyze each case. More sleepless nights.

[CaptainEd]

Yup, but fortunately, reasoning should be straight forward with the proper tools and elimination procedure. I doubt I'll solve it before February...

[Prime]

Let me try and sort this out.

Let’s take the case where the host put away two different labels thus leaving 6 of each in the play. And let’s forget about the first round of guessing for now.

I designate a contestant wearing a pair of one color as 0, a pair of another color as 1, and a mixed pair as x. The six possible variations (disregarding the order) are: 00011; x0011; xx001; xxx01; xxxx0; xxxxx. Other possibilities: 11100, xx110, and xxxx1 are symmetrical and use the same logic.
The guessing by elimination would be as following.

When a contestant observes:
1) 0111, he knows he has 0. (The fastest ordered guessing variation would be ?0111, where “?” can guess on his first turn, he is a “0”.)
2) 0011, contestant can guess he has x, when it is his turn after one 0 and one 1 have not guessed. (Fastest variation: 01?01, where “?” guesses on his first turn, he is an “x”.)
3) 001x, the man who sees that, is able to exclude himself from having 1 after x has not guessed having observed not guessing by 0 and 1. (Fastest path: 01x?0.)
4) 01xx, after 0 and 1 have not guessed, followed by two x-s, the contestant can deduce he is neither 0, nor 1. (01xx? guesses on the first turn.)
5) 0xxx, contestant can figure himself for x on his second turn after not guessing on his first try and seeing 0 not guessing followed by all 3 x-s failing to make their deduction. (Fastest variation ?0xxx.)
6) xxxx, when all four x-s have failed and one them twice the next man can announce, he has mixed colors. In this situation where all 5 men are x, the second man in the line must be the first to deduce his labels on his second turn: x?xxx.

The longest path to guessing seems to be the variation xxxx0, where the fourth contestant in line is the first man who shall be able to make the deduction on his second turn. Another such variation is 0xxx1, where again the fourth contestant guesses on his second turn.

With 6 labels of each color, I don’t see how the first round of guessing where 14 labels are engaged, can provide any useful information to the contestants at all. If the host threw away two labels of the same color, then the first round could eliminate the possibility of all 7 labels of the same color used on the foreheads. In that case if 1 represents a pair of the color of which 7 labels are in play and 0 -- the color of 5, the fastest guessing variation after the host throws away two labels would be 00111.

[Prime]

Let me try and sort this out.

Let’s take the case where the host put away two different labels thus leaving 6 of each in the play. And let’s forget about the first round of guessing for now.

I designate a contestant wearing a pair of one color as 0, a pair of another color as 1, and a mixed pair as x. The six possible variations (disregarding the order) are: 00011; x0011; xx001; xxx01; xxxx0; xxxxx. Other possibilities: 11100, xx110, and xxxx1 are symmetrical and use the same logic.

The guessing by elimination would be as following.

When a contestant observes:

1) 0111, he knows he has 0. (The fastest ordered guessing variation would be ?0111, where “?” can guess on his first turn, he is a “0”.)

2) 0011, contestant can guess he has x, when it is his turn after one 0 and one 1 have not guessed. (Fastest variation: 01?01, where “?” guesses on his first turn, he is an “x”.)

3) 001x, the man who sees that, is able to exclude himself from having 1 after x has not guessed having observed not guessing by 0 and 1. (Fastest path: 01x?0.)

4) 01xx, after 0 and 1 have not guessed, followed by two x-s, the contestant can deduce he is neither 0, nor 1. (01xx? guesses on the first turn.)

5) 0xxx, contestant can figure himself for x on his second turn after not guessing on his first try and seeing 0 not guessing followed by all 3 x-s failing to make their deduction. (Fastest variation ?0xxx.)

6) xxxx, when all four x-s have failed and one them twice the next man can announce, he has mixed colors. In this situation where all 5 men are x, the second man in the line must be the first to deduce his labels on his second turn: x?xxx.

The longest path to guessing seems to be the variation xxxx0, where the fourth contestant in line is the first man who shall be able to make the deduction on his second turn. Another such variation is 0xxx1, where again the fourth contestant guesses on his second turn.

With 6 labels of each color, I don’t see how the first round of guessing where 14 labels are engaged, can provide any useful information to the contestants at all. If the host threw away two labels of the same color, then the first round could eliminate the possibility of all 7 labels of the same color used on the foreheads. In that case if 1 represents a pair of the color of which 7 labels are in play and 0 -- the color of 5, the fastest guessing variation after the host throws away two labels would be 00111.

In the xx001 situation it is "1" who should guess first. The step (3) of the elimination table from my previous post is incorrect.

The elimination table has to be reworked.

[Prime]

I’ll try again.

Just the case of 6 red and 6 blue labels, disregarding the round before the host revealed two of the stamps.
Let’s use the following terminology:
r = a man with two red stamps; b = man with two blue stamps; x = man with a mix.
x' = NOT (x was unable to deduce his stamps.)
* = AND;
+ = OR;
x(condition) = x can deduce his stamps based upon the condition. E.g., x(r’) means x can deduce his stamps after r has failed.

There are only 6 significant cases (disregarding the order) based on the number of mixed colors in the lineup -- from zero to 5: rrrbb, xrrbb, xxrrb, xxxrb, xxxxr, xxxxx. “r” and “b” may be swapped for one another making logically identical cases.

The 6 cases may be resolved as following:

1) r₁ r₂ r₃ b₁ b₂ ==> b() + r₃(r₂’(r₁’)).
Example 1: r₁’ b₁ r₂ r₃ b₂, where b₁ solves on his turn; OR Ex.2: r₁’ r₂’ r₃ b₁ b₂, where r₃ solves after r₁ and r₂ failed.

2) x r₁ r₂ b₁ b₂==> x(r’ * b’) + r₂(r₁’) + b₂(b₁’)
Ex.1: r₁’ b₁’ x r₂ b₂. Ex.2: r₁’ r₂ b₁ b₂ x. Ex.3: b₁’ x’ r₁’ b₂ r₂.

3) x₁ x₂ r₁ r₂ b ==> b() + x(r₂’(r₁’)).
Ex.1: b r₁ r₂ x₁ x₂. Ex.2: r₁’ r₂’ x₁ b x₂.

4) x₁ x₂ x₃ r b ==> x(r’ * b’).
Example: x₁’ r’ b’ x₂ x₃.

5) x₁ x₂ x₃ x₄ r ==> x₁(x₂’(x₁’ * r’)).
Ex.1: x₁' r' x₂' x₃' x₄' (x₁ solves on his second turn). Ex.2: x₁'' x₂' x₃' x₄' r' (x₂ solves on his second turn.)

6) x₁ x₂ x₃ x₄ x₅ ==> x₂(x₁’(x’(x₁’ * x₂’))).
Example: x1'' x₂' x₃' x₄' x₅', where x₂ can deduce that he is a mix on his second turn after x₁ fails for the second time.

I derive deduction strings for each case based on perspectives that the men in the lineup may have and deduction strings from those perspectives. Take for example case (3). An x in that line up may suppose he is either part of the case (2), or (3). Without any additional data, r may think he is in either (3) or (4). Whereas b in lineup (3) simply knows he is b.

It appears, the longest deduction string here is one where the men made one full round of non-guessing whereafter in the second round the second man in the line up must deduce his stamps. There are several possibilities for that:
x₁'' x₂' x₃' x₄' x₅';
x₁'' x₂' x₃' x₄' r';
r'' x₁' x₂' x₃' b'.

The first round, where 14 stamps were in play, does not seem to offer any useful information for those longest deduction variations above.

[bushindo]

I’ll try again.

Just the case of 6 red and 6 blue labels, disregarding the round before the host revealed two of the stamps.

Let’s use the following terminology:

r = a man with two red stamps; b = man with two blue stamps; x = man with a mix.

x' = NOT (x was unable to deduce his stamps.)

* = AND;

+ = OR;

x(condition) = x can deduce his stamps based upon the condition. E.g., x(r’) means x can deduce his stamps after r has failed.

There are only 6 significant cases (disregarding the order) based on the number of mixed colors in the lineup -- from zero to 5: rrrbb, xrrbb, xxrrb, xxxrb, xxxxr, xxxxx. “r” and “b” may be swapped for one another making logically identical cases.

The 6 cases may be resolved as following:

1) r₁ r₂ r₃ b₁ b₂ ==> b() + r₃(r₂’(r₁’)).

Example 1: r₁’ b₁ r₂ r₃ b₂, where b₁ solves on his turn; OR Ex.2: r₁’ r₂’ r₃ b₁ b₂, where r₃ solves after r₁ and r₂ failed.

2) x r₁ r₂ b₁ b₂==> x(r’ * b’) + r₂(r₁’) + b₂(b₁’)

Ex.1: r₁’ b₁’ x r₂ b₂. Ex.2: r₁’ r₂ b₁ b₂ x. Ex.3: b₁’ x’ r₁’ b₂ r₂.

3) x₁ x₂ r₁ r₂ b ==> b() + x(r₂’(r₁’)).

Ex.1: b r₁ r₂ x₁ x₂. Ex.2: r₁’ r₂’ x₁ b x₂.

4) x₁ x₂ x₃ r b ==> x(r’ * b’).

Example: x₁’ r’ b’ x₂ x₃.

5) x₁ x₂ x₃ x₄ r ==> x₁(x₂’(x₁’ * r’)).

Ex.1: x₁' r' x₂' x₃' x₄' (x₁ solves on his second turn). Ex.2: x₁'' x₂' x₃' x₄' r' (x₂ solves on his second turn.)

6) x₁ x₂ x₃ x₄ x₅ ==> x₂(x₁’(x’(x₁’ * x₂’))).

Example: x1'' x₂' x₃' x₄' x₅', where x₂ can deduce that he is a mix on his second turn after x₁ fails for the second time.

I derive deduction strings for each case based on perspectives that the men in the lineup may have and deduction strings from those perspectives. Take for example case (3). An x in that line up may suppose he is either part of the case (2), or (3). Without any additional data, r may think he is in either (3) or (4). Whereas b in lineup (3) simply knows he is b.

It appears, the longest deduction string here is one where the men made one full round of non-guessing whereafter in the second round the second man in the line up must deduce his stamps. There are several possibilities for that:

x₁'' x₂' x₃' x₄' x₅';

x₁'' x₂' x₃' x₄' r';

r'' x₁' x₂' x₃' b'.

The first round, where 14 stamps were in play, does not seem to offer any useful information for those longest deduction variations above.

Excellent analysis, Prime. I just have 1 minor thing to add

There is 1 more possibility for the distribution that leads to the longest gameplay

r'' x₁' x₂' x₃' x₄'.