Sunday, June 22, 2008

Unbiased Coin Puzzle

Unbiased coin puzzle
A little variation to the Biased coin puzzle.

You and your rival are competing for the same girl, and decide to settle it with a coin toss. Your rival has known the girl longer than you have, so you agree that it is fair for him to have a chance of winning equal to P, where P > 0.5. However, you only have a fair coin.

How can you conduct this contest such that the biased probability is manifested? What is the average number of coin flips needed to determine a winner?

Saturday, June 7, 2008

Solution to Find the Culprit Managers Puzzle

Solution to "Find the Culprit Managers Puzzle". Before the solution .. give it a try at Find the Culprit Managers Puzzle

There could be two possible scenarios

Here's an n-1 query solution to part 1. Maintain three sets of people: UNSEEN, STACK, and DISCARD. Initialize the process by picking one arbitrarily to be the STACK, everything else is UNSEEN. Repeat the following step until UNSEEN is empty:

Pick an UNSEEN element x, remove it from UNSEEN. Ask the top of the STACK y about x. If y says "manager" pop y off the stack and DISCARD both x and y. If it says "engineer" add x to the top of the STACK.

After all elements have been processed in this way (n-1 comparisons), the top of the stack must be an engineer.

Why does this work? First observe that whenever we discard a pair, at least one of them is a manager. So among the rest of them (STACK and UNSEEN) a majority must still be engineers. So at the end, when UNSEEN is empty, there must be an engineer in the stack, therefore the top of the stack must be an engineer.

This can be improved to n-2 simply by stopping one earlier. When there's one UNSEEN left, if the stack is empty, that UNSEEN one is an engineer. Otherwise, the top of the stack must be an engineer.

If is n is even and n>=4, as a first step we can just throw out one person, and appy this algorithm to the remaining n-1 obtaining n-3 comparisons. This gives the optimal algorithm.

2: If half or more of the people are managers, then the problem cannot be solved. The managers can ensure this simply by always lying. Now there's way to separate the two sets of people. Each one simply claims the others are Managers.


Subscribe via email

Enter your email address:

Delivered by FeedBurner