The Stark Raving Mad King

August 31, 2007 | Leave a Comment

A stark raving mad king tells his 100 wisest men he is about to line them up and that he will place either a red or blue hat on each of their heads. Once lined up, they must not communicate amongst themselves. Nor may they attempt to look behind them or remove their own hat.

The king tells the wise men that they will be able to see all the hats in front of them. They will not be able to see the color of their own hat or the hats behind them, although they will be able to hear the answers from all those behind them.

The king will then start with the wise man in the back and ask “what color is your hat?” The wise man will only be allowed to answer “red” or “blue,” nothing more. If the answer is incorrect then the wise man will be silently killed. If the answer is correct then the wise man may live but must remain absolutely silent.

The king will then move on to the next wise man and repeat the question.

The king makes it clear that if anyone breaks the rules then all the wise men will die, then allows the wise men to consult before lining them up. The king listens in while the wise men consult each other to make sure they don’t devise a plan to cheat. To communicate anything more than their guess of red or blue by coughing or shuffling would be breaking the rules.

What is the maximum number of men they can be guaranteed to save?

A stark raving mad king tells his 100 wisest men he is about to line them up and that he will place either a red or blue hat on each of their heads. Once lined up, they must not communicate amongst themselves. Nor may they attempt to look behind them or remove their own hat.

The king tells the wise men that they will be able to see all the hats in front of them. They will not be able to see the color of their own hat or the hats behind them, although they will be able to hear the answers from all those behind them.

The king will then start with the wise man in the back and ask “what color is your hat?” The wise man will only be allowed to answer “red” or “blue,” nothing more. If the answer is incorrect then the wise man will be silently killed. If the answer is correct then the wise man may live but must remain absolutely silent.

The king will then move on to the next wise man and repeat the question.

The king makes it clear that if anyone breaks the rules then all the wise men will die, then allows the wise men to consult before lining them up. The king listens in while the wise men consult each other to make sure they don’t devise a plan to cheat. To communicate anything more than their guess of red or blue by coughing or shuffling would be breaking the rules.

What is the maximum number of men they can be guaranteed to save?

 

Answer: 99.

You can save about 50% by having everyone guess randomly.

You can save 50% or more if every even person agrees to call out the color of the hat in front of them. That way the person in front knows what color their hat is, and if the person behind also has the same colored hat then both will survive.

So how can 99 people be saved? The first wise man counts all the red hats he can see (Q) and then answers “blue” if the number is odd or “red” if the number is even. Each subsequent wise man keeps track of the number of red hats known to have been saved from behind (X), and counts the number of red hats in front (Y).

If Q was even, and if X&Y are either both even or are both odd, then the wise man would answer blue. Otherwise the wise man would answer red.

If Q was odd, and if X&Y are either both even or are both odd, then the wise man would answer red. Otherwise the wise man would answer blue.

There can be any number of red hats, as the following examples show…

Prisoner Hat he wears Number of red hats he sees (Y) Red hats saved for sure (X) He says
1 red 6 even (Q)  

N/A

 red
2 blue 6 even 0 even blue
3 red 5 odd 0 even red
4 blue 5 odd 1 odd blue
5 blue 5 odd 1 odd blue
6 red 4 even 1 odd red
7 red 3 odd 2 even red
8 red 2 even 3 odd red
9 red 1 odd 4 even red
10 red 0 even 5 odd red

Another example might also help, as this puzzle seems to trip up most people…

Prisoner Hat he wears Number of red hats he sees (Y) Red hats saved for sure (X) He says
1 blue 5 odd (Q)   N/A blue
2 blue 5 odd 0 even blue
3 red 4 even 0 even red
4 blue 4 even 1 odd blue
5 blue 4 even 1 odd blue
6 red 3 odd 1 odd red
7 blue 3 odd 2 even blue
8 red 2 even 2 even red
9 red 1 odd 3 odd red
10 red 0 even 3 odd red

Posted by | Filed Under Algorithms 

The emperor

August 31, 2007 | Leave a Comment

You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You’ve got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.

The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.

You have thousands of prisoners at your disposal and just under 24 hours to determine which single bottle is poisoned.

What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?

 

Answer: 10 prisoners must sample the wine. Bonus points if you worked out a way to ensure than no more than 8 prisoners die.

Number all bottles using binary digits. Assign each prisoner to one of the binary flags. Prisoners must take a sip from each bottle where their binary flag is set.

Here is how you would find one poisoned bottle out of eight total bottles of wine.

  Bottle 1 Bottle 2 Bottle 3 Bottle 4 Bottle 5 Bottle 6 Bottle 7 Bottle 8
Prisoner A   X   X   X   X
Prisoner B     X X     X X
Prisoner C         X X X X

In the above example, if all prisoners die, bottle 8 is bad. If none die, bottle 1 is bad. If A & B dies, bottle 4 is bad.

With ten people there are 1024 unique combinations so you could test up to 1024 bottles of wine.

Each of the ten prisoners will take a small sip from about 500 bottles. Each sip should take no longer than 30 seconds and should be a very small amount. Small sips not only leave more wine for guests. Small sips also avoid death by alcohol poisoning. As long as each prisoner is administered about a millilitre from each bottle, they will only consume the equivalent of about one bottle of wine each.

Each prisoner will have at least a fifty percent chance of living. There is only one binary combination where all prisoners must sip from the wine. If there are ten prisoners then there are ten more combinations where all but one prisoner must sip from the wine. By avoiding these two types of combinations you can ensure no more than 8 prisoners die.

One viewer felt that this solution was in flagrant contempt of restaurant etiquette. The emperor paid for this wine, so there should be no need to prove to the guests that wine is the same as the label. However, this medieval wine will taste more like vinegar than it ever did, as it has been breathing for up to a day.

Posted by | Filed Under Algorithms 

The most intelligent prince

August 31, 2007 | 1 Comment

The king wants his daughter to marry the smartest of 3 extremely intelligent young princes, and so the king’s wise men devised an intelligence test.

The princes are gathered into a room and seated, facing one another, and are shown 2 black hats and 3 white hats. They are blindfolded, and 1 hat is placed on each of their heads, with the remaining hats hidden in a different room.

The king tells them that the first prince to correctly identify the color of his hat will marry his daughter. A wrong guess will mean death. The blindfolds are then removed.

You are one of the princes. You see 2 white hats on the other prince’s heads. After some time you realize that the other prince’s are unable to deduce the color of their hat, or are unwilling to guess. What color is your hat?

Note: You know that your competitors are very intelligent and want nothing more than to marry the princess. You also know that the king is a man of his word, and he has said that the test is a fair test of intelligence and bravery.

Posted by | Filed Under Algorithms 

Shrink specific databases

August 31, 2007 | Leave a Comment

USE master

GO

DECLARE DB_CURSOR CURSOR FOR

SELECT [NAME] FROM sysdatabases

   WHERE [name] like ‘ULTIPRO%’

OR [name] like ‘HRMS%’

ORDER BY [name]

OPEN DB_CURSOR

DECLARE @STATEMENT VARCHAR(1024)

DECLARE @DB VARCHAR(56)

FETCH NEXT FROM DB_CURSOR INTO @DB

WHILE @@FETCH_STATUS = 0

BEGIN

   PRINT @DB

   DBCC SHRINKDATABASE (@DB)

   FETCH NEXT FROM DB_CURSOR INTO @DB

END

 

CLOSE DB_CURSOR

DEALLOCATE DB_CURSOR

 

 

 

 

Posted by | Filed Under SQL 

Next Page »