Easy | Strategy |

An Egg breaks only if dropped from above a threshold floor, within this 100 story building. Every time you drop the egg, it is counted an attempt. You are given two eggs, find an algorithm to deduce the threshold floor, with minimum number of attempts in worst case!

Hint

If we had only 1 egg, we would go linearly from 1 to 100. Having an extra egg gives an opportunity to jump (skip some floors from testing). When 1st egg breaks, second egg moves linearly. Think why first egg should not move in constant jumps, but rather decreasing jumps! This will give 14 steps in the worst case.

Answer

It can be done in 14 steps in the worst case.

Solution

A solution for minimum steps in worst case is the smallest integer greater than or equal to the positive solution of n(n+1)/2=100...which gives 14....

start at 14th floor, if egg breaks start linearly from 1, if it does not break drop the egg from 14+13 = 27th floor, and so on....

My friend was asked only one puzzle in his interview, "3 eggs". He got the job.

start at 14th floor, if egg breaks start linearly from 1, if it does not break drop the egg from 14+13 = 27th floor, and so on....

My friend was asked only one puzzle in his interview, "3 eggs". He got the job.

Source: Quant Interview

Enable Like and Comment Easy | Strategy |

A certain town comprises of 100 married couples. Some husbands secretly cheat on their wives. All wives know about the nature of every husband except their own. When a wife concludes that her husband cheated, she kicks her husband into the street at midnight. All husbands remain silent about their secret. One day, the mayor of the town announces to the whole town that there is at least 1 cheating husband in the town. After announcement, no one talks, waiting for someone to get kicked. Till 9th night from announcement, no husband was kicked, but on the 10th night, some husbands got kicked out simultaneously. How many are they?

Hint

What happens if only one husband cheated?

Solution

It must be 10 husbands kicked out.

If there was only 1 cheating husband in the town, there will be 99 women who know exactly who the cheater is. The 1 remaining woman, who is being cheated on, would have assumed there are no cheaters. But now that the mayor has confirmed that there is at least one cheater, she realizes that her own husband must be cheating on her. So her husband gets kicked on the day of the announcement.

Now let’s assume there are 2 cheaters in the town. There will be 98 women in the town who know who the 2 cheaters are. The 2 wives, who are being cheated on, would think that there is only 1 cheater in the town. Since neither of these 2 women know that their husbands are cheaters, they both do not report their husbands in on the day of the announcement. The next day, when the 2 women see that no husband was kicked, they realize that there could only be one explanation – both their husbands are cheaters. Thus, on the second day, 2 husbands are kicked.

Through induction, it can be proved that when this logic is applied to n cheating husbands, they are all kicked on the n th day after the mayor’s announcement. Hence it must be 10 husbands kicked in our case.

If there was only 1 cheating husband in the town, there will be 99 women who know exactly who the cheater is. The 1 remaining woman, who is being cheated on, would have assumed there are no cheaters. But now that the mayor has confirmed that there is at least one cheater, she realizes that her own husband must be cheating on her. So her husband gets kicked on the day of the announcement.

Now let’s assume there are 2 cheaters in the town. There will be 98 women in the town who know who the 2 cheaters are. The 2 wives, who are being cheated on, would think that there is only 1 cheater in the town. Since neither of these 2 women know that their husbands are cheaters, they both do not report their husbands in on the day of the announcement. The next day, when the 2 women see that no husband was kicked, they realize that there could only be one explanation – both their husbands are cheaters. Thus, on the second day, 2 husbands are kicked.

Through induction, it can be proved that when this logic is applied to n cheating husbands, they are all kicked on the n th day after the mayor’s announcement. Hence it must be 10 husbands kicked in our case.

Source: Common

Enable Like and Comment Easy | Strategy |

So there's this king. Someone breaks into his wine cellar where he stores 1000 bottles of wine. This person proceeds to poison one of the 1000 bottles, but gets away too quickly for the king's guard to see which one he poisoned or to catch him.

The king needs the remaining 999 safe bottles for his party in 4 weeks. The king has 10 prisoners who deserve execution. The poison takes about 3 weeks to take effect, and any amount of it will kill whoever drinks it. How can he figure out which bottle was poisoned in time for the party?

The king needs the remaining 999 safe bottles for his party in 4 weeks. The king has 10 prisoners who deserve execution. The poison takes about 3 weeks to take effect, and any amount of it will kill whoever drinks it. How can he figure out which bottle was poisoned in time for the party?

Hint

Convert to binary strings?

Solution

The king has to mix wine in order to isolate the single poisoned one. 2) There are 10 servants. After about 3 weeks, each one can be either dead or alive, meaning that there are 2^10 = 1024 possible outcomes. Since 1024 > 1000, it's actually possible for some scheme to work.

Here's the scheme: The king assigns each servant a number from 1-10. The king assigns each bottle a number from 0-999. When he labels them, though, he writes the number on the bottle in binary with ten digits, like this: 0: 000000000 1: 000000001 2: 000000010 3: 000000011 4: 000000100 5: 000000101 ... 999: 1111100111 and so on.

Now the strategy is simple: Pick bottle 1, write its binary form, look at the positions where '1' appears (here: 1st only). Make the corresponding prisoner drink small quantitiy of that wine. (ie prisoner 1 takes a sip of wine #1). Continue this process upto 1000th wine. After 3 weeks, suppose only prisoner number 4 & 7 die. This means the binary representation of poisoned wine has '1' at position 4 & 7, and rest all zeros. Convert this binary number to decimal and that gives the poisoned wine.

Here's the scheme: The king assigns each servant a number from 1-10. The king assigns each bottle a number from 0-999. When he labels them, though, he writes the number on the bottle in binary with ten digits, like this: 0: 000000000 1: 000000001 2: 000000010 3: 000000011 4: 000000100 5: 000000101 ... 999: 1111100111 and so on.

Now the strategy is simple: Pick bottle 1, write its binary form, look at the positions where '1' appears (here: 1st only). Make the corresponding prisoner drink small quantitiy of that wine. (ie prisoner 1 takes a sip of wine #1). Continue this process upto 1000th wine. After 3 weeks, suppose only prisoner number 4 & 7 die. This means the binary representation of poisoned wine has '1' at position 4 & 7, and rest all zeros. Convert this binary number to decimal and that gives the poisoned wine.

Source: Common

Enable Like and Comment Medium | Strategy |

Suppose you have a hotel which has one floor with infinite number of rooms in a row and all of them are occupied.

1) A new customer wants to check in, how will you accommodate her?

2) What if infinite number of people want to check in, how will you accommodate them?

3) Suppose infinite number of buses arrive at the hotel, each having infinite number of people, how will you accommodate them?

1) A new customer wants to check in, how will you accommodate her?

2) What if infinite number of people want to check in, how will you accommodate them?

3) Suppose infinite number of buses arrive at the hotel, each having infinite number of people, how will you accommodate them?

Hint

Define Infinity ;)

Solution

1) Since there are infinite number of rooms and infinite+1= infinite

Just ask person in room k to move to k+1, thus making the first room vacant. :)

2) In the other case, since infinite+infinite = infinite

asking person in room k to move to 2k solves the problem.

3) Since NxN is countable set. We can get a 1-1 mapping from N to NxN

Hence, we can accommodate (infinite people X infinite buses) in the hotel.

Relevant article:

http://en.wikipedia.org/wiki/Cantor_pairing_function

Just ask person in room k to move to k+1, thus making the first room vacant. :)

2) In the other case, since infinite+infinite = infinite

asking person in room k to move to 2k solves the problem.

3) Since NxN is countable set. We can get a 1-1 mapping from N to NxN

Hence, we can accommodate (infinite people X infinite buses) in the hotel.

Relevant article:

http://en.wikipedia.org/wiki/Cantor_pairing_function

Source: CSEblog

Enable Like and Comment Medium | Strategy |

After the revolution, each of the 66 citizens of a certain city, including the king, has a salary of 1. King cannot vote, but has the power to suggest changes - namely, redistribution of salaries. Each person's salary must be a whole number of dollars, and the salaries must sum to 66. He suggests a new salary plan for every person including himelf in front of the city. Citizens are greedy, and vote yes if their salary is raised, no if decreased, and don't vote otherwise. The suggested plan will be implemented if the number of "yes" votes are more than "no" votes. The king is both, selfish and clever. He proposes a series of such plans. What is the maximum salary he can obtain for himself?

Hint

notice: (1) that the king must temporarily give up his own salary to get things started, and (2) that the game is to reduce the number of salaried citizens at each stage.

Answer

63

Solution

Continuing from hint, The king begins by proposing that 33 citizens have their salaries doubled to $2, at the expense of the remaining 33 (himself included). Next, he increases the salaries of 17 of the 33 salaried voters (to $3 or $4) while reducing the remaining 16 to $0. In successive turns, the number of salaried voters falls to 9, 5, 3, and 2. Finally, the king bribes three paupers with $1 each to help him turn over the two big salaries to himself, thus finishing with a royal salary of $63. It is not difficult to see that the king can do no better at any stage than to reduce the number of salaried voters to just over half the previous number; in particular, he can never achieve a unique salaried voter. Thus, he can do no better than $63 for himself, and the six rounds above are optimal

Source: P. Winkler

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |