Determine winner of 2/9 number game

Two players play the following game: they pick a random number N (less than 2 billion) then, 
starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins. 
The candidate should write a function that given N decides who wins (first or second player)?

Three Doors, 1 Prize Puzzle , One of Toughest Puzzle on Probabality

You are on a gameshow and the host shows you three doors. Behind one door is a suitcase with $1 million in it, and behind the other two doors are sacks of coal. The host tells you to choose a door, and that the prize behind that door will be yours to keep.
You point to one of the three doors. The host says, "Before we open the door you pointed to, I am going to open one of the other doors." He points to one of the other doors, and it swings open, revealing a sack of coal behind it.
"Now I will give you a choice," the host tells you. "You can either stick with the door you originally chose, or you can choose to switch to the other unopened door."
Should you switch doors, stick with your original choice, or does it not matter?

Einstein's Riddle

ALBERT EINSTEIN'S RIDDLE ARE YOU IN THE TOP 2% OF INTELLIGENT PEOPLE IN THE WORLD? SOLVE THE RIDDLE AND FIND OUT.


There are no tricks, just pure logic, so good luck and don't give up.

1. In a street there are five houses, painted five different colors.

2. In each house lives a person of different nationality

3. These five homeowners each drink a different kind of beverage, smoke different brand of cigar and keep a different pet.  

THE QUESTION: WHO OWNS THE FISH?

HINTS

   1. The British man lives in a red house.
   2. The Swedish man keeps dogs as pets.
   3. The Danish man drinks tea.
   4. The Green house is next to, and on the left of the White house.
   5. The owner of the Green house drinks coffee.
   6. The person who smokes Pall Mall rears birds.
   7. The owner of the Yellow house smokes Dunhill.
   8. The man living in the center house drinks milk.
   9. The Norwegian lives in the first house.
   10. The man who smokes Blends lives next to the one who keeps cats.
   11. The man who keeps horses lives next to the man who smokes Dunhill.
   12. The man who smokes Blue Master drinks beer.
   13. The German smokes Prince.
   14. The Norwegian lives next to the blue house.
   15. The Blends smoker lives next to the one who drinks water.

ALBERT EINSTEIN WROTE THIS RIDDLE EARLY DURING THE 19th CENTURY. HE SAID THAT 98% OF THE WORLD POPULATION WOULD NOT BE ABLE TO SOLVE IT.  

Feel free to comment your answers and share to your friends.

Manager and Engineer Puzzle

The FBI has surrounded the headquarters of the Norne corporation. There are n people in the building. Each person is either an engineer or a manager. All computer files have been deleted, and all documents have been shredded by the managers. The problem confronting the FBI interrogation team is to separate the people into these two classes, so that all the managers can be locked up and all the engineers can be freed. Each of the n people knows the status of all the others. The interrogation consists entirely of asking person i if person j is an engineer or a manager. The engineers always tell the truth. What makes it hard is that the managers may not tell the truth. In fact, the managers are evil geniuses who are conspiring to confuse the interrogators.

1. Under the assumption that more than half of the people are engineers, can you find a strategy for the FBI to find one engineer with at most n-1 questions?
2. Is this possible in any number of questions if half the people are managers?
3. Once an engineer is found, he/she can classify everybody else. Is there a way to classify everybody in fewer questions?

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
   
   
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

Josephus Problem - Puzzle

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

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.

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.

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

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)

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

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...

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/

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

Weigh System With More Explaination..How Many Weight We Needs..???

Puzzle: You have a common balance with two sides. You can only keep weighs on one side. You have to weigh items from 1 to 1000 weight units with integral weights only.
What is the minimum number of weights required and what will be their weights?
Eg. With 2 weights one of 1 weight unit and other of 3 weight unit you can measure 1, 3 and 4 only.
Note: Don't forget to visit us again. Answer to the puzzle will be posted tomorrow. You can provide your answer in comments.

Solution: This puzzle is an easy puzzle as to make any odd number you need all other even numbers and one 1.
So only one odd number is needed to make all odd numbers. Now you are left with all even numbers. All even numbers are base 2 and thus can be though of as binary representation. To make 1000 you need at most 10 bits(1111101000). You can make any number below 1000 from these bits.
So the answer is 10 weights required. 1, 2, 4, 8,16, 32, 64, 128, 256, 512.

Puzzle: This is part 2 of puzzle posted Above. The puzzle is that you have to weigh 1 to 1000 using a common balance scale with minimum number of weighs. This time you can put wights on both sides.
You can check Part 1 of this puzzle How many weights? Puzzle Part 1.
Note: Don't forget to visit us again. Answer to the puzzle will be posted tomorrow with winner's name. You can provide your answer in comments.

Solution: The answer is series of base 3 i.e. 1, 3, 9, 27, 81, 243 and 729.
We can start from smallest number 1. To measure 1 we definitely need 1.
To measure 2 we need to look for highest number possible. We can measure 2 by using 3(3-1 = 2). So we need 1 and 3.
Now to measure 4 we can use 1 and 3 both (1+ 3). To measure 5 again we will look for highest possible number. 9 is highest possible number (9-4 = 5). We can measure up to 13 using these weights.

Continuing the same way we can deduce that a series of base 3 is required, thus 1, 3, 9, 27, 81, 243, 729.


Puzzle: This is the 3rd part of weighing puzzles. You can check Part 2 and Part 1.
You have to weigh 125 packets of sugar with first one weighing 1 lb, second 2 lb, third 3 lb and so on.You can only use one pan of the common balance for measurement for weighing sugar, the other pan has to be used for weights.
The weights have to put on to the balance and it takes time. Time taken to move weights is equal to the number of weights moved.
Eg. So if you are weighing 5 lb using 3lb and 2 lb weight then you have to lift both these weights one by one and thus it will take 2 unit time. If you have to measure only 3lbs it will take only 1 unit time. Now if we have to measure sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 lb, with 1 unit of time, we place 3 lb along with 1 lb and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4lb using weights 1 and 3 only.

Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.
Note: Don't forget to visit us again. Answer to the puzzle will be posted tomorrow with winner's name. You can provide your answer in comments.
Source: Classic Puzzles
Solution: Amazing explanation provided by Kasturi.
You will need the weights 1, 2, 4, 8, 16, 32 and 64 i.e. 7 weights. You can measure 125 packets in 125 movements. The strategy to be followed is this:
Put 1: measure 1, weights in pan 1

To measure further you need to use a new weight.
Put 2: measure 3, weights in pan 1,2
Remove 1: measure 2, weights in pan 2

Thus, by adding the next smallest weight to the pan i.e. 2, we can measure all weights below 4 in total 3 movements.

To measure further you need to use a new weight.
Put 4: measure 6, weights in pan 2,4
Remove 2: measure 4, weights in pan 4
Put 1: measure 5, weights in pan 1,4
Put 2: measure 7, weights in pan 1,2,4

Thus, by adding the next smallest weight to the pan i.e. 4, we can measure all weights below 8 in total 7 movements.

Following the same strategy, whenever we have measured all weights below n, add n and we can measure measure all the weights below 2n in 2n-1 movements.
Eventually, we can measure 125 packets in 125 movements.

Ten Pirates and their Gold

Ten pirates find a buried treasure of 100 pieces of gold.

The pirates have a strict ranking in their group: Pirate 1 is the lead pirate, Pirate 2 is second-in-command, Pirate 3 is the third most powerful pirate, and so on.

Based on this ranking, the pirates decide on a system to determine how to split up the 100 pieces of gold. The lead pirate (Pirate 1) will propose a way to divy it up. Then all the pirates (including the lead pirate) will vote on that proposal. If 50% or more of the pirates agree on the system, then that is how the gold will be divied up. However, if less than 50% of the pirates vote for the proposal, then the lead pirate will be be killed. The next-most powerful pirate will then become the lead pirate, and they'll restart the process (Pirate 2 will suggest a way to divy up the gold and it will be voted on by the rest of the pirates). This will keep going on until finally a proposal is agreed upon.

All of the pirates are very smart and very greedy. Each pirate will vote against a proposal if they know that they would end up with more gold if that proposal were to fail. A pirate also will never vote for a proposal that gives him 0 pieces of gold.

You are Pirate 1. You must come up with a proposal that will give you as much gold as possible, without getting yourself killed. Keep in mind that the rest of the pirates all know that if your proposal fails, then Pirate 2 will succeed at coming up with a plan that benefits him the most while not getting him killed.

What's your proposal?

Answer

You should keep 96 pieces of gold for yourself, and give 1 piece of gold each to Pirate 3, Pirate 5, Pirate 7, and Pirate 9.

To see why, let's look at the situation where there are only two pirates, and you're the lead pirate. Your proposal would be to give yourself all 100 pieces gold. Pirate 2 would vote against this and you would vote for it, giving you 50% of the vote and letting it pass. And you would get 100 pieces of gold.

What about for 3 pirates, with you as the lead pirate? Well, Pirates 2 and 3 know that if your proposal fails, then they will find themselves in the situation described above for 2 pirates, in which Pirate 2 will get all the gold, and Pirate 3 will get none. Pirate 2 would love this situation, but Pirate 3 would hate it. So you just propose to give Pirate 3 one piece of gold, while giving Pirate 2 no gold. Pirate 2 will vote against this, but Pirate 3 will vote for it because he knows that if this proposal fails, he'll get no gold. So your proposal will pass, you'll get 99 pieces of gold, and Pirate 3 gets 1 piece.

For 4 pirates, the situation is similar again. Pirates 2 and 4 would love your proposal to fail since they know that with only 3 pirates, they'll both get gold, whereas Pirate 3 will get none. So you just give Pirate 3 one piece of gold and keep the other 99 for yourself, and this proposal will hold up with 50% of the votes (from you and Pirate 3).

We can follow this same logic all the way up to 10 pirates, where you give one piece of gold each to Pirates 3, 5, 7, and 9, and keep the rest for yourself. You know these four pirates will support your proposal because they know they'll each get 0 pieces of gold if your proposal fails.