Brain Teasers

Here are some brain teasers problem from the book

You are trying to cook an egg for exactly fifteen minutes, but instead of a timer, you are given two ropes which burn for exactly 1 hour each. The ropes, however, are of uneven densities – i.e., half the rope length-wise might take only two minutes to burn.

So what we can get from the info. First we can time 1 hour with burning one rope. Can we time 30 mins? yes, we burn the rope from two ends. Our targets is to time 15 min, so we need a rope that can time 30 mins, then if we light the rope from both end, we have 15 mins. See the solution? we first light 1 rope from both end and 1 rope from 1 end, when the first rope finishes, we light the other end of the second rope, and start cooking. When the second rope finished, we have 15 mins.

1. Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8. You can use any parentheses you’d like.
if we can use parenthesis, (3+1) * 2 = 8, but how can we get 3 and 6 to 2? We know that 6/3 is 2, so we can use ((3+1)/3)*6 = 8

2. There is an 8×8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible).

Say we have black and white on a chess board, if we remove 2 on the diagonal, they must be with the same color, if you have a domino covering 2 connected squares, then they must be of different color. one black and one white. But there are 30 black and 32 whites on the chess board, so it is impossible.

3. You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water?
NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible.

We need 1 quart to get 4 quarts (either 5-1 or 3+1 can make 4 quarts). so we can do the following:
fill 5 quart jar
move 5 quart jar water to 3 quart, now 5 quart jar has 2 quarts water in it.
remove all the water from 3 quart jar, and move the 2 quart water from the 5 quart jar to 3 quart jar, now the 3 quart jar has 2 quarts water in it.
fill the 5 quart jar, and use the 5 quart jar to fill the 3 quart jar which already have 2 quarts water in it. Then what was left in the 5 quart jar will be 4 quarts of water

4.A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.

To solve this problem, the idea is try to start from the base case.
What if there is only one hat c == 1? the one with the hat on him will see no hat, (while the others will see 1 hat), because the there will be at least one hat, so the one sees no hat will know that the only hat is on his hat. so he will remove the hat on the first night.

What is c == 2? All the others will see 2 hats except those 2 with hat on their head, but they are not sure if there is only 1 hat or 2 hats in total. If there is only one hat, then the one with the hat will see no hats and thus would have remove the hat on the first night (case 1). So on the second day, if the two with the hat still sees the one hat, they will both know that he has one hat on their head. Then they will remove the hat on the second night.

What if c == 3? those with the head will see two hats, but they will not be able to tell if there are 2 hats or 3 hats. but after the second night, if there are only 2 hats, both of them will be removed, and if they see 2 hats on day 3, then those sees two hats will know that there are 3 hats in total and they have one hat on their head, and thus will remove the head on the third night.

then we can go on to any number of hats.

5. There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.

Lets take an example to look closer at the problem. say we try every 10 level, if the first egg break between 10 and 20, then we will need to try another 9 for step 11 to 19. which leads to total of 20 tries for two eggs. However if the first egg break at 100 level, then we have a total of 10+9 = 19 tries.

In the condition that we do not have an idea when the two eggs will break, we should break the tries evenly to get minimum number of tries. if we make fewer tries on the first jump, we need to have more tries for the second try. With more first tries, we need to reduce the number of second tries to balance the number of tries. so lets say we make first try of X floors for the first try, then we jump X -1 because we will have one less try for the second try. so we will have X + X-1 + X-2 + … + 1 = 100 => X = 14.

6.There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

When is a lock gets toggled? when there is a factor was hit, given an example of 12, it is toggled at 1, 2, 3, 4, 6, 12.

When a lock is open? when it was toggled odd time, which means it has an odd number of factors.

So what are the numbers that has an odd number of factors? only those that are the square of some number, 1, 4, 9 … 81, and 100. So there will be 10 locker left open at the end

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s