Friday, December 9, 2011

In how many ways 3 identical coins can be placed in 5x5 grid so that no two coin come in same row and same column

First coin can be placed in one of 25 places. For second, only 16 places are possible because of the same column and same row condition. Similarly, only 9 places for third coin. So, total ways = 25 * 16 * 9. but since coins are identical you can't distinguish one from another and thus final answer is ( 25*16*9 ) / 3 = 1200.

Feel Free to Let Us Know Your Comment if anything wrong ?

Sunday, October 30, 2011

Two_envelopes_problem

  1. Someone gives you two envelopes with cash inside, and tells you that one of the envelopes has twice as much as the other. You're asked to pick an envelope and open it. You pick Envelope 1 and you open it to reveal $100. Awesome! And now that person asks you if you'd like to switch to Envelope 2, for a cost of merely $5. What should you do ?
  2. The basic setup: You are given two indistinguishable envelopes, each of which contains a positive sum of money. One envelope contains twice as much as the other. You may pick one envelope and keep whatever amount it contains. You pick one envelope at random but before you open it you are offered the possibility to take the other envelope instead.[3]
  3. The switching argument: Now suppose you reason as follows:

  1. I denote by A the amount in my selected envelope.
  2. The probability that A is the smaller amount is 1/2, and that it is the larger amount is also 1/2.
  3. The other envelope may contain either 2A or A/2.
  4. If A is the smaller amount the other envelope contains 2A.
  5. If A is the larger amount the other envelope contains A/2.
  6. Thus the other envelope contains 2A with probability 1/2 and A/2 with probability 1/2.
  7. So the expected value of the money in the other envelope is

    {1 \over 2} (2A) + {1 \over 2} ({A \over 2}) = {5 \over 4}A
  8. This is greater than A, so I gain on average by swapping.
  9. After the switch, I can denote that content by B and reason in exactly the same manner as above.
  10. I will conclude that the most rational thing to do is to swap back again.
  11. To be rational, I will thus end up swapping envelopes indefinitely.
  12. As it seems more rational to open just any envelope than to swap indefinitely, we have a contradiction
  1. The puzzle: The puzzle is to find the flaw in the very compelling line of reasoning above

  1. http://en.wikipedia.org/wiki/Two_envelopes_problem

Thursday, October 20, 2011

Whats The Expected Number of Tosses to to Get Head.

Getting a Head a probability of p and getting a tail of probability 1-p .then find Whats The Expected Number of Tosses to to Get Head.?

Thursday, August 25, 2011

what is the expected number of times he will have to toss his coin to see that pattern.

One day Rohil was getting very bored so he was tossing an unbiased coin randomly. He observed that certain patterns (a sequence of Head and Tail) appear very frequently while some other are very rare. Being a programmer he decided to code a solution which takes a pattern string as input and tells what is the expected number of times he will have to toss his coin to see that pattern. He wrote this program very quickly. Can you?

Input

First line contains ( 1<=T<=25 ) the number of test cases. Each of following T lines contains a pattern string of 'H' and 'T' only. H is for Head and T is for Tail.

|S| <= 40
Output

For each test case print the output in a new line (it is guaranteed that answer will always be an integer and fits in 64 bit type).
Example

Input:
3
H
HTHT
TTHTHTHTHTHHTHTHTHTTTTTTHTHHHHHTT

Output:
2
20
8589934598

Solution http://www.se.cuhk.edu.hk/~seem3570/12-pattern.pdf
http://deepblue.lib.umich.edu/bitstream/2027.42/24435/1/0000708.pdf

Thursday, August 11, 2011

6 Bullet & a Pesron Puzzle

You have been taken hostage by terrorists. Terrorist has a revolver with 6 empty chambers. He now loads the revolver with 2 bullets in front of you. These two bullets are kept next to each other (contiguously) in the 2 adjacent chambers, the terrorist now spins the barrel so that now you don't know what is location of bullets in chamber. He keep the revolver against your head and pulls the trigger. But its lucky day for you. It was the empty chamber. Now terrorist gives a slight chance to get free. He gives you a choice whether he should spin the barrel first then pull the trigger again.. or should just simply pull the trigger again ? If you get lucky again, terrorists will let you go..otherwise ..!!!


So what would you prefer ? Would you want him to spin the barrel first then shoot or just shoot without spinning the barrel ?

Minimum number of cuts to the bar of gold that will allow you to pay to worker 1/7th each day ?

A worker is to perform work for you for seven straight days. In return for his work, you will pay him 1/7th of a bar of gold per day. The worker requires a daily payment of 1/7th of the bar of gold. What and where are the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?

Solution
Gold bar need minimum two cuts. It should be divided in powers of two.
e.g. for i=0 to k where 2^k is nearly equals to N length of gold piece. 1 ,2 , 4........assuming 7 parts which is divided into a total of 1,2,4.

first day : 1 ---(1)
second day: take back one and give 2----(2)
third day : give back one----(1,2)
fourth day : take back 2,1 and give 4 ----(4)
fifth day : give back 1------(1,4)
sixth day : give 2 and take back 1-----(4,2)
sevent day : give back one-------(1,2,4)

Tuesday, August 9, 2011

What is the probability that you toss next time, heads turns up.

A bag contains 5 coins. Four of them are fair and one has heads on
both sides. You randomly pulled one coin from the bag and tossed it 5
times, heads turned up all five times. What is the probability that
you toss next time, heads turns up. (All this time you don't know you
were tossing a fair coin or not).


The probability of getting n consecutive heads is
P(n heads) = 1/5 * 1 + 4/5 * (1/2)^n,
Thus, the probability of getting a head on the n+1st roll given that
you have gotten heads on all n previous rolls is
P(n+1 heads | n heads) = P(n+1) / P(n)
= ( 1/5 * 1 + 4/5 * (1/2)^(n+1) ) / ( 1/5 * 1 + 4/5 * (1/2)^n ).
Multiplying numerator and denominator by 5* 2^(n-1) and recognizing 4
as 2^2 gives
P(n+1 heads | n heads) = (2^(n-1) + 1) / (2^(n-1) + 2)

put n=5 in above expression probability that you toss next time, heads turns up will be 17/18

Saturday, August 6, 2011

What is the probability that the outside of this cube is completely black?

Twenty seven identical white cubes are assembled into a single cube,
the outside of which is painted black. The cube is then disassembled
and the smaller cubes are thoroughly shuffled in a bag.

A blindfolded man (who cannot feel the paint) reassembles the pieces
into a cube. What is the probability that the outside of this cube is
completely black?

Thursday, August 4, 2011

Some Interesting Probablity Puzzles

Balls into Bins



1. Given n balls and n bins. We throw each ball uniformly randomly into the bins. What is the expected number of (i) empty bins (ii) bins containing one ball (iii) bins containing k balls



2. Given an unlimited supply of balls and a set of n empty bins. We take a ball from the supply and throw it randomly among the bins so that its chances of landing into any of the n bins is same. We continue throwing the balls until no bin is left empty. What is the expected number of balls thrown before no bin is left empty ?



3. Consider the following experiment that proceeds in a sequence of rounds. For the first round, we have n balls, which are thrown uniformly randomly into n bins. After round i , we discard every ball that fell into a bin itself in round i . The remaining balls are retained for i+1 round, in which they are again thrown independently and uniformly at random into the n bins. We stop when there is no ball left. Prove that with probability 1- o(1) the experiment will finish in loglog n number of rounds.



Balls out of Bin

1. A bin contains a white balls and b black balls. We take out the balls at random from the bin without replacement. What is the probability that first ball is white, second ball is white, kth ball is white.



2. A bin contains n balls numbered 1,2,...,n . We pick a bunch of k balls from the bin uniformly randomly. What is the
(i) expected number of the greatest numbered ball in the bunch.
(ii) expected number of the least numbered ball in the bunch.



3. There are n bins and n players, and each player has an infinite supply of balls. The bins are initially empty. We have a sequence of rounds : in each round, each player throws a ball into an empty bin chosen independently at random from all currently empty bins. Let the random variable Z be the number of rounds before every bin is non-empty. Determine the expected value of Z. What can you say about the distribution of Z?



4. A bin contains m white balls and n black balls. We take out the balls uniformly randomly from the bin without replacing them. What is the expected number of black balls left when all the white balls have been taken out.

Monday, July 25, 2011

There are four dogs each at the corner of a unit square. Each of the dogs starts chasing the dog in the clockwise direction. They all run at the same speed and continuously change their direction accordingly so that they are always heading straight towards the other dog. How long does it take for the dogs to catch each other and where?

Since the dogs are moving symmetrically, the distance saperating them will decrease evenly as they case each other, so the dogs should catch each other in the center of the room. Their path will be curved, but for sake of approximation, lets se it’s a straigt line to the center.

Assuming that the dogs run at 1m/sec, and room is y x y in diamater.

h^2 = (y/2)^2 + (y/2)^2
h^2 = 2(y/2)^2
h = sqrt(2) * y/2
h = y/sqrt(2) meters

thus it would take the dogs approximtly y/sqrt(2) seconds to catch each other. This is a lower bounds, as the dog will not be traveling in a straight line, but along a curve.

Some Other & Good Aproaches are

Each dog starts at the corner and moving symmetrically. So each dogs start moving perpendicular to the adjacent dogs. Lets assume v.

So each one start moving with v towards the next dog.

If we see realtive speed of the dog1 (v1), w.r.t dog 2, it changes perpendicularly. So it’ll not affect the time taken along the direction of the dog1 to dog2 and the speed will be v only always.

So it they have started at corners with the distance of the length of the square(s).

Time = s/v. They’ll meet at the center.

Another Similar Approach is

Let’s the dogs be A, B, C and D where A is chasing B, B is chasing C, C is chasing D and D is chasing A.
All the dogs will eventually meet in the center of the square. Since all the dogs move in symmetry, the only logical answer to the location of their meeting is the center of the square.
At any point in time, dog A is perpendicular to dog B and B perpendicular to C and so on. Dog A moves towards dog B but dog B does not move towards or away from dog A since it is moving perpendicular to dog A. Therefore, the distance that dog A needs to cover to reach dog B is the same as the original distance between them, one unit.

The speed of each of the dog towards the dog it is chasing is given by (1 + cos(t)) where t is the angle on each corner of the square.

Speed of dog = 1 + cos(90) = 1 + 0 = 1
Time needed = Distance/Speed = 1 / 1 = 1 unit.

A Heavan Puzzle

Wednesday, July 20, 2011

Google Puzzle- who keeps the fish?

Facts:*

1: There are 5 villas in 5 different colors
2: In each villa lives a person with a different nationality.
3: These 5 owners drink a certain beverage, smoke a certain brand of cigar
and keep a certain pet.
4: No owner has the same pet, smoke the same brand of cigar or drink the
same drink.


*Hints:*

1: The British lives in a red villa.
2: The Swede keeps dogs as pets
3: The Dane drinks tea
4: The green villa is on the left of the white villa (it also means they are
next door to each other)
5: The green villa owner drinks coffee
6: The person who smokes Pall Mall rears birds
7: The owner of the yellow villa smokes Dunhill
8: The man living in the villa right in the center drinks milk
9: The Norwegian lives in the first villa
10: The man who smokes Blend lives next to the one who keeps cats
11: The man who keeps horses lives next to the man who smokes Dunhill
12: The owner who smokes Blue Master drinks beer
13: The German smokes Prince
14: The Norwegian lives next to the blue villa
15: The man who smokes Blend has a neighbor who drinks water.

*The question is: who keeps the fish?

Monday, July 4, 2011

Minimum Number of Cuts Needed to Cut Rope in get the rope of desired length

the length of the rope is l units.
I can only cut any rope into two halves. for example if the length of the rope is 8 and we need a length of rope 6 we first cut into two halves and we get 4, 4 now we cut any of the half again and we get 4,2,2 now we can merge 4 and 2 and form a rope of length 6. in this example we need a minimum of 2 cuts to get the length of rope 6 from 8

assume that l is always a power of 2 and we need always a even length of rope from it how to find the number of minimum cuts needed to get the new rope?.

1st Solution

k -> rope of desired length.
l -> rope of given length
m = 2;
while(k%m==0 )
m *= 2;
ans :: (log2(l) - log2(m) + 1).
ex.
k = 6,l = 8
so initially m = 2;
after 1st iteration m = 4;
then break;
so min = log2(8) - log2(4) + 1 = 3 -2 + 1 = 2.


2nd Solution
for a number N
first set bit(From Left) is simply integer value of log(N)
last set bit can be calculated as
N = N-(N&(N-1)); and then Log(N)
int i = log(n);
n -= n&(n-1);
int j = log(n);
i-j will be the answer.

Refer here for more detail

Thursday, June 30, 2011

A Triangle Puzzle

three points are randomly chosen on a circle.what the probability that
1.triangle formed is right angled triangle.
2.triangle formed is acute angled triangle.
3.triangle formed is obtuse angled triangle.

Let the three vertices be A, B, C. We denote the angle at
center by the arcs AB, BC, CA by x, y, z.

x + y + z = 360.

Hence, the sample space can be represented by the region
surrounded by lines

x > 0,
y > 0 , and
x + y < 360. For the acute angled triangle ABC max(x, y, z) < 180, i.e., x < 180, y < 180, and x + y > 180

It can be easily seen that the three constraints form a
region which has exactly 1/4-th area of the original
sample space.

Solution Given abc

Monday, June 27, 2011

Secratry Puzzle ( A Kind of Hat having Balls)

A hat contains n balls, each with a number on it. On each turn, a ball is drawn uniformly at random and without replacement, and shown to you. If you are able to identify the ball with the largest number when it is drawn, you win the game. Give an algo/technique that wins with probability at least 1/4.


The secretary problem is an optimal stopping problem that has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem. The solution is sometimes called the 37% rule. The problem can be stated as follows:

1. There is a single secretarial position to fill.
2. There are n applicants for the position, and the value of n is known.
3. The applicants can be ranked from best to worst with no ties.
4. The applicants are interviewed sequentially in a random order, with each order being equally likely.
5. After each interview, the applicant is accepted or rejected.
6. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
7. Rejected applicants cannot be recalled.
8. The objective is to select the best applicant. The payoff is 1 for the best applicant and zero otherwise.

Terminology: A candidate is an applicant who, when interviewed, is better than all the applicants interviewed previously. Skip is used to mean "interview and reject".

Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) has a surprising feature. Specifically, for large n the optimal policy is to interview and reject the first n/e applicants (where e is the base of the natural logarithm) and then to accept the next who is better than these interviewed candidates. As n gets larger, the probability of selecting the best applicant from the pool goes to 1/e, which is around 37%. Whether one is searching through 100 or 100,000,000 applicants, the optimal policy will select the single best one about 37% of the time.

Solution http://en.wikipedia.org/wiki/Secretary_problem

Tuesday, June 21, 2011

Fogcreek programmers Variation of Hat Puzzle

100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can’t see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says “what color is your hat?” the fogcreek programmer can only answer “red” or “blue.” the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can’t communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?

Solution

this is a very difficult problem to solve during an interview (especially if you’ve already taxed the candidate’s brain). look for obvious solutions first, and the reasoning behind them and then try to lead them to the ultimate solution.

a logical answer could be all the programmers would just say “red” and that way about half of them would survive on average, assuming the hats were distributed randomly.

this is a good start and should naturally lead to having every other programmer say the color of the hat in front of them. the first programmer would say the color of the hat in front of him, then the next programmer would just say that color that was just said. so we can guarantee that half survive - the even numbered programmers (since the person behind them told them the answer). and potentially if the hats were distributed randomly some of the programmers would get lucky and the hat in front of them would be the same color as their own. so this strategy should save more than half, and on average 75% of them would live.

at this point, if the solution is not clear, the candidate may give answers like, “they could agree that if they said their hat color in a soft voice, it means the hat in front of them is the same color, and if they say it in a loud voice, it means the hat in front is a different color”. this is definitely good and on the correct track. another option is they could say “reeeeeeeeeeed” for x number of seconds, where x represented the distribution of hats where a hat was a bit in a binary number, (red = 1, blue = 0). another interesting answer. there are many others like these that “bend” the rules and come to a solution.

but the real solution acknowledges that the programmers can only say “red” or “blue” and cannot alter their voice in such a convincing way as to signal any information other than the word they said. a good way to get this point across, is simply to change the problem slightly by saying “the assassin gets to hear their plan before she puts the hats on, and so will try to thwart the plan however she can.”

so if they decide to all say “red”, she’ll put blue hats on all of them. if they decide to all say the color of the hat in front of them, she’ll alternate the hats on every head, guaranteeing half will die. even with the assassin hearing their plan, there is still a way to save almost everyone.

we know that the first person is never going to have any information about the color of their hat, so they cannot be guaranteed to survive. but, i’ll give you a hint to the solution: i can save every other person for sure.

solution: they agree that if the number of red hats that the back person can see is even, that programmer will say “red”. if they add up to an odd number, they will say “blue”. this way number 99 can look ahead and count the red hats. if they add up to an even number and number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signalling an odd number of red hats, number 99 must also be wearing a red hat. number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98’s head.

sample:

100 99 98 97 96 95 94 ... facing ->
R B B R B R B ... -> 45 R and 48 B

this shows #100 wearing a red hat, 99 a blue, 98 a blue, 97 a red, 96 a blue, 95 a red, 94 a blue and 45 red hats - 48 blue hats on the people in front of them.

100 counts up the red hats: 47 total. so 100 says “blue”. the assassin kills 100. 99 counts up the red hats in front: 47. 100 said blue, so 100 saw an odd number. 99 sees an odd number, so 99 says “blue” and lives. 98 had counted 47 red hats, and 99 didn’t say “red” so thats still the total. 98 says “blue”. 97 counts up and finds 46 red hats. 99 and 98 didn’t say “red”, so his count is missing a red hat (its on his head, he realizes). he says “red”. 96 heard the “red” and now knows that there are an even number of “red” hats in front of 95. 96 sees 46, so he knows he has a “blue” hat. etc…

even if the assassin knows the plan, she can’t thwart it. she hears the plan, but she still has to put the hats on their heads. the plan doesn’t rely on any ordering of the hats, so the worst the assassin can do is to make sure #100 gets killed and thats the worst damage she can do.

Check if Given Date is Palindrom or Not

Problem: this year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards).
10/02/2001
when was the last date that this occurred on? (see if you can do it in your head!)

Solution: we know the year has to be less than 2001 since we already have the palindrome for 10/02. it can’t be any year in 1900 because that would result in a day of 91. same for 1800 down to 1400. it could be a year in 1300 because that would be the 31st day. so whats the latest year in 1300 that would make a month? at first i thought it would be 1321, since that would give us the 12th month, but we have to remember that we want the maximum year in the 1300 century with a valid month, which would actually be 1390, since 09/31 is a valid date.

but of course, a question like this wouldn’t be complete without an aha factor. and of course, there are not 31 days in september, only 30. so we have to go back to august 08 which means the correct date would be 08/31/1380.

palindromes also offer another great string question.
write a function that tests for palindromes
bool isPalindrome( char* pStr )

if you start a pointer at the beginning and the end of the string and keep comparing characters while moving the pointers closer together, you can test if the string is the same forwards and backwards. notice that the pointers only have to travel to the middle, not all the way to the other end (to reduce redundancy).

bool isPalindrome( char* pStr )
{
if ( pStr == NULL )
return false;

char* pEnd = pStr;
while ( *pEnd != '\0' )
pEnd++;

pEnd--;

while(pEnd > pStr)
{
if ( *pEnd != *pStr )
return false;

pEnd--;
pStr++;
}

return true;
}

How can you get a fair coin toss if someone hands you a coin that is weighted to come up heads more often than tails?

Hint:Treat outcome TH as tails, HT as heads, and reflip when you get TT and HH.

Explaination

f a cheat has altered a coin to prefer one side over another (a biased coin), the coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure:[1]

1. Toss the coin twice.
2. If the results match, start over, forgetting both results.
3. If the results differ, use the first result, forgetting the second.

The reason this process produces a fair result is that the probability of getting heads and then tails must be the same as the probability of getting tails and then heads, as the coin is not changing its bias between flips and the two flips are independent. By excluding the events of two heads and two tails by repeating the procedure, the coin flipper is left with the only two remaining outcomes having equivalent probability. This procedure only works if the tosses are paired properly; if part of a pair is reused in another pair, the fairness may be ruined.

Mathematically We Can Write
Lets define an event, E as tossing the biased coin twice. The possible outcomes with probabilities is as follows

P(h,h) = x^2
P(h,t) = x(1-x)
P(t,h) = x(1-x)
P(t,t) = (1-x)^2

The event h,t or t,h are equi-likely, without any bias we can call that if Event h,t occurs it means head, t,h means tails but if h,h or t,t occurs we repeat the experiment.

Try to find the expected number of coin toss that would be required to call heads or tails?

Let expected coin toss be e.

Probability that we get outcome in 1st event is 2x(1-x)
Total number of coin toss would be 2
Probability that we get no outcome in 1st event is [1 - 2x(1-x)]
Total number of coin toss would be 2 + e (we wasted 2 coin toss and still we expect e)

==> e = 2 * 2x(1-x) + (2+e) * [1 - 2x(1-x)]
==> e = 4x(1-x) + 2 - 4x(1-x) + e - 2ex(1-x)
==> e = 1/ [x(1-x)]

so for x = 1/2, e = 4
for x=2/3, e = 4.5
for x=1, e = INF (as expected, because all we get is chain of h h h h h)


What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?

p = prob of e heads + prob of e tail
==> p = x^e + (1-x)^e

To find a bound on this p in polynomial terms can be done by using binomial expansion and Newtonian series is out of the scope of this blog. But some number crunching is.

For x = 1/2, e = 4, p = 0.125
For x = 2/3, e = 4.5, p = 0.168
For x = 3/4, e = 5.33, p = 0.216
For x = 0.99, e = 101, p = 0.362

This tells us that probability that outcome comes is quite good even for high coin biases.


How can we improve on the expected number of coin tosses?

In above method, we say that HT or TH terminates experiment. and continue the experiment a fresh when the outcome is HH or TT.

We can further combine outcome of two such events to increase the probability of outcome e.g. say HH TT => heads and TT HH means tails.


How much expected coin tosses are we doing in this case?

try?

Feel Free to Write Comment or Suggestion

Find The Number of Pages in Printing Book,if Tottal Number of Digits Printed is Given

There is a printed book. The page numbers are not printed. Now the printing of page numbers is being done separately. If the total number of digits printed is 1095 then how many pages does the book have?



There are 9 significant single digit numbers. Hence for the first 9 pages, 9x1 = 9 digits will be printed.

There are 90 significant double digit numbers. Hence for the next 90 pages, 90x2 = 180 digits will be printed. Total number of pages = 99 (90 plus 9), total number of digits is 189(9 plus 180) till now.

Subsequently, we have 900 significant triple digit numbers and 900x3 = 2700 digits. Since the total number of digits printed lies in the range [189, 2889], it suggests that all double digit numbers were printed and some triple digit numbers were printed. The upper limit is arrived at as 2700 plus 189.

Number of digits used to print triple digit numbers = 1095 -189 = 906.

Therefore, 906/3 = 302 triple digit numbers were used.

Therefore the total number of pages printed = 9 plus 90 plus 302 = 401.

That is how solution: 401

Feel Free to Comment or Suggesting New Approaches .

Wednesday, May 18, 2011

Seven Bridges of Königsberg (Unsolvable Puzzle in Computer Science))

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology.

The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.

The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side).



Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges

Data Structure Can be Used to Represent The Puzzle: Graph

Solution. (Unsolvable Puzzle in Computer Science)

Reason: Its application of Graph Data Structure (Idea Comes In Mind as Studied The Puzzle Carefully). so we have to traverse each bridge one & only once & returned back to source vertex if we draw the graph of this problem we found that each vertex has odd degree so its not possible to satisfy the puzzle solution. in 17's Euler already proved it unsolvable problem of computer science & said we can solve this if we have each vertex of even degree.

See This Graph Representation




Fell Free to Comment & Suggest your Approach

Sum & Product Puzzle

X and Y are two different integers, greater than 1, with sum less than 100. S and P are two mathematicians; S knows the sum X+Y, P knows the product X*Y, and both know the information in these two sentences. The following conversation occurs.

* P says "I cannot find these numbers."
* S says "I was sure that you could not find them."
* P says "Then, I found these numbers."
* S says "If you could find them, then I also found them."





What are these numbers?
Solution

The solution has X and Y as 4 and 13 (or vice versa), with P initially knowing the product is 52 and S knowing the sum is 17.

Initially P does not know the solution, since

52 = 4 × 13 = 2 × 26

and S knows that P does not know the solution since all the possible sums to 17 within the constraints produce similarly ambiguous products. However, each can work out the solution by eliminating other possibilities following the other's statements and that is enough for the reader to find the solution given the constraints.

Water,Glass, Electricity

Suppose there are three cottages on a plane (or sphere) and each needs to be connected to the gas, water, and electric companies. Using a third dimension or sending any of the connections through another company or cottage are disallowed. Is there a way to make all nine connections without any of the lines crossing each other?

Solution

The answer is no; It is impossible to connect the three cottages with the three different utilities without at least one of the connections crossing another.

As You Can The Possible Graph Made to fulfill All the Condition is Like This




The problem is part of the mathematical field of topological graph theory which studies the embedding of graphs on surfaces. In more formal graph-theoretic terms, the problem asks whether the complete bipartite graph K3,3 is planar. This graph is often referred to as the utility graph in reference to the problem.[1] The graph is equivalent to the circulant graph Ci6(1,3). Kazimierz Kuratowski proved in 1930 that K3,3 is nonplanar, and thus that the problem has no solution.

One proof of the impossibility of finding a planar embedding of K3,3 uses a case analysis involving the Jordan curve theorem, in which one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding. Alternatively, it is possible to show that any bridgeless bipartite planar graph with n vertices and m edges has m ≤ 2n − 4 by combining the Euler formula n - m + f = 2 (where f is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (because each face has at least four edges and each edge belongs to exactly two faces). In the utility graph, m = 9 and 2n − 4 = 8, violating this inequality, so the utility graph cannot be planar.

Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor the complete graph K5 as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor K5 as a minor, encompass this result.

Tumblers on a Rotating Table- 3 Glass & 4 Glass

The three cups problem is a mathematical puzzle. Starting with three cups place one upside down and two right side up. The objective is to eventually turn all cups right side up in six moves. You must turn exactly two cups over each turn.
[edit] Solution

The puzzle is impossible. An even number of cups are facing up and you are allowed to turn two over at a time. Since an even plus an even is an even, not an odd, no number of even flips will ever get all the three cups face up. You need an odd number of cups facing up, so the problem is impossible. The possible version of this puzzle is to start with two cups facing down and one cup facing upward. This is possible. Turn up an even number (two) of cups, and all the cups are facing up; an odd plus an even is an odd (1+2 = 3).






Tumblers on a Rotating Table Puzzle :

A blind gnome and an evil goblin take turns to play a game. Four tumblers are placed at the corners of a square table. The initial configuration of the tumblers (facing up or facing down) is chosen by the evil goblin. When the blind gnome gets his turn, he is allowed to specify a subset of the four tumblers and flip them simultaneously. To be precise, he may choose “one tumbler”, “two diagonally opposites”, “two adjacent”, “three tumblers” or “four tumblers” lying in front of him, and flip them simultaneously. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues and the evil goblin is allowed to rotate the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy?

Solution :


If there were only two cards, then “flip both” — “flip one” — “flip both” would ensure a victory for the blind gnome. For the case of four cards, let F denote “all four cards”, A denote “two adjacent cards”, D denote “two diagonally opposite cards”, O denote “one card”. Then the following 15-step sequence ensures victory for the blind gnome: F, D, F, A, F, D, F, O, F, D, F, A, F, D, F. The procedure can be generalized to 2^n cards. This problem is studied in detail by Ehrenborg and Skinner (see bibliography below); they call it “The Blind Bartender’s Problem”.
A variant of the above problem allows the blind gnome to first “touch” any t out of n tumblers on a polygonal table with n sides. Touching allows the gnome to deduce which of the t tumblers he touched are upright, and then to decide which of these t tumblers to flip. It was this variant that was originally published in Martin Gardner’s article in Feb 1979. For four tumblers, the blind gnome can win in five moves, as Gardner showed in his subsequent article in Mar 1979. The problem generated quite some interest. Two pairs of mathematicians independently proved that the blind gnome can win with a deterministic strategy if and only if t ≥ n(p-1)/p where p is the largest prime factor of n (Lewis and Willard in 1980; Laaser and Ramshaw 1981). These proofs are quite involved

Saturday, May 14, 2011

Which Box Has Defective Balls

You have 10 boxes of balls (each ball weighing exactly10 gm) with one box with defective balls (each one of the defective balls weigh 9 gm). You are given an electronic weighing machine and only one chance at it. How will find out which box has the defective balls?



Firstly 10 boxes of ball kept in a queue and mark it as box1,box2,box3.........box10
then from 1st box we have to take 1 ball,from 2nd box 2 ball..........from 10th box we kept 10 balls. and weight the total ball....

so if total nos ball is :n(n+1)/2 (n= total nos of box that is 10)=55
if all the ball is 10 gm.then total weight will be=550gm.
suppose total weight is 546gm.
so the difference is(550-546=4gm).
then the d defective ball is in box no:4.
similarly we can try for all possible box difference gives us the box number which contains the defective balls

Whats The Age of 3 Childs .?????

A man walks into a bar, orders a drink, and starts chatting with the bartender. After a while, he learns that the bartender has three children. "How old are your children?" he asks. "Well," replies the bartender, "the product of their ages is 72." The man thinks for a moment and then says, "that's not enough information." "All right," continues the bartender, "if you go outside and look at the building number posted over the door to the bar, you'll see the sum of the ages." The man steps outside, and after a few moments he reenters and declares, "Still not enough!" The bartender smiles and says, "My youngest just loves strawberry ice cream." How old are the children?




Answer :

First, determine all the ways that three ages can multiply together to get 72:


72 1 1 (quite a feat for the bartender)
36 2 1
24 3 1
18 4 1
18 2 2
12 6 1
12 3 2
9 4 2
9 8 1
8 3 3
6 6 2
6 4 3
As the man says, that's not enough information; there are many possibilities. So the bartender tells him where to find the sum of the ages--the man now knows the sum even though we don't. Yet he still insists that there isn't enough info. This must mean that there are two permutations with the same sum; otherwise the man could have easily deduced the ages.

The only pair of permutations with the same sum are 8 3 3 and 6 6 2, which both add up to 14 (the bar's address). Now the bartender mentions his "youngest"--telling us that there is one child who is younger than the other two. This is impossible with 8 3 3--there are two 3 year olds. Therefore the ages of the children are 6, 6, and 2.

Question

A variant of the problem is for the sum of the ages to be 13 and the product of the ages to be the number posted over the door. In this case, it is the oldest that loves ice cream. Then how old are they?


In the sum-13 variant, the possibilities are:
11 1 1
10 2 1
9 3 1
9 2 2
8 4 1
8 3 2
7 5 1
7 4 2
7 3 3
6 6 1
6 5 2
6 4 3

The two that remain are 9 2 2 and 6 6 1 (both products equal 36). The final bit of info (oldest child) indicates that there is only one child with the highest age. This cancels out the 6 6 1 combination, leaving the childern with ages of 9, 2, and 2.

Chess Queen Puzzle

Imagine there are infinite number of Queens (Chess Game Piece) with u. Find the minimum number of queens required so that every square grid on the chess board is under the attack of a queen. Arrange this minimum no. of Queens on a chess board.



to solve it we have to think all possible combination. because we have to find out the one can easily solve it if he has strong foundation of backtracking algorithm its the geeks way to solve . although it can also be solve by trying all possible combinatios thats the normal way

start by putting queen at all position where i=j e.g. 1,1, 2,2 3,3, & so on
so then we have 8 queens like It can also be keeping one at diagonal (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7)

can we do better ..??

as we know This problem has more than one solutions. I found one with 6 queens placed at (0,0), (1,7), (2,1), (3,4), (4,2), (6, 3) now if we rotate the chess board then we can get other solution so in this case we need 6 queen can we do still do better..?? think again



it requires much deep thinking then i was able to come up with two more solution that requires 5 queens & i think that are minimum number of queens we are looking for ...

1st (1,1) (3,4) (3,6) (4,2) (5,5)
2nd (0,0) (1,7) (2,4) (4,0), (7,6)

Queen Needed 5

Feel Free to Update & Optimize Th Solution

Wednesday, May 11, 2011

Find 3 Fastest Horses from set of 25 Horses

There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.

1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?

We group the 25 horses in 5 groups each containing 5 horses.In each of first five races we will rank each five horsesA, B,C,D and E ( A : fastest and E: slowest) in the group.

1A 1B 1C 1D 1E
2A 2B 2C 2D 2E
3A 3B 3C 3D 3E
4A 4B 4C 4D 4E
5A 5B 5C 5D 5E


In the sixth race ( among the first of each group) we will get the fastest horse and rank these five horses 1A,2A,3A,4A & 5A (1A : fastest and 5A slowest)
Similarly .just select the fastest of the remaining horses from each row for the race.

Now we have got the fastest horse 1A and will also set nomenclature for each horses.
The fastest of the remaining horses in the row will take part.For e.g. the seventh race will be between 1B & 2A (no need to run 3A,4A & 5A)for determining
2nd fastest horse.

The 8th race will determine the third place and it will be between 1C and 2B ( in case 1B wins 7th race) or among 1B,2B & 3A ( in case 2A wins 7th race).

The 9th race will determine the 4th place and the 10th race will determine 5th place.

And moving on 25 th race will determine 20th place.The 26th race will tel the remaining 5 ranks.



Follow Up minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?


* min number of races to rank all of them

sol:-

1. I can re-phrase this question to ask the min number of races to get 25 fastest horses.
2. You need 6 races to get the fastest ranked (steps 1 thru 3).
3. After that every race will give you the next fastest.
4. We can continue this till we have got the 20 fastest horses. After that we just need 1 race to rank the remaining 5.

total = 6 (to get rank 1) + 19 (to get rank 2-20) + 1 (to get rank 21-25) = 26

* min number of races to get k fastest horse

sol:-

5 + k (for k <= 20 )
26 (otherwise)

Friday, April 29, 2011

How many regions (open or closed) can n straight lines give at the maximum?

Let f(n) denote the number of regions for n lines no three of which coincide in one point. This latter condition will guarantee the maximum. Obviously, f(0)=1, f(1)=2, f(2)=4, f(3)=7, etc.

Now, given n-1 lines, there are already f(n-1) regions. With the introduction of the n-th line, imagine the points of intersection of the pre-existing n-1 lines fall on one side of the n-th line. So, on one side of the n-th line -- where the points of intersection lie -- you still have f(n-1) regions, whereas on the other side of the n-th line, you now have n regions. So, for these n lines before us, the total number f(n) of regions must be equal to f(n-1)+n.

So, f(n)=f(n-1)+n. With the initial condition(s) given earlier, this gives us f(n)=1+n(n+1)/2.

we can use induction to prove the same,

Base case:
if n = 1, regions (planes) = 2

Induction Hypothesis:
Addition of a new line adds
---------------------------------------------
|n
---------------------------------------------

regions to the regions formed by previous
---------------------------------------------
|n-1
---------------------------------------------
lines, i.e.

f(n) = n + f(n-1)

Upon simplifying the above, we get f(n) = 1 + n(n+1)/2

Thursday, April 28, 2011

Weighting Puzzles One Side Weighing & two side Weighing



Puzzle 1:

The puzzle is if the shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1, 3 and 4 only. Now the question is how many minimum weights and names the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also. Answer for this puzzle is given below.

Solution :


This is simply the numbers 2^0,2^1,2^2 ... that is 1,2,4,8,16... So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, and 512. Comments your suggestions or other answers.

Puzzle 2:


This is same as the above puzzle with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg. Answer for this puzzle is given below.

Solution:


For this answer is 3^0, 3^1, 3^2... That is 1,3,9,27,81,243 and 729.

Monday, April 25, 2011

Dropping Eggs from a Building - 100 Story Building Famous Google Puzzle



Source:: Heard From Googlear in Bangalore

You stand before a 100-story building with two eggs. Using only these two eggs, you must figure out the highest floor from which you can drop an egg such that the egg won't break when it hits the ground (we'll call this the "highest safe floor"). Every floor is equally likely to be the highest safe floor, including the top floor, and it's also just as likely that the egg will break from every floor. You can assume that if you drop an egg and it doesn't break, its shell is just as strong as it was before you dropped it.

If you want to minimize the expected number of drops you have to perform, what strategy should you use for picking which floors to drop the eggs from? You should write a program to solve this problem.


Answer: The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.

Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.

Can we do even better? Yes we can (Bob, the builder). What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).

Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 – 20
15 – 20
16 – 21

So picking any one of the intervals with 19 maximum tries would be fine.

2nd Solution Discussed With Friends You Can Find This @ Many Places

Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.

Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.


Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.


(For strict computer science students, well this problem can be solved using binary search on the number of drops needed to find the highest floor.)

Now let x be the answer we want, the number of drops required.

So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.

Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task


Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

So we could write it as

(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).


3rd way to Approach Suggested by Galye Lakemann


Observation: Regardless of how we drop Egg1, Egg2 must do a linear search. i.e., if Egg1 breaks between floor 10 and 15, we have to check every floor in between with the Egg2
The Approach:
A First Try: Suppose we drop an egg from the 10th floor, then the 20th, …
»»If the first egg breaks on the first drop (Floor 10), then we have at most 10 drops total.
»»If the first egg breaks on the last drop (Floor 100), then we have at most 19 drops total (floors 10, 20, ...,90, 100, then 91 through 99).
»»That’s pretty good, but all we’ve considered is the absolute worst case. We should do some “load balancing” to make those two cases more even.
Goal: Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the first drop or the last drop.
1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
5. Solve for X+(X-1)+(X-2)+…+1 = 100. X(X+1)/2 = 100 -> X = 14
We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.

Please feel free to correct or post any comment on the solution or the answer.


4th way to Solve it Purely Computer Science Way
Dynamic Programming

Solution

The key insight to solving this problem is to realize that if you drop and egg and it doesn't break, then you are essentially going to be performing the same problem for a building of a shorter size. For example, if you were to drop an egg from floor 60 and it didn't break, you would then be solving the same problem for floors 61-100, which is like solving it on a 40-story building.

Another important realization is that if your first egg breaks, you must go down to the the highest floor that you know is "safe" (or to the bottom floor if you don't know of any safe floors), and then go up one floor at a time, dropping the egg at each floor until it breaks. This is the only way to ensure that you'll then find the highet safe floor.

Let's generalize these ideas. Assume we decide to drop the first egg from floor k.

* If it breaks, then we'll have to go down to floor 1 and drop the second egg from each floor up to (k-1), or until it breaks. In this case, we expect about k/2 more drops on average, since each of the floors below floor k is is equally likely to be the highest safe floor. In fact, the exact number of drops to expect on average is (1 + 2 + ... + (k-1) + (k-1)) / k. We'll leave it as an exercise to the reader to see why.
* If it doesn't break, then it's as if we're considering the same problem on a building of size (100 - k), where the bottom floor is floor k+1.
* There is some probability of the first egg breaking from floor k. It's actually fairly straightforward to see that this probability is (k/101), because there are 101 possible scenarios (the scenarios in which each floor is the highest safe floor, plus the scenario in which all floors are unsafe). For the general case of an n-floor building, this probability is k/(n+1)
* Thus the probability of the egg not breaking is (1 - k/101), or for the general case, (1 - k/(n+1))

This leads us to define the "Best" formula. The function Best(n), should return the best number of expected drops we can attain for a builing with n stories. We also define the function Best(n,k), which should return the best expected number of drops we can attain for a building with n stories if our first drop is from floor k.

Best(100, k) = 1
+ (probability_of_breaking_from_floor_k * expected_number_of_drops_with_sequential_dropping_starting_at_floor_1)
+ (probablity_of_not_breaking_from_floor_k * Best(100-k))

This formula is based on basic probability theory. The first 1 in the sum is for the current drop. Then we add the expected number of additional drops if the current egg does or does not break, each weighted by the probability of that situation occurring. This gives us the expected total number of drops.

We are looking for Best(100), which we can find by calculating Best(100,k) for all values of k between 1 and 100, and picking the one that returns the minimal value. The value of k associated with this minimal value is the floor we should drop the first egg from.

This formula isn't solveable as is, because it is recursive (it includes a call to the Best() function within itself). But we can see that the recursive call to Best() always uses a number less than 100. This suggests that if we can build up the values for Best() starting at Best(1), then we can use a program to iteratively build up a solution for Best(100).

And that is exactly what we'll do. Below is a program written in the Ruby programming language which solves the problem for 100 floors (though you can change the value), and finishes by printing out the proper floors to drop the egg as the dropping progresses.

Algorithm

PRINT_DEBUG = false
MAX_FLOORS = 100

def probability_of_breaking(cur_floor, num_floors)
return (cur_floor.to_f / (num_floors.to_f + 1.0))
end

def expected_drops_with_final_egg(num_floors_to_check)
if num_floors_to_check == 0
return 0.0
elsif num_floors_to_check == 1
return 1.0
else
numerator = (1..(num_floors_to_check-1)).to_a.inject(0){|p,c| p + c} + (num_floors_to_check * 2)
denominator = num_floors_to_check + 1
return (numerator.to_f / denominator.to_f)
end
end

expected_best = {0 => {:best_num_drops => 0.0, :best_start_floor => 0}}
for num_floors in 1..MAX_FLOORS
cur_best = nil
best_start_floor = nil
puts "======================= #{num_floors} Floors ======================="
for start_floor in 1..num_floors
#if the egg breaks from the current floor, we have to start from the highest floor below the current floor
# where we know the egg won't break from (or floor 1 if we haven't tested from any floors below the current floor)

puts "--- Starting on #{start_floor} of #{num_floors} floors ---" if PRINT_DEBUG
break_probability = probability_of_breaking(start_floor,num_floors)
floors_above = num_floors - start_floor
floors_below = start_floor - 1
expected_floors_if_breaks = expected_drops_with_final_egg(floors_below)
expected_floors_if_does_not_break = expected_best[floors_above][:best_num_drops]
best_expected_drops = 1.0 +
(break_probability * expected_floors_if_breaks) +
((1.0 - break_probability) * expected_floors_if_does_not_break)
puts " probability of breaking: #{break_probability} --- if breaks: #{expected_floors_if_breaks} --- if not: #{expected_floors_if_does_not_break} --- expected drops: #{best_expected_drops}" if PRINT_DEBUG

if cur_best.nil? or best_expected_drops < cur_best cur_best = best_expected_drops best_start_floor = start_floor end end expected_best[num_floors] = {:best_num_drops => cur_best, :best_start_floor => best_start_floor}
end

for k in expected_best.keys.sort
puts "#{k} floors: #{expected_best[k].inspect}"
end


num_floors = MAX_FLOORS
puts "===== For #{num_floors} floors, we expect an average of #{expected_best[num_floors][0]} drops ====="
effective_num_floors = num_floors
base_floor = 0
while true
drop_floor = base_floor + expected_best[effective_num_floors][:best_start_floor]
floors_above = num_floors - drop_floor
effective_floors_below = drop_floor - base_floor - 1

puts "Drop from floor #{drop_floor}"
puts " If it breaks there, you can expect #{expected_drops_with_final_egg(effective_floors_below)} more drops"

effective_num_floors = floors_above
base_floor = drop_floor

break if drop_floor >= num_floors - 1
end

Knight Tour - Yet Another Chess Problem

Source : Heard From My Friend Who Went to Crack Amazon

The Knight's Tour is a famous chess problem, in which a knight starts on the top-left square of an ordinary chessboard and then makes 63 moves, landing on every square of the chessboard exactly once (except for the starting square).

Can you complete the Knight's Tour? For a further challenge, can you find a "closed" solution, meaning that the knight can make a 64th move to land back on the starting square (thus making the solution circular)?





Solution
This pictures shows a non-cyclical solution. The strategy is to essentially cover the border (outer 3 rows/columns) first, and then cover the inner part of the board. We'll leave a cyclical solution as a challenge to the reader




More Info
http://en.wikipedia.org/wiki/Knight%27s_tour

Saturday, April 23, 2011

You need to check that your friend, Bob, has your correct phone number…Google Puzzle

You need to check that your friend, Bob, has your correct phone number…

but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?


Solution Started From Funniest Way to Deepest Thing of Computer Science

Funny Solutions

it is funny with all these technologies nowadays, I would opt for following as answer for 2.

Write on paper question ....."Bob Can you verify if you have my correct number without revealing to Eve and without talking to me in any of following methods?

1. E-mail me at abc@xyz.com

2. MMS me to my phone number that "If I get this MMS, then Bob has my correct number"

3. Go to my internet website account (facebook) OR even linked.com and write me a message for what number you have

4. Use communicator chat software or gtalk or yahoo messenger and ping me the number that you have

5. mathematically compute like checksum or decode and send me coded number with decoding steps. on paper back to Eve.


Computer Science Way of Thinking

Public key Cryptography
here is my public key, pls encrypt my phone you have with it and send back to me.
key=num-reveres of num

e.g if my no is 9740852296
the key=2818271817 eve can't read it as eva dopn't have my number so she can't predict & she has to lot of computation which only possible she know my number or some its digits ..so she can't decode the my key

(we can also extend the explanation so i write on the paper that bob i am sending you key to decode it reverse the key & then decode using logic you have so the same thing bob has to do in its side & same he write back to me..m not using this in this solution )

then bob decode it using computation he tries all the way +,-*,/, %,xor all possible way to decode if he has my correct phone number then suppose he try to subtract my key from my phone number he has so if has correct phone number then after subtracting the key from my number he will send 9740852296-2818271817=6922580476 & he also write that after decoding reverse it so i will get my original number e.g. 9740852296 so i can say bob has my correct phone number else it would have been some other value & after reversing it i wont get my exact no so i can say bob don't have my correct number..


Hurray i think i have done..Please Correct me if i am wrong

More Depth This Solution provide by Ankul

Click here



Ask Bob to Hash the phone number using a string hashing technique :
T[256] = permutation of 0...255
H[0] = 0
H[i] = T[ H[i-1] xor C[i] ]
H[n] is the final hash value

Since this hash function gives different hash values for permutations of same string, so a hash collision will not occur when two strings are permutation of each other.

This is a one-way hash function and cannot be decrypted back to the original phone number.

When I will get the hash key from Bob, I will find the hash value for my actual phone number and then match it with the hash key given by Bob.

Now, if hash values don't match, Bob has wrong phone number of mine.
Otherwise, there can be two cases :

1. He has correct phone number.
2. He has incorrect phone number but still gives same hash value (collision).

To decide between these two cases, I can ask Bob to also send me the frequency of each digit in the number that he has. This way, I will be able to decide if the two numbers are permutations of each other or not. If, the frequency of any of the digit in my actual number doesn't matches with the frequency given by him, that means the 2nd case is applicable, otherwise 1st case (phone numbers match) because a permutation of same string cannot give same hash value for this hash function.

Thus, I will ask Bob to send me the hash value and the frequency of each digit in his phone number. Eve has no way to find the phone number.

Cheers
WgpShashank

Monday, April 11, 2011

9 Digit Number Problem Every nth number formed by n digit is Divided By Every nth digit

Arrange the digits 0 to 9 such, that the number formed by the
first digit is divisible by 1, the number formed by the first two
digits is divisible by 2, that formed by the first three digits
divisible by 3, and so forth, thus the number formed by the first
9 digits will be divisible by 9 and that formed by all 10 digits
divisible by 10.

Here is what we would do.

_ _ _ _ _ _ _ _ _ _

those are my ten blanks.

Now let's start asking questions.

Since the whole thing has to be divisible by 10, the last number
must be a zero.

And since the first five digits must be divisible by 5, the fifth
digit must be a 5 or 0, but we have already used 0 so it must be a
five.

One last quickie is that the 2nd, 4th, 6th, and 8th and last
digits must be even, so all the rest are odd

So let's look at we have. I'll write the digits that could go in a
certain place under where they could go:


_ _ _ _ 5 _ _ _ _ 0
1 2 1 2 2 1 2 1
3 4 3 4 4 3 4 3
7 6 7 6 6 7 6 7
9 8 9 8 8 9 8 9

Now things get trickier.

Let's start with the 4th spot.

Any number is divisible by 4 if the last two digits are divisible
by 4

So what are the two-digit numbers divisible by 4 that begin with
an odd number that is not 5?

12 16 32 36 72 76 92 96

Hey, so the 4th digit is either a 2 or a 6.

Now, let's look at the 8th digit. If the first 8 digits are
divisible by 8, then they are divisible by 4 also. So if we apply
the same logic as above, we find that the 8th digit is either a 2 or
a 6.

So spaces 2 and 6 must be 4 or 8.

That narrows it down. So we have this:

_ _ _ _ 5 _ _ _ _ 0
1 4 1 2 4 1 2 1
3 8 3 6 8 3 6 3
7 7 7 7
9 9 9 9



Now for my next trick let's recall that every third space must be
divisible by 3. So every three numbers must sum to be divisible
by 3.

In particular spaces 4, 5, and 6 must sum to 3, and we already
have a five. So either we have

2 5 8 or 6 5 4

in positions 4, 5, and 6.

That is good stuff. That means we have either this:

_ 4 _ 2 5 8 _ 6 _ 0
1 1 1 1
3 3 3 3
7 7 7 7
9 9 9 9

or this:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 1 1
3 3 3 3
7 7 7 7
9 9 9 9

Let's check each of the four digits we could put in the 8th place.
Since a number is divisible by 8 if its last 3 digits are, we need
number in the 6th, 7th, and 8th places to be divisible by 8. We see
that 816 and 896 work in the first case, and 432 and 472 work in the
second case. So we have:

_ 4 _ 2 5 8 _ 6 _ 0
1 1 1 1
3 3 9 3
7 7 7
9 9 9

or this:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 3 1
3 3 7 3
7 7 7
9 9 9


Let's look at the 9th place now. Recall that 1+2+3+4+5+6+7+8+9 = 45,
so we don't need to worry about the 9th place - it will always work
out.

Let's look at the 1st and 3rd places. In case 1, only 147 and 741 are
options. In case 2, we could have 183, 189, 381, 387, 783, 789, 981, or
987. Note that 387 and 783 don't work, because then we don't have any
digits left for the 7th digit.

So our first case becomes:

_ 4 _ 2 5 8 9 6 3 0
1 1
7 7

We can just check the two numbers this can give rise to, namely 1472589630
and 7412589630. Since neither of them are divisible by 7, case one must be
a dead end. So we have to work with case two if we want a solution:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 3 1
3 3 7 3
7 7 7
9 9 9

(and the first 3 digits are 183, 189, 381, 789, 981, or 987)

If we look at the 7th, 8th, and 9th digits to see if we can get them to sum
to three, we see that only 321, 327, 723, and 729 are options.

So which of our options for digits 1,2,3 and 7,8,9 can we use together? In
order to not repeat digits, we could use these:

183 and 729
189 and 327
189 and 723
381 and 729
789 and 321
981 and 327
981 and 723
987 and 321

This means that the only possible solutions to the puzzle are these:

1836547290
1896543270
1896547230
3816547290
7896543210
9816543270
9816547230
9876543210

This is now a small enough number of cases that we can check them by hand.
The first thing we should do is check the first 7 digits for divisibility by
seven. Here are the results:

1836547/7 = 262363.857142857...
1896543/7 = 270934.714285714...
1896547/7 = 270935.285714286...
3816547/7 = 545221
7896543/7 = 1128077.57142857...
9816543/7 = 1402363.28571429...
9816547/7 = 1402363.85714286...
9876543/7 = 1410934.71428571...

Sunday, April 10, 2011

There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passen

There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passengers.



This is equal to 1-(probability that they all carry different number of passengers). That probability in paranthesis is equal to (m+1)!/((m+1-n)! * (m+1)^n). This is given that (m+1) >= n. If (m+1) < n, then the probability is 1.

- m+1 because maximum m passengers mean m+1 different possiblities (a bus could carry 0 passengers).
- The first bus has (m+1) possibilities in terms of number of passengers. The second has m+1, the third has m+1 and so on. Total number of orderings possible is (m+1) ^ n.
- For the number of passengers to be different in each bus, first bus has m+1 possibilities, second has m, third has m-1 nd so on. For n buses, this is equal to (m+1)!/(m+1-n)!. Dividing this by (m+1)/n gives the possibility. Subtract this number from one to find at least two buses with the same amount of passengers.


Solved by James

Tuesday, April 5, 2011

The Wire Identification Problem

There is a bunch of 120 electrical cables laid under the ground. The cables are 10 KM in length and both ends of each wire are out in open.




We need to identify and label the cables 1-120. All you have is a circuit completion detector bulb.(i.e. if you join same side ends of any two cables and then on the other side apply the bulb to corresponding 2 ends then bulb will light up, but to detect this way you have to make a 10 KM trip)

How would you identify each cable in minimum number of trips.

Solution

We need to identify and label the cables 1-120. As you might have guessed, the only way to gain information in this setup is to connect some set of wires at one end, walk up to the other end, and test for conductivity. The process may have to be repeated many times before a complete labeling can be constructed. And since each such step involves walking across 10 KM, we wish to solve the problem with the least number of trips.

How would you identify each cable in minimum number of trips?

Answer:
Boundary Condition: If we have just 2 wires, there’s really nothing we can use to break the symmetry of the situation.

Solution: At the first end, connect pairs of wires together, leaving two wires unconnected. Go to the other end. Find a pair of connected wires, andnumber them #2 and #3. Find another pair and label them #4 and #5. Repeat for all of the pairs, with the last pair labeled #118 and #119. There remain two wires that are not connected to each other. Label one of these #1 and the other #120.

Now at second end, connect #1 to #2, #3 to #4, etc, leaving #119 and 120 unconnected. Go back to the first end. One of the originally unconnected wires still is unconnected. Label it #120 and label the other originally connected wire #1. Now find the wire connected to #1 and label it #2. The wire that originally was connected with new wire #2 can be labeled #3. The wire that is now connected to the newly labeled #3 is #4. In this way, all of the wires can be identified on both ends in two trips (one round trip). If it is necessary to disconnect the connections at the other end, a third trip is necessary.

Below is an execution diagram for 6 wires. We have to label wires from 1-6.





Source

http://ashutoshmehra.net/blog/2009/09/wire-identification-problem/

Saturday, April 2, 2011

6 Riddles

QUESTIONS:

1) The Elder Twin
One day Kerry celebrated her birthday. Two days later her older twin brother, Terry, celebrated his birthday.
How could this happen?

2) Manhole Covers
Why is it better to have round manhole covers than square ones?

This is logical rather than lateral, but it is a good puzzle which can be solved by lateral thinking techniques. It is supposedly used by a very well-known software company as an interview question for prospective employees.

3) The Deadly Party
A man went to a party and drank some of the punch. He then left early. Everyone else at the party who drank the punch subsequently died of poisoning.
Why wasn't the first guy poisoned?

4) Heaven
A man died and went to Heaven. There were thousands of other people there. They were all naked and all looked as they died at the age of 21. He looked around to see if there was anyone he recognized. He saw a couple and he knew immediately that they were Adam and Eve.
How did he know?

5) Trouble with Sons
A woman had two sons who were born on the same hour of the same day of the same year. But they were not twins.
How could this be so?

6) The Man in the Bar
A man walks into a bar and asks the barman for a glass of water. The barman pulls out a gun and points it at the man. The man says `Thank you' and walks out.
Why?

This puzzle has claims to be the best of the genre. It is simple in its statement, absolutely baffling and yet with a completely satisfying solution. Most people struggle very hard to solve this one yet they like the answer when they hear it or have the satisfaction of figuring it out.





ANSWERS:

1) At the time she went into labor, the mother of the twins was traveling by boat. The older twin, Terry, was born first early on March 1st. The boat then crossed the International Date line (or anytime zone line) and Kerry, the younger twin, was born on February the 28th. In a leap year the younger twin celebrates her birthday two days before her older brother.

2) A square manhole cover can be turned and dropped down the diagonal of the manhole. A round manhole cannot be dropped down the manhole. So for safety and practicality, all manhole covers should be round.

3) The poison in the punch came from the ice cubes. When the man drank the punch the ice was fully frozen. Gradually it melted, poisoning the punch.

4) He recognized Adam and Eve as the only people without navels. Because they were not born of women, they had never had umbilical cords and therefore they never had navels.

This one seems perfectly logical but it can sometimes spark fierce theological arguments!

5) They were two of a set of triplets (or quadruplets etc.)

This simple little puzzle stumps many people. They try outlandish solutions involving test-tube babies or surrogate mothers. Why does the brain search for complex solutions when there is a much simpler one available?

6) The man had hiccups. The barman recognized this from his speech and drew the gun in order to give him a shock. It worked and cured the hiccups - so the man no longer needed the water.

The is a but a difficult one to solve. It is a perfect example of a seemingly irrational and incongruous situation having a simple and complete explanation. Amazingly this classic puzzle seems to work in different cultures and languages.

King Bear & Poison ..Very Common & Tough Puzzle

Problem : A king has a wine cellar with 100 drums of wine. A traitor sneaked into his wine cellar to poison the drums. He could mix poison in only one of the drums when guards caught him. However, guards could not see which one drum was poisoned. Our king being a drunkard wishes to be able to drink wine as soon as possible but safely. The poison guarantees that the person drinking the wine would die in 10 days.

Being a king, he can order his servants to drink wine from the drums to find out poisonous drum. However, he wishes does not want to risk lives of too many servants.

1) King wishes to be able to drink some wine on 11th day. How many servant would be needed to take the risk of drinking wine before figuring out a harmless wine drum?

2) King wishes to throw a grand party on 11th day. How many servant would be needed for figuring out the poisonous wine drum?

Solution :

The solution to the first problem is extremely simple and obvious. Only one servant need to drink any one of the wine drum. If the servant dies, all the other drums are harmless. If he does not die, we can guarantee that at least that one wine-drum is harmless.

Well, second problem has actually two sides to it. Say for example, king wishes that number of servant to be put on stake can be arbitrarily large, but the number of servant died during the process should be less. Then, we need 99 servant for each wine drum. At most one servant would die in this case.

However, what if we want to minimize the number of servants to be put on stake? Initially I went on a very wrong direction. That was to use prime factorization of every number from 1 to 100. For example, there will be a servant drinking from wine-drums which are numbered in multiple of 2, and similarly another servant for multiple of 5. So, we would be able to detect number 10 as the poisonous drum if both of them dies. Using this multiple scheme, number of servant needed would be

2,4,8,16,32,64

3,9,27,81

5,25

7,49

all primes number between 1 to 100 which has not appeared in the above list.
Basically, the number comes out to be huge. Certainly a very very bad solution.

A good solution would be to arrange wine-drums in 10×10 maze. We would need only 20 servant. 10 servant for the row and 10 for the column. So when in 10 days i-th servant for row and j-th servant for column dies, we would know that the drum located at (i,j) is the culprit. But still we are far from the best solution.

We can visualize the maze in three dimension. 5x5x5 would need only 15 servants. Of course, there would be some spots empty in the maze, but that does not matter.6x6x3 = 15. Going ahead we can have 5x5x4=14.

It seems we can still push it further. We can visualize the maze in four dimension. 4x3x3x3 = 13. This is the least possible number I could find. I don’t know whether we can push it still further down. If you can figure out a still smaller number, please comment on this post.


Soln By –Saurabh Joshi from his blog me.maths & puzzle
i found its interesting so i pasted here

Who Can Name the Bigger Number?

http://www.scottaaronson.com/writings/bignumbers.html

Friday, April 1, 2011

Another Hat Color Problem

The Island - One puzzle a day - Puzzle Buddies
100 men were captured and prisoned in an island.the island is guarded by a genie.
Everyday genie takes prisoners out.genie places them in a circle so that everyone can see each other,then all the prisoners are blindfolded. Genie then places hats on prisoners head,some of them are white and some of them are red.their folds will be opened after the genie places hats.

On genie's command the prisoners with white hat should step forward.They will be set free if only the men with white hat steps forward.
If any one without white hat steps forward,genie executes all of them
If no one steps forward,the same game will be repeated the next day,if the game is repeated,each prisoner will get the same hat that they got on the first day

Prisoners are not allowed to communicate with each prisoner.if communicated all of them will be executed.prisoners are not allowed to see the hat that they are wearing
At least one white hat is given, and all prisoners are aware of this.

how many days did it take for the prisoners to get out if genie gave "n" white hats where 1<=n<=100, and how did they do it?



Solution:
Let us say there is one white hat,the answer is simple.the prisoner wearing white hat sees no other white hat and he steps forward.
Now let us take two white hats.No body comes forward on the first day,because the prisoners wearing white hat sees one white hat.On the second day since no body has come forward they both know there must be two white hats and one he can see and other must be his own.so they come forward on second day.
Similarly if there are three white hats they will not come out on second day.it will take three days.
and so on..for "n" it will take n days

Monty Hall Problem

You are a contestant on a game show. You have three closed doors in front of you. One of the doors has a car behind it and the other two doors have nothing. You have to choose a door to open.

You have with you a Magic Watch.
- Whenever you ask the watch a question with a yes/no answer, it will blink either red or blue.
- One of the colors represents 'yes' and the other 'no'.
- You don't know which color means what. (gotcha!)
- You are allowed to ask the watch only 2 questions before you make your decision.

Which questions would you ask and how would you choose the door to open?

The puzzle might have a number of solutions and this is one of them.

Solution:

The contestant should ask the following two questions:
1) If I asked whether the car was behind door 1, would you blink red?
2) If I asked whether the car was behind door 2, would you blink red?

There are two cases here:
a) red = no, blue = yes:

The watch can answer in 4 different ways:
1) red, blue:
From the answer to the 1st question, car is behind door 1.
From the answer to the 2st question, car is not behind door 2.
2) blue, red:
From the answer to the 1st question, car is not behind door 1.
From the answer to the 2nd question, car is behind door 2.
3) blue, blue:
From the answer to the 1st question, car is not behind door 1.
From the answer to the 2nd question, car is not behind door 2.
4) red, red:
From the answer to the 1st question, car is behind door 1.
From the answer to the 2nd question, car is behind door 2.
b) red = yes, blue = no:

The watch can answer in 4 different ways:
1) red, blue:
From the answer to the 1st question, car is behind door 1.
From the answer to the 2st question, car is not behind door 2.
2) blue, red:
From the answer to the 1st question, car is not behind door 1.
From the answer to the 2nd question, car is behind door 2.
3) blue, blue:
From the answer to the 1st question, car is not behind door 1.
From the answer to the 2nd question, car is not behind door 2.
4) red, red:
From the answer to the 1st question, car is behind door 1.
From the answer to the 2nd question, car is behind door 2.

Observe that the conclusions are exactly the same for the same answer set irrespective of the color code.
Hence, when the watch answers:
1) red, blue: Pick door 1.
2) blue, red: Pick door 2.
3) blue, blue: Pick door 3.
4) red, red: This outcome is impossible since it implies that the car is behind door 1 as well as door 2.

How can you get a fair coin toss

Interview question: How can you get a fair coin toss if someone hands you a coin that is weighted to come up heads more often than tails?

The story of these types of questions starts at the software giant Microsoft who pioneered the use of puzzle type question, where the aim is to test the interviewers problem solving skills and creativity. It's ironic that these type of questions are no longer asked in Microsoft job interviews, but the rest of the software industry hasn't caught on.



The solution is to toss the coin twice, which gives four possible outcomes:
H (heads) followed by H, probability of this is pH * pH
H followed by T (tails), probability of this is pH * pT
T followed by H, probability of this is pT * pH
T followed by H, probability of this is pT * pT
Looking at the above outcomes we can see that HT (H followed by T) is just as likely as TH,
So to get a fain coin toss, toss the coins and use HT or TH as fair outcomes of the toss, and discard the results of TT and HH.

Another Hat Puzzle

I buried four fishermen up to their necks in the sand on the beach at low tide for keeping their fishing spot a secret from me. I put a hat on each of their heads and told them that one of them must shout out the correct color of their own hat or they will all be drowned by the incoming tide. I give them 10 minutes to do this. Fisherman A and B can only see the sand dune I erected. Fisherman C can see that fisherman B has a white hat on. Fisherman D can see that C has a black hat, and B has a white hat. The fisherman have been told that there are four hats, two white and two black, so they know that they must have either a white or a black hat on. who shouts out the color of their hat and how do they know?

Fisherman C shouts out.

Fishermen A and B are in the same situation - they have no information to help them determine their hat colour so they can’t answer. C and D realise this.

Fisherman D can see both B and C’s hats. If B and C had the same colour hat then this would let D know that he must have the other colour.

When the time is nearly up, or maybe before, C realises that D isn’t going to answer because he can’t. C realises that his hat must be different to B’s otherwise D would have answered. C therefore concludes that he has a black hat because he can see B’s white on