Navigation Links

Responsive Topnav Example

Resize the browser window to see how it works.

Tuesday, April 19, 2016

8 Balls Puzzle


Problem:-

You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weighing, how do you find the defective one?

Solution:

Defective ball is light

Make three Groups G1 – 3 balls G2 – 3 balls G3 – 2 balls

First weight- G1 and G2 if G1 = G2 then defective ball in G3 ,
weigh the the 2 balls in G3 if EQUAL then 3rd ball of G3 is defective
else whichever lighter in 1st or 2nd is defective ball

else if G1 < G2 defective ball in G1
weigh 1 and 2 ball of G1 if EQUAL then 3rd ball of G1 is defective
else whichever lighter in 1st or 2nd is defective ball

else if G1 > G2 defective in G2
Again in 1 comparison we can find the odd ball.

So by following above steps in 2 steps, lighter ball can be find out.

The Fox and The Duck Puzzle

Problem:-

A number of different versions of the puzzle are available. For this post we are using the Fox and the Duck version. A duck, pursued by a fox, escapes to the center of a perfectly circular pond. The fox cannot swim, and the duck cannot take flight from the water. The fox is four times faster than the duck. Assuming the fox and duck pursue optimum strategies, is it possible for the duck to reach the edge of the pond and fly away without being eaten? If so, how?

Solution:
This is not a simple mathematical puzzle to solve like normal common problems. Fox in this puzzle is too fast and clever for any normal and simple strategy.

From the speed of the fox it is obvious that duck cannot simply swim to the opposite side of the fox to escape. Pi*R/4 < R.

Let V be the speed of Duck and 4V speed of fox.

Now we need to find out the position from where duck can swim to the shore in time less then Pi*R/4V. Pi = 3.14.

To keep things simple we will take the distance from center for the duck to escape when the fox is on the exact opposite side of the pond to be R/4.
So duck can swim in 3R/4V which is less than Pi*R/4V.

Now the next challenge is how we can make sure the clever fox will be on the opposite side. Here is the tricky part.

Let the duck rotate around the pond in a circle of radius R/4. Now fox and duck will take exact same time to make a full circle. Now reduce the radius the duck is circling by a very small amount (Delta). Now the Fox will lag behind, he cannot stay at a position as well. Now in due time duck will get to a position we wanted, 3/4*R distance away from shore where fox is on the exact opposite side of the pond. From there duck can swim safely to shore and fly away.


Monday, April 18, 2016

Red and Blue Marbles

Problem:
You have two jars, 50 red marbles and 50 blue marbles. You need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. When picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar. You can arrange the marbles however you like, but each marble must be in a jar.

Answer:
Say we put all the red marbles into JAR A and all the blue ones into JAR B. then our chances for picking a red one are:

1/2 chance we pick JAR A * 50/50 chance we pick a red marble
1/2 chance we pick JAR B * 0/50 chance we pick a red marble

You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%.

What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice). Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).

So the maximum probability will be :
jar A : (1/2)*1 = 1/2 (selecting the jar A = 1/2, red marble from jar A = 1/1)
jar B : (1/2)*(49/99) = 0 (selecting the jar B = 1/2, red marble from jar B = 49/99)
Total probability = 74/99 (~3/4)

Blind Bartender’s Problem: The Four Glass Puzzle

Puzzle

The four glasses puzzle, also known as the blind bartender’s problem, is a logic puzzle first publicized by Martin Gardner in his “Mathematical Games” column in the February 1979 edition of Scientific American.

Four glasses are placed on the corners of a square table. Some of the glasses are upright (facing upwards) and some upside-down (facing downwards). You have to arrange the glasses so that they are all facing up or all facing down (while keeping your eyes closed all the time). The glasses may be re-arranged in turns subject to the following rules.

  1. Any two glasses may be inspected in one turn and after feeling their orientation you may reverse the orientation of either, neither or both glasses.
  2. After each turn table is rotated through a random angle.
  3. At any point of time if all four glasses are of the same orientation a ring will bell

You have to come up with a solution to ensure that all glasses have the same orientation (either up or down) in a finite number of turns. The algorithm must be non-stochastic i.e. it must not depend on luck.

Solution:-

  1. On the first turn choose a diagonally opposite pair of glasses and turn both glasses up.
  2. On the second turn choose two adjacent glasses. At least one will be up as a result of the previous step. If the other is down, turn it up as well. If the bell does not ring then there are now three glasses up and one down (3U and 1D).
  3. On the third turn choose a diagonally opposite pair of glasses. If one is down, turn it up and the bell will ring. If both are up, turn one down. There are now two glasses down, and they must be adjacent.
  4. On the fourth turn choose two adjacent glasses and reverse both. If both were in the same orientation then the bell will ring. Otherwise there are now two glasses down and they must be diagonally opposite.
  5. On the fifth turn choose a diagonally opposite pair of glasses and reverse both. The bell will ring for sure.

The puzzle can be generalized to n glasses instead of four. For two glasses it is trivially solved in one turn by inverting either glass. For three glasses there is a two-turn algorithm. For five or more glasses there is no algorithm that guarantees the bell will ring in a finite number of turns.

A further generalization allows k glasses (instead of two) out of the n glasses to be examined at each turn. An algorithm can be found to ring the bell in a finite number of turns as long as k ≥ (1 − 1/p)n where p is the greatest prime factor of n.


Crossing the Bridge Puzzle

Puzzle: 

Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person: 1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?

Puzzle Solution:

It is 17 mins.
1 and 2 go first, then 1 comes back. Then 7 and 10 go and 2 comes back. Then 1 and 2 go again, it makes a total of 17 minutes.

5 Pirates Fight for 100 Gold Coins Puzzle

Puzzle: 

There are 5 pirates in a ship. Pirates have hierarchy C1, C2, C3, C4 and C5.C1 designation is the highest and C5 is the lowest. These pirates have three characteristics : a. Every pirate is so greedy that he can even take lives to make more money.  b. Every pirate desperately wants to stay alive. c. They are all very intelligent.There are total 100 gold coins on the ship. The person with the highest designation on the deck is expected to make the distribution. If the majority on the deck does not agree to the distribution proposed, the highest designation pirate will be thrown out of the ship (or simply killed). The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 5 devises a plan which he knows will be accepted for sure and will maximize his gold. What is his plan?

Solution:
To understand the answer,we need to reduce this problem to only 2 pirates. So what happens if there are only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates, the proposal has to be accepted leaving Pirate 1 with nothing.

Now let’s look at 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted.

If there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the distribution will be {0, 1, 0, 99}.

Smart right? Now can you figure out the distribution with 5 pirates? Let’s see. Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.

Other Way:-

Puzzle2

5 pirates of different ages have a treasure of 100 gold coins.

On their ship, they decide to split the coins using this scheme:

The oldest pirate proposes how to share the coins, and ALL pirates (including the oldest) vote for or against it.

If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.

As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard.

Assuming that all 5 pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen?

Solution 2
The oldest pirate will propose a 98 : 0 : 1 : 0 : 1 split, in other words the oldest pirate gets 98 coins, the middle pirate gets 1 coin and the youngest gets 1 coin.

Let us name the pirates (from oldest to youngest): Alex, Billy, Colin, Duncan and Eddie.

Working backwards:

2 Pirates: Duncan splits the coins 100 : 0 (giving himself all the gold). His vote (50%) is enough to ensure the deal.

3 Pirates: Colin splits the coins 99 : 0 : 1. Eddie will accept this deal (getting just 1 coin), because he knows that if he rejects the deal there will be only two pirates left, and he gets nothing.

4 Pirates: Billy splits the coins 99 : 0 : 1 : 0. By the same reasoning as before, Duncan will support this deal. Billy would not waste a spare coin on Colin, because Colin knows that if he rejects the proposal, he will pocket 99 coins once Billy is thrown overboard. Billy would also not give a coin to Eddie, because Eddie knows that if he rejects the proposal, he will receive a coin from Colin in the next round anyway.

5 Pirates: Alex splits the coins 98 : 0 : 1 : 0 : 1. By offering a gold coin to Colin (who would otherwise get nothing) he is assured of a deal.

(Note: In the final deal Alex would not give a coin to Billy, who knows he can pocket 99 coins if he votes against Alex's proposal and Alex goes overboard. Likewise, Alex would not give a coin to Duncan, because Duncan knows that if he votes against the proposal, Alex will be voted overboard and Billy will propose to offer Duncan the same single coin as Alex. All else equal, Duncan would rather see Alex go overboard and collect his one coin from Billy.)


Tuesday, March 29, 2016

3 Employee Average salary

Problem:-

How can three employees calculate the average of their salaries without knowing other’s salary

Solution:-

Let's say the three co-workers are A, B, and C and their individual salaries are Sa, Sb, and Sc respectively. For knowing the average of their salaries without disclosing their own salaries to each other, they follow these steps:-
A adds a random amount, say Ra to his own salary and gives that to B (B won't be able to know A's salary as he has added a random amount known to him only). In this case, B will receive the figure (Sa + Ra) from A.
B does the same and gives the final amount to C (without showing that to A). Now C will get the figure (Sa + Ra + Sb + Rb).
C does the same and gives the final figure to A (without showing it to B). Now, A will receive the figure (Sa + Ra + Sb + Rb + Sc + Rc).
Now A subtracts his random amount and gives the final figure to B (without showing that to C). B will now receive the figure (Sa + Sb + Rb + Sc + Rc).
B subtracts his random amount and gives the final figure to C (without showing it to A). C will receive the figure (Sa + Sb + Sc + Rc).
C subtracts his random amount and then the figure becomes (Sa + Sb + Sc). It's shown to everyone and by they get to know the average simply by dividing this figure by 3. Cool... isn't it?

It's important to note here that at every stage (except the very last where C subtracts his random amount), only two co-workers communicating each other should know the fugures and not the third one.

We can apply the same technique to know the average of more than 3 people as well. We just need to remember that at every stage only two people should share the figures and rest other should not be communicated that. What are you waiting for? Find the average salary of your team. No one needs to disclose his/her own salary