Wednesday, February 16, 2011
Fairness in Carpooling
A group of n people decide to form a carpool. Each day a subset of these people will arrive to a (fixed) gathering point and one of them should drive. A method for determining which person should drive on any given day is required. The algorithm should be perceived as fair by all members so as to encourage their continued participation. Before discussing the scheduling algorithm, suggest a criterion for fairness
Comparing Information Without Leaking It
Bob comes to Ron, a manager at his company, with a complaint about a sensitive matter; he asks Ron to keep his identity confidential. A few months later, Moshe (another manager) tells Ron that someone has complained to him, also with a confidentiality request, about the same matter.
Ron and Moshe would like to determine whether the same person has complained to each of them, but, if there are two complainers, Ron and Moshe want to give no information to each other about their identities.
The protocol typically used in a situation like this one is akin to the game ``twenty questions,'' but goes by the name of ``delicate conversational probing.'' Ron might ask Moshe if Moshe's complainer is male, and if the answer is ``yes'' Moshe might then ask Ron if Ron's complainer's surname begins with a letter preceding ``M'' in the alphabet. This goes on until Ron and Moshe have ascertained whether they have the same person in mind. When they do not, however (particularly when the first ``no'' occurs late in the game) a great deal of information may have been exchanged.
What can Ron and Moshe do in order not leak more information than necessary?
Ron and Moshe would like to determine whether the same person has complained to each of them, but, if there are two complainers, Ron and Moshe want to give no information to each other about their identities.
The protocol typically used in a situation like this one is akin to the game ``twenty questions,'' but goes by the name of ``delicate conversational probing.'' Ron might ask Moshe if Moshe's complainer is male, and if the answer is ``yes'' Moshe might then ask Ron if Ron's complainer's surname begins with a letter preceding ``M'' in the alphabet. This goes on until Ron and Moshe have ascertained whether they have the same person in mind. When they do not, however (particularly when the first ``no'' occurs late in the game) a great deal of information may have been exchanged.
What can Ron and Moshe do in order not leak more information than necessary?
Nuts & Bolts
A disorganized carpenter has a mixed pile of bolts and nuts and would like to find the corresponding pairs of bolts and nuts. Each nut matches exactly one bolt (and vice versa). By trying to match a bolt and a nut the carpenter can see which one is bigger, but she cannot compare two bolts or two nuts directly. Can you help the carpenter match the nuts and bolts quickly?
The "media power" riddle or the importance of being well-connected
The riddle:
In each node of a simple unweighted n-node graph G there lives a citizen. Tomorrow morning, the citizens of G are about to vote "Yes/No" on a critical and highly controversial proposition whose details I could never really figure out.
Out of curiosity and boredom, each citizen of G spends the afternoon amusing himself by conducting a private poll among his neighbors (including himself), in order to get a sense of the outcome of this all-important election. The alarming and disappointing result found by each "Yes" voter is an astounding 3:1 majority for the "No" voters in his neighborhood.
Should the "Yes" voters be worried?! Should the "No" voters rejoice?! Can all these polls lie?? In short: What can be said with certainty about the minimum guaranteed number of "No" voters in tomorrow's election, given these poll results?
2nd variant:
The result of a 3:1 majority for the "No" voters in the neighborhood, was found by EACH and EVERY voter (not just the "Yes" voting ones).
What can be guaranteed now about the minimum number of "No" voters in the election?
3rd variant:
In order to strengthen the validity of the polls, each citizen performs his poll among all citizens in distance up to 4 from himself. Alas, the poll results remain the same.
What can be deduced now, in both previous cases?
In each node of a simple unweighted n-node graph G there lives a citizen. Tomorrow morning, the citizens of G are about to vote "Yes/No" on a critical and highly controversial proposition whose details I could never really figure out.
Out of curiosity and boredom, each citizen of G spends the afternoon amusing himself by conducting a private poll among his neighbors (including himself), in order to get a sense of the outcome of this all-important election. The alarming and disappointing result found by each "Yes" voter is an astounding 3:1 majority for the "No" voters in his neighborhood.
Should the "Yes" voters be worried?! Should the "No" voters rejoice?! Can all these polls lie?? In short: What can be said with certainty about the minimum guaranteed number of "No" voters in tomorrow's election, given these poll results?
2nd variant:
The result of a 3:1 majority for the "No" voters in the neighborhood, was found by EACH and EVERY voter (not just the "Yes" voting ones).
What can be guaranteed now about the minimum number of "No" voters in the election?
3rd variant:
In order to strengthen the validity of the polls, each citizen performs his poll among all citizens in distance up to 4 from himself. Alas, the poll results remain the same.
What can be deduced now, in both previous cases?
Applied Kid Cryptography
``Where's Waldo?'' is a puzzle book where each page contains a very detailed picture with many different characters (click here for ``Where's Waldo?'' on the WEB). The goal is to find Waldo, a predefined character . As the following true story will reveal, in these pictures also lies an interesting cryptographic problem.
Our story involves two characters; for the sake of anonymity and following a long cryptographic tradition we shall call them Alice and Bob. One day, while Alice and Bob were playing ``Where's Waldo?'', Alice suddenly claimed: ``I know where Waldo is!''. Bob responded with a baffling riddle: ``Alice, do you know what a liar is?''. Worried about her reputation (both as an honest person and as a qualified cryptographer), Alice wondered: ``How can I prove to Bob that I know where Waldo is without revealing his location?''
Can you help Alice and propose a simple solution that does not require complex computation and is low-tech in terms of the required resources?
Our story involves two characters; for the sake of anonymity and following a long cryptographic tradition we shall call them Alice and Bob. One day, while Alice and Bob were playing ``Where's Waldo?'', Alice suddenly claimed: ``I know where Waldo is!''. Bob responded with a baffling riddle: ``Alice, do you know what a liar is?''. Worried about her reputation (both as an honest person and as a qualified cryptographer), Alice wondered: ``How can I prove to Bob that I know where Waldo is without revealing his location?''
Can you help Alice and propose a simple solution that does not require complex computation and is low-tech in terms of the required resources?
Amazing telepathetic Tachman Family.
The Amazing Tachman Family are world famous for their astonishing feats involving telepathy. They have performed in front of large crowds. But can they exhibit their skills in the carefully controlled environment of the laboratories of FEXI (the Foolproof Experiments Institute )? Mr. Tachman agreed that his three children will participate in a scientific experiment on telepathy. However, he imposed the condition that any experiment that they take part in should only prove that telepathy exists, without revealing which of the three children is the one who has telepathic skills (this was considered a professional secret).
The chief mathematician in FEXI proposed the following experiment. It is performed with a deck of six cards. One card has the symbol X on it, two cards have the symbol Y , and three cards have the symbol Z . The three children are placed in different rooms. Each child is given one of the cards with the symbol Z on it. The other three cards are shuffled and then each child gets one of them (face down). Each child inspects this second card that he receives, and can either return it, or return the Z card (face down). The three cards that are returned are shuffled, and then inspected. If they contain all three symbols, X , Y , and Z , then the children win. Otherwise, they fail.
The mathematician argued that if the children have no telepathic skills, they win with probability at most 2/3 . A child that receives X must return X (otherwise, no X is returned). A child that receives Y has two possible strategies: either to return Y or to return Z . Since each child must base his decision of which card to return only on the card that he receives (he sees no other card), then he must associate himself with exactly one of the two strategies. Since there are three children and only two possible strategies, at least two children share the same strategy. With probability 1/3, both these children will receive a Y card. If this event happens, they both return the same type of card, causing failure.
The mathematician also argued that if at least one child is telepathic, the children need never fail. The telepathic child need not base his strategy only on the card that it sees, but can base it also on the cards that the other children see and return. Using this information, and assuming that each of the other children employs a different strategy, it is always possible to ensure that three different symbols will be returned (by a simple case analysis). Moreover, since the cards are shuffled both before they are dealt, and after they are returned, symmetry arguments show that there is no way of telling who the telepathic child is.
Mr. Tachman praised the mathematician on the wise design, and agreed that his family take part in the experiment. The staff at FEXI was concerned that even without telepathy, the children have probability greater than 1/2 of success. However, the mathematician assured them that the experiment can be repeated in order to build up the confidence in the results. Even if the children succeed in the first experiment, there still is probability 1/3 of failing in the next experiment. If the experiment is repeated 100 times, then the probability of success in all experiments is at most (2/3)^{100} , which is astronomically small. The mathematician was willing to stake his job on his conviction that an event of such low probability will not happen.
For the experiment, FEXI employees prepared hundreds of decks, each containing six cards, as instructed by the mathematician. With the first two deck of cards, the children won, and Mr. Tachman was very pleased. On the third deck, they failed, but Mr. Tachman said that this is due to excitement and pressure. After ten decks were played the children won seven times, and failed on three. Mr. Tachman commented that the children are doing very well. The mathematician disagreed, and said that seven out of ten for this experiment is what one would expect to get by chance. Mr. Tachman said that not being a mathematician, he is unable to comment on the mathematics of the experiment. However, knowing the pressure his children are under, 30%-40% failure rate is to be expected. The experiments were stopped. The mathematician said that under current circumstances, a new experiment needs to be designed. This might take a few days. Mr. Tachman got angry, and said that FEXI are sore loosers, and that he only agreed to come for one day. The head of the lab anxiously called everyone to calm down.
After a few minutes, Mr. Tachman proposed the following modified experiment. Instead of using one deck of cards as was done in each execution of the original experiment, use three: a red deck, a blue deck, and a yellow deck. The original experiment will be executed three times in parallel. As in the original experiment, each child receives a red Z card. The other three red cards are shuffled, and each child gets one more red card at random. Then the same procedure is repeated with the blue deck and the yellow deck. Each child can inspect the six cards that it receives, and return one card of each color. The three cards of each color that are returned will be shuffled and inspected. If there are X , Y and Z cards of every color, the children win. Otherwise, they loose. Mr. Tachman explained that in the extended experiment, the children must win with the red deck, and also with the blue deck, and also with the yellow deck. Since each deck is shuffled independently, then the probability of winning simultaneously with all three decks is at most (2/3)^3 < 0.3 , if no telepathy is involved. He was sure that his children would do much better then that.
The first time the extended experiment was executed, the children won with the red deck, but failed with the blue deck and with the yellow deck. Hence the children failed in the extended experiment. Mr. Tachman was annoyed. The second time the extended experiment was executed, the children won with the red deck and with the yellow deck, but failed with the blue deck. Hence despite the improvement, the children still failed in the extended experiment. Mr. Tachman was furious. He said that his children obviously do not understand what they need to do, and called out a five minute break. In this break he gathered up the children, and gave them instructions (in Hebrew). The children returned to their rooms. The next time the extended experiment was executed, the children failed with all three decks. The mathematician asked Mr. Tachman if he wants another break, but Mr. Tachman expressed complete confidence in his children. And for good reasons. The extended experiment was repeated a hundred times. To everyone's amazement (except for Mr. Tachman), the children won 65 times. The mathematician calculated that the probability of having 65 successes out of a hundred, when the probability of an individual success is 0.3, is bellow one in a million. The Tachman family were the clear winners of the day.
A report on this experiment was prepared by the lab. However, the report was never published, and the mathematician was fired. Can you see why?
Any relation between the first name of the author and the first name of Uri Geller is a coincidence.
The chief mathematician in FEXI proposed the following experiment. It is performed with a deck of six cards. One card has the symbol X on it, two cards have the symbol Y , and three cards have the symbol Z . The three children are placed in different rooms. Each child is given one of the cards with the symbol Z on it. The other three cards are shuffled and then each child gets one of them (face down). Each child inspects this second card that he receives, and can either return it, or return the Z card (face down). The three cards that are returned are shuffled, and then inspected. If they contain all three symbols, X , Y , and Z , then the children win. Otherwise, they fail.
The mathematician argued that if the children have no telepathic skills, they win with probability at most 2/3 . A child that receives X must return X (otherwise, no X is returned). A child that receives Y has two possible strategies: either to return Y or to return Z . Since each child must base his decision of which card to return only on the card that he receives (he sees no other card), then he must associate himself with exactly one of the two strategies. Since there are three children and only two possible strategies, at least two children share the same strategy. With probability 1/3, both these children will receive a Y card. If this event happens, they both return the same type of card, causing failure.
The mathematician also argued that if at least one child is telepathic, the children need never fail. The telepathic child need not base his strategy only on the card that it sees, but can base it also on the cards that the other children see and return. Using this information, and assuming that each of the other children employs a different strategy, it is always possible to ensure that three different symbols will be returned (by a simple case analysis). Moreover, since the cards are shuffled both before they are dealt, and after they are returned, symmetry arguments show that there is no way of telling who the telepathic child is.
Mr. Tachman praised the mathematician on the wise design, and agreed that his family take part in the experiment. The staff at FEXI was concerned that even without telepathy, the children have probability greater than 1/2 of success. However, the mathematician assured them that the experiment can be repeated in order to build up the confidence in the results. Even if the children succeed in the first experiment, there still is probability 1/3 of failing in the next experiment. If the experiment is repeated 100 times, then the probability of success in all experiments is at most (2/3)^{100} , which is astronomically small. The mathematician was willing to stake his job on his conviction that an event of such low probability will not happen.
For the experiment, FEXI employees prepared hundreds of decks, each containing six cards, as instructed by the mathematician. With the first two deck of cards, the children won, and Mr. Tachman was very pleased. On the third deck, they failed, but Mr. Tachman said that this is due to excitement and pressure. After ten decks were played the children won seven times, and failed on three. Mr. Tachman commented that the children are doing very well. The mathematician disagreed, and said that seven out of ten for this experiment is what one would expect to get by chance. Mr. Tachman said that not being a mathematician, he is unable to comment on the mathematics of the experiment. However, knowing the pressure his children are under, 30%-40% failure rate is to be expected. The experiments were stopped. The mathematician said that under current circumstances, a new experiment needs to be designed. This might take a few days. Mr. Tachman got angry, and said that FEXI are sore loosers, and that he only agreed to come for one day. The head of the lab anxiously called everyone to calm down.
After a few minutes, Mr. Tachman proposed the following modified experiment. Instead of using one deck of cards as was done in each execution of the original experiment, use three: a red deck, a blue deck, and a yellow deck. The original experiment will be executed three times in parallel. As in the original experiment, each child receives a red Z card. The other three red cards are shuffled, and each child gets one more red card at random. Then the same procedure is repeated with the blue deck and the yellow deck. Each child can inspect the six cards that it receives, and return one card of each color. The three cards of each color that are returned will be shuffled and inspected. If there are X , Y and Z cards of every color, the children win. Otherwise, they loose. Mr. Tachman explained that in the extended experiment, the children must win with the red deck, and also with the blue deck, and also with the yellow deck. Since each deck is shuffled independently, then the probability of winning simultaneously with all three decks is at most (2/3)^3 < 0.3 , if no telepathy is involved. He was sure that his children would do much better then that.
The first time the extended experiment was executed, the children won with the red deck, but failed with the blue deck and with the yellow deck. Hence the children failed in the extended experiment. Mr. Tachman was annoyed. The second time the extended experiment was executed, the children won with the red deck and with the yellow deck, but failed with the blue deck. Hence despite the improvement, the children still failed in the extended experiment. Mr. Tachman was furious. He said that his children obviously do not understand what they need to do, and called out a five minute break. In this break he gathered up the children, and gave them instructions (in Hebrew). The children returned to their rooms. The next time the extended experiment was executed, the children failed with all three decks. The mathematician asked Mr. Tachman if he wants another break, but Mr. Tachman expressed complete confidence in his children. And for good reasons. The extended experiment was repeated a hundred times. To everyone's amazement (except for Mr. Tachman), the children won 65 times. The mathematician calculated that the probability of having 65 successes out of a hundred, when the probability of an individual success is 0.3, is bellow one in a million. The Tachman family were the clear winners of the day.
A report on this experiment was prepared by the lab. However, the report was never published, and the mathematician was fired. Can you see why?
Any relation between the first name of the author and the first name of Uri Geller is a coincidence.
The Circular Lake
A swan sits at the center of a perfectly circular lake. At an edge of the lake stands a ravenous monster waiting to devour the swan. The monster can not enter the water, but it will run around the circumference of the lake to try to catch the swan as soon as it reaches the shore. The monster moves at 4 times the speed of the swan, and it will always move in the direction along the shore that brings it closer to the swan the quickest. Both the swan and the the monster can change directions in an instant.
The swan knows that if it can reach the lake's shore without the monster right on top of it, it can instantly escape into the surrounding forest.
How can the swan succesfully escape?
Subscribe to:
Posts (Atom)