Intro: The Interactive Card Problem (Hard)
Inspired by http://www.khanacademy.org/math/brain-teasers/v/alien-abduction-brain-teaser
This is a challenge that will make you think, and can be done and tested with a group of people. All you need is your mind and possibly a group of willing people, cards, and tape.
The objective is to teach problem solving, and practice creating and applying mathematical systems.
Step 1: Materials
You will need-
-a group of preferably more than 5 people
-tape (for taping cards to peoples' backs)
-a room preferably without mirrors and reflective surfaces
-paper and pencil
Step 2: The First Part of the Challenge!
Gather your group of people, and select someone to act as the tester and tell them:
Soon they will be put to a test. Each person will have one playing card taped to their back, and it will either be red or black
(obviously), and there will be no jokers. The distribution will be completely random. No one will be allowed to look at their own card, but they will be able to look at all the other cards on the other peoples' backs. The tester will then ask one person, also at random, "what color is your card." You may only answer "red" OR "black," and you cannot enunciate the word in any way that would convey more information than whether you just said red or black. Then the tester will write down if that person answered correctly or not, and then the person asked will leave the room. The tester will continue to ask this question at random until everyone has been asked once and only once, with each person leaving the room after being asked.
During this test they can NOT communicate with each other in any way shape or form except when asked about the color of their card, which then they can only communicate by saying red or black.
So for the first part they are given a set amount of time where they can communicate knowing what the test is and try to come up with a system, so that as many people as possible guess the color of their card correctly.
Step 3: The Test!
So now we start the test just as described in the first part. Note the point of this test is not to come up with some loophole in the rules, but to make a system that works based on conveying information with only two variables (red or black). These two variables can mean different things based on the system you come up with. For example, "red" can mean that the number of red cards you can see is a prime number, and "black" can mean the number of red cards you see is a composite number. While that system would do little for you, it is a good example of the way you need to be thinking.
Also there are a few things that can be easily deduced:
1- the first guy asked will have a 50/50 chance of answering correctly as he has no information to go on
2- the system has to work on something that has two properties as you can only say one of two things, like in my example prime or composite.
3- since the first guy has a 50/50 chance there is no point in trying to get him to answer correctly, thus he can convey information that instead helps as many other people as possible
If you do not want more hints do NOT go to the next step!
Step 4: Hints
The first hint is that with the proper system all the people can answer correctly, except for the first one asked who will have a 50/50 chance. Also there is a system that can guarantee at least (half minus one) of the people will answer correctly; Which is where the first guy asked says the color that is in the majority, and then every person after says that color.
if you do NOT want to know the solution do NOT go to the next step!
Step 5: The Solution
Now for the solution.
So the first person asked counts the number of let's say red cards. If he/she counts an odd number that person will say red. If the number is even however then he/she will say black. So how does this work?
let us say we have six people (R= a person with a red card) (B= a person with a black card)...
R B R B B R
So we ask a person at random ((X)= person asked)...
R (B) R B B R
He counts an odd number of red cards so he says "red" and gets it wrong, but he had a 50/50 chance anyway. He exits the room, so that leaves...
R R B B R
now we ask again...
(R) R B B R
Now he counts the number of red cards knowing, thanks to the first guy, that there is an odd number of red cards in the room, yet he counts an even number. Thus he knows he is one of the red cards the first guy counted. He says red and gets it right, then leaves the room. Now we have (to save space I will be going ahead and selecting the guy who will get asked next)...
R B (B) R
At this point everyone knows that there is an even number of red cards, because the second guy asked was one of the odd cards the first guy counted (yes I know it can be confusing just bear with me). The next guy getting asked counts an even number of red cards, so he knows his card is black. He gets it right...
R B (R)
The person asked here counts an odd number of red cards. Thus he knows his card is red, because he is one of the even red cards the previous guy counted...
At this point it is important to note that the two people left in the room know that there is one red and one black card still in the room, since there is an odd number of red cards, and there are only two cards. Also since the one being asked sees a black card he knows his is red, and when he says "red" the last person knows his card is black.
If the last two people who were getting asked had the same color card they would both know that there were an even number of cards (because of the people before them), and since there are only two cards they would both know that either both their cards
were red or both were black. Thus if one says black than the other would know he also has a black card.