16 replies to this topic

[bushindo]

 

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

 

Spoiler for first question

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.

Spoiler for half of the solution

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.

Spoiler for half of the solution

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.

 

Spoiler for OOPS

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.

Spoiler for not that long

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.[/size]

Spoiler for not that long

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.

[/size]

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

Spoiler for

There is 1 more possibility for the distribution that leads to the longest gameplay
r'' x₁' x₂' x₃' x₄'.