Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I A new puzzle based on the "Blue-eye paradox"

  1. Aug 16, 2016 #1
    The puzzle presented below is derived as a variation of the Blue-eye paradox" which has been discussed in the following thread.
    THE PUZZLE

    Teams of N people each are each given the following challenge. The rules for the challenge contest are shown indented below, and they are presented to each team member before the contest begins.
    Each person, in a private room, is blindfolded and is assisted in putting on a pullover shirt which has a four inch diameter dot on the back between the shoulder blades. Randomly, for each team, W of the members wil have white dots and B of the members have black dots.​

    N = W + B. Also, W > 1 and B > 1. The value of W is chosen randomly for each contest, and it is the same for each team, but the value is not revealed to the teams.​

    The blindfolds are removed, and all of the team members go into a large common room. Each team member can see the colors of the dots on the back of all the others, but not her/his own dot. There is no way a peson can see his/her own dot. No one is permitted to communicate in any way about the color of any other person's dot to anyone. Any such communication will disqualify the team.​

    After a few minutes, sufficient time for every one to get a look at everyone else's dot, one team member is randomly selected to make one helpful public announcement. After the announcement is made, each person returns to her/his private room.​

    * If a person comes to know the color of her/his own dot s/he is to pick up a black or a white card corresponding to her/his now known dot. Then everyone returns to the large room. If anyone displays a card with the wrong color, the team is disqualified. After a time sufficient for every team member to again see the dot for every other member, and to see all the cards (if any), the members again return to the private rooms.​

    The process described in the * paragraph above is repeated until everyone displays a color card. (Note that if any team member who is unable to deduce the color of her/his dot, after a time which that member feels is enough, s/he may intentionally tell some other person the color of the dot which in on that other person's back. This will immediately terminate the team's further participation in the contest.)​

    The challenge is for each team to to have all of its members holding a card with the correct color as quickly as they can, that is with the fewest iterations of paragraph * above. The teams win prizes depending on the time it take for every member of the team to display a correct color card. The fastest team wins the largest prize.
    Assume that you are a member of a team, and you are selected to make the one public announcement. What is your announcement?

    SUGGESTION
    To avoid spoilers for some who are thinking about this puzzle, those with a solution they would like to post should postpone doing so for a few days. After a few days I will post my solution, and then others can do so if they like. I would be very interested to see the variety of solutions that people might post.
     
  2. jcsd
  3. Aug 17, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    How many teams are there? The strategy I would choose depends on that.

    > If a person comes to know the color of her/his own dot s/he is to pick up a black or a white card corresponding to her/his now known dot.
    Do they have to do that at the earliest possible time? Does the team get disqualified if they don't do that?

    Can the "one helpful public announcement" as long as we want?

    I suggest to allow answers, but only in spoiler tags:
    like this
     
  4. Aug 17, 2016 #3
    Hi mfb:

    Thank you for your post.

    I confess I find this surprising. I would be curious to see how the number of teams, say T, would affect your strategy. I suggest you choose two values for T which would demonstrate this difference in strategies.

    I again confess these questions are surprising. I see no reason why the monitors of the contest would care about someone having deduced her/his dot color postponing choosing a card to display. I also don't see any way that they could enforce a requirement against such a postponement since the monitors have no way of knowing when a person knows her/his dot color other than the choosing of a card. You may assume there is no rule against postponement, and I am looking forward to seeing how this might possibly affect strategy.

    I had thought about setting some arbitrary adequate word limit of the announcement length, but I decided not to do that. What limit would you suggest?

    I like your suggestion about the spoiler tag. I do not know how to insert a spoiler tag, so I suggest you might post the method for doing this.

    Regards,
    Buzz
     
    Last edited: Aug 17, 2016
  5. Aug 17, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You should have seen the spoiler tag in the post you quoted. Anyway:
    [spoiler]text[/spoiler] ->
    text
    [spoiler=Other text]text[/spoiler] ->
    text

    And here my thoughts about the problem (slightly modified after a rule clarification):
    Let's call the person making the announcement A. A says: "Excluding my dot, the number of white dots in this group is [even/odd]". Everyone knows the colors of everyone in this group apart from their own, so having the even/odd information allows to figure out the own color.


    Strategy 1: Everyone returns to their room, all apart from A can pick the right card, A randomly picks a card. 50% chance to win in the first round, 50% chance to lose completely. This is the best strategy if there is a large number of teams - because some of the teams will choose this strategy and chances are good one will be lucky, so finishing in the second round doesn't help you at all.


    Strategy 2: A also selects a person B with the following special order: "If my color is white then pick your card in the first round, otherwise pick it in the second round". After the first round A checks if B picked their card, afterwards A knows their shirt color and in the second round everyone picked their card correctly. This strategy can be advisable if there are just two teams. If the other teams goes for strategy 1 it does not matter (50% probability for both teams), if the other team also goes for strategy 2 both teams finish at the same time, but if the other team doesn't find those strategies you can be faster and you don't have to risk anything.
    Here everyone knows that B knows their color even for the first round, but B might choose not to pick a card - to help A.
     
    Last edited: Aug 18, 2016
  6. Aug 17, 2016 #5

    disregardthat

    User Avatar
    Science Advisor

    As I see it, postponing showing your card is a possible way to convey more information to the other participants.

    Also, if T is very large, then it's possible that the best strategy is to attempt showing cards when you're not certain of your color. E.g., if a strategy exists in which you have a 50% chance of guessing everything right is significantly shorter than a strategy that gives a 100% chance of guessing everything right, then you might do some probability theory and come to the conclusion that your best chance at winning is taking a risk. Although, you don't know the strategies of other teams. So it may by that every other team are also taking such risks. In which case you would have a better chance by taking even bigger risks. However, this is all perhaps irrelevant, depending on the solution.

    I'm really confused though. What kind of announcement are the participant allowed to make? Is it allowed to say outright who has what color?
     
  7. Aug 17, 2016 #6
    Hi disregardthat:

    My intention is to only restrict the announcer from saying what s/he has seen to be the dot color of any specific person.
    Regards,
    Buzz
     
  8. Aug 17, 2016 #7
    Hi mfb:

    Thanks for the method of posting a Spoiler tag.

    I am not clear about the intended meaning of the first sentence in your spoiler. It seems to violate the rule I quoted in my post #6, but perhaps you had a different interpretation.

    Also, your Strategy 2 has person A tell person B what person A sees as person B's dot color. This definitely violates the quoted rule.

    Regards,
    Buzz
     
  9. Aug 17, 2016 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Well, the announcement is communication, so I thought the "no communication" restriction was not applicable to that. If you take it literally, you cannot make any announcement because that is always communication.
    Anyway, here is a slightly modified announcement that does the same job but without explicitly saying a color of a person:
    A says: "Excluding my dot, the number of white dots in this group is [even/odd]". Everyone knows the colors of everyone in this group apart from their own, so having the even/odd information allows to figure out the own color.
     
  10. Aug 17, 2016 #9
    Hi mfb:

    I much appreciate your insights into this puzzle. You have pointed out some aspects that I had overlooked. Consequently, I will post some additional information that is given to all team members of all teams at the beginning of a contest.

    Regards,
    Buzz
     
    Last edited: Aug 17, 2016
  11. Aug 17, 2016 #10
    Hi everyone:

    Below is the text of some additional information given to all team members of all teams at the beginning of a contest.
    1. If there is a tie among teams for any ranking, the prize for that ranking is NOT divided, but rather all the tied teams will get the same specified prize for that rank.
    2. The prize for rank 1 (having the fewest repetitions of the * paragraph actions) is R1 (a specific number of currency units.)
    3. The prize for rank 2 is: R2 = (2/3) × R1.
    4. The prize for rank 3 is: R3 = (1/3) × R2.
    There are no other prizes.​

    Regards,
    Buzz
     
  12. Aug 17, 2016 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Well, there is no strategy that can beat the two I posted, so the prize distribution just means we have to find the Nash equilibrium between the two.

    Interestingly, if everyone simply wants to optimize their own prize, everyone will play strategy 2, and all teams will share the prize for the first rank.
     
  13. Aug 17, 2016 #12
    Hi mfb:

    I feel I should remind you that your strategy 2 as presented in your Spoiler text has the flaw of violating the rule about not telling anyone about a specific dot color.

    Regards,
    Buzz
     
  14. Aug 17, 2016 #13

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The person does not tell anyone about a specific dot color with the modification in post #8.
     
  15. Aug 17, 2016 #14
    Hi mfb:

    I saw the correction you made in post #8 and also to the text in the Spoiler in post #4. That correction is fine. The "flaw I am referring to is in the text of Strategy 2. I quote the bad text in the Spoiler below.
    Strategy 2: A also selects a person B with the following special order: "Your color is [whatever it is].

    Am I mistaken about this?

    Regards,
    Buzz
     
  16. Aug 18, 2016 #15

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    This is not necessary, as the person can infer their color from the previous statement already. I edited the post to take that additional rule into account.
    See it in the context of the timeline: when I made that post I assumed that the announcement can be anything.
     
  17. Aug 18, 2016 #16
    Hi mfb:

    The Spoiler below contains a quote from your revised Strategy 2.
    A also selects a person B with the following special order: "If my color is white then pick your card in the first round, otherwise pick it in the second round"
    I understand that others may consider my comment to be a nit, but I interpret the quote to mean that B is communicating (non-verbally) A's color to A, and this violates the rule against such communication.

    Regards,
    Buzz
     
  18. Aug 18, 2016 #17

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I explicitly asked if team members can choose not to pick their card. And your first post tells us that seeing if someone picked a card is allowed:
    Where is the point in seeing the cards if we are not allowed to gain information from it?

    The announcement of A cannot depend on the color of A. If we are not allowed to have the actions of any person depending on the color of A (and taking the correct card, or not taking a card, are the only useful actions), then A can never know their own color.
     
  19. Aug 18, 2016 #18
    Hi mjb:

    I have a different solution in mind. It may well be that when I post it in a few days, you will interpret my method of also violating the same rule I suggested that your method violated. However, I interpret there to be a distinct difference. I will say more about this when I post my solution.

    Regards,
    Buzz
     
  20. Aug 20, 2016 #19
    The following is my solution.

    THE ANNOUNCEMENT
    The following are the 6 steps I have worked out for all of us to follow so our team can easily win the rank 1 prize.

    Step 1. I want everyone to line up in rows. When I have completed this announcement, I will join the last row at the end.

    Step 2. Staring in the first row, group yourselves by threes from left to right. When you reach the end of the row 1, continue making groups of three by continuing the grouping into row 2 from right to left. Then continue the grouping process into row 3 from left to right. Continue the process as described from row to row until reaching the end of the last row. There is no need to consider dot colors during this grouping.

    Step 3. When you reach the end of the last row, there are three possibilities:
    a. The grouping comes out even, with no one left over.
    b. After the grouping into threes, there is one person left over.
    c. After the grouping into threes, there are two persons left over.​
    If there are one or two persons left over, each will choose one of the nearby groups of three and join that group, making it a group of four. At this point there will be a number of groups of three, and possibly one or two groups of four. The groups should separate a bit from each other so each group can perform the following steps independently.

    Step 4. Within each group, each person will look at the dots of the others in the group. If a person sees a combination of both white and black dots among the other persons in the group, the person should raise his hand.

    Step 5. From seeing the other dots in the group and the raised hands, each person should be able to easily deduce the color of her/his own dot.

    Step 6. After deducing the color of one's own dot, the person should retire to her/his private room to collect the corresponding card. When everyone returns with their card to the common room, our team will have successfully completed the challenge in just a single execution of the * paragraph.​
    That completes my announcement.

    I omitted details for Step 5 because I assume that they would not be necessary. I described each of the various possibilities for the situations to be resolved in Step 5 to my 11 year old grandson, and he was able to figure out the correct dot color for all of them.

    Comments would be much appreciated.
     
  21. Aug 20, 2016 #20

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I think you violate your rules.
    How is that not communication? Raising the hand clearly depends on the dots of others, and gives others information. If that is allowed, why don't you make groups of 2, and tell everyone to raise the hand if the other person has a white dot?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: A new puzzle based on the "Blue-eye paradox"
  1. Probability Puzzle (Replies: 2)

  2. Puzzle statements (Replies: 5)

  3. Probability puzzle (Replies: 27)

  4. Hat puzzle (Replies: 4)

  5. Blue-eye paradox (Replies: 275)

Loading...