Gold bar with 7 segments

You’ve got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

Break the 7 piece gold bar to make a piece of 1 segment size and the other of 2 segments size.( the remaining 4 segments intact)

i.e 7= 1 + 2 + 4 (only two breaks needed)

1- 1st day

2- 2nd day

(1+2) - 3rd day

4 - 4th day

(4+1) - 5th day

(4+2) - 6th day

(4+2+1) - 7th day.

Pick a Random Byte

Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.

Answer: Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it?

Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time.

When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.

Just generalizing, when we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.

Sometimes, this question is a little confusing. The question said you have only space to store one byte but there is an assumption that you have space to store variables to track the number of bytes and so on. Another assumption is that the stream of bytes is not infinite. If not, we won’t be able to calculate (n-1)/n.

If you have suggestions or comments, they are always welcome.

Three Switches

Question: You are standing outside a room next to three switches, all of which are off. Each switch operates a different light bulb in the room. The room door is closed, so you cannot see which switch operates which bulb. You are only allowed to go into the room once. Determine which switch operates which bulb.

Answer: Stumped? The issue lies in the fact that there are only two possible positions for each switch (on or off), but three bulbs to identify. Identifying one bulb is super easy, just set one switch on and then go into the room to check which one is on. But then, how do we detect the other two?

So let’s think deeper, what are the other properties of a light bulb operated by a switch? Light bulbs definitely produce light, but they also produce heat (a not so very important characteristic!). Any chance we can use this idea to help solve our problem? Since a light bulb would take sometime to lose its heat after being switched off, you could still determine if it had ever been on by touching it.

So now, we can easily determine which bulb is operated by which switch. First, we turn the first switch on and leave the other two off. After 5 minutes, we turn the first switch off, turn the second switch on and leave the third switch off. Then we go into the room and touch one of the bulbs which is turned off. After that, it would be easy to tell that the first switch matches the warm bulb, the second switch matches the bulb thats turned on and the third switch matches the colder bulb.

Flipping Coins on the table

There are twenty coins sitting on the table, ten are currently heads and tens are currently tails. You are sitting at the table with a blindfold and gloves on. You are able to feel where the coins are, but are unable to see or feel if they heads or tails. You must create two sets of coins. Each set must have the same number of heads and tails as the other group. You can only move or flip the coins, you are unable to determine their current state. How do you create two even groups of coins with the same number of heads and tails in each group?

Answer: Create two sets of ten coins. Flip The coins in one of the sets over, and leave the coins in the other set alone. The first set of ten coins will have the same number of heads and tails as the other set of ten coins.

Reaching the door of Heaven

A person dies, and he arrives at the gate to heaven. There are three doors in the heaven. one of them leads to heaven. another one leads to a 1-day stay at hell, and then back to the gate, and the other leads to a 2-day stay at hell, and then back to the gate. every time the person is back at the gate, the three doors are reshuffled. How long will it take the person to reach heaven?

this is a probability question - i.e. it is solvable and has nothing to do with religion, being sneaky, or how au dente the pasta might be ;-)

Answer:

1/3 of the time, the door to heaven will be chosen, so 1/3 of the time it will take zero days. 1/3 of the time, the 1-day door is chosen; of those, the right door will be chosen the next day, so 1/9 trips take 1 day. Similarly, 1/9 will take two days (choosing the 2-day door, then the right door).

After that, the cases split again, and again, and again. I can’t seem to make a nice infinite sum this way, so let’s try again.

Suppose the average days spent is X. 1/3 of the cases are done in zero days as before. 1/3 of the cases are 1 day plus X. 1/3 are 2 + X. So:

X = 1/3 * 0 + 1/3 * (1 + X) + 1/3 * (2 + X)

  = 0 + 1/3 + X/3 + 2/3 + X/3

  = 1 + 2X/3

Therefore,

  X/3 = 1

    X = 3

On average, it takes three days to get to heaven. Two if the noodles are limp.

Took me one blind alley, and about five minutes.

Can you properly the hotel charges?

Three people check into a hotel. They pay $30 to the manager, and go to their room. The manager finds out that the room rate is $25 and gives $5 to the bellboy to return. On the way to the room the bellboy reasons that $5 would be difficult to share among three people so he pockets $2 and gives $1 to each person. Now each person paid $10 and got back $1. So they paid $9 each, totaling $27. The bellboy has $2, totaling $29. Where is the remaining dollar ? 

 

Solution: True its just a slip of tongue. 3 rooms money paid = $27 = Manager $25 + bellboy $2. Plus $1 to each of them.

Passengers and Random Seats

100 passengers are boarding an airplane with 100 seats.
Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order.
However, the first passenger lost his ticket so he just took a random seat.
For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat.
What's the probability that the last passenger would sit on his own seat ?

Solution:
Let us say that everyone is sitting except for the 100th passenger. Consider where can he sit - he can sit in either seat numbered 100 or 1. There cannot be any other seat vacant for him.
We can prove this using contradiction. Lets say that a seat numbered n=55 is vacant for 100th passenger. Since passenger 55 came earlier he should be sitting in his seat if its vacant. So seat 55 cant be vacant. This logic can be applied to all seats except for seat 1 and 100.
So all permutations of the seating arrangement would result in last person sitting in either seat 1 or seat 100. Both the options are equally likely.
So answer = 1/2.

Fint out the matching socks

Michael have ten pairs of black socks, eight pairs of white socks and seven pairs of green socks. Everything is mixed in a draw. As there is no light he were not able to identify the color of the socks. How many of the socks did he want to take to match one pair ?

Solution:

The answer is 4 since in worst case all 3 socks taken first will be different color then the 4th one would be repetition. However if we consider a left sock to be different from right one, then at least 10 + 8 + 7 + 1 = 26 socks are needed.

How many races required?

You have 25 horses and 5 tracks and you need to find out top 3 horses. What is the minimum number of races required to do this ?


Solution:


For 1st question:
Group 25 horses in 5 groups:

A : A1, A2, A3, A4, A5 [Decreasing order of speeds]

B : B1, B2, B3, B4, B5

C : C1, C2, C3, C4, C5

D : D1, D2, D3, D4, D5

E : E1, E2, E3, E4, E5

Five races will have to take place for ranking in groups themselves.

One race for A1, B1, C1, D1, E1 for ranking of the groups.

Now A1>B1>C1>D1>E1

So A1 is the topper. We now need to find 2 more horses for 2nd and 3rd position.

Here is the key observation.

Selection by Elimination  [We need to find 2 more horses, if any horse is slower than 2 horses except A1 then it can not be included in the solution]

1. D1 and E1 can not be included in the solution as both of them are slower than B1 and C1

and hence their whole group is eliminated as they were best from their groups.

2. A4, A5 can not be included in the solution as they are slower than A2 and A3.
3. B3, B4, B5 can not be included in the solution as they are slower than B1 and B2.

4. C2, C3, C4, C5 can not be included in the solution as they are slower than C1 which is slower than B1 itself.

So we are now having only 5 possible horses for 2 positions which can be found out in just one race. [A2, A3, B1, B2, C1] Top 2 of this group will be ranked 2nd and 3rd after A1.

4 Quarts of Water

Question: If you had an infinite supply of water and a 5 quart and 3 quart pails, how would you measure exactly 4 quarts? and What is the least number of steps you need?

Answer: This question is very simple actually. Since we can’t hold 4 quarts in the 3 quart pail, we have to look to filling up the 5 quart pail with exactly 4 quarts. Lets count the steps as we move along

Answer: This question is very simple actually. Since we can’t hold 4 quarts in the 3 quart pail, we have to look to filling up the 5 quart pail with exactly 4 quarts. Lets count the steps as we move along
1. Fill 3 quart pail ( 5p – 0, 3p – 3)
2. Transfer to 5 quart pail (5p – 3, 3p – 0)
3. Fill 3 quart pail ( 5p – 3, 3p – 3)
4. Transfer to 5 quart pail (5p – 5, 3p – 1)
5. Empty 5 quart pail (5p – 0, 3p – 1)
6. Transfer to 5 quart pail (5p – 1, 3p – 0)
7. Fill 3 quart pail ( 5p – 1, 3p – 3)
8. Transfer to 5 quart pail (5p – 4, 3p – 0) We are done!!!

Four People on a Rickety Bridge

Question: Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?
Answer: The initial solution most people will think of is to use the fastest person as an usher to guide everyone across. How long would that take? 10 + 1 + 7 + 1 + 2 = 21 mins. Is that it? No. That would make this question too simple even as a warm up question.
Let’s brainstorm a little further. To reduce the amount of time, we should find a way for 10 and 7 to go together. If they cross together, then we need one of them to come back to get the others. That would not be ideal. How do we get around that? Maybe we can have 1 waiting on the other side to bring the torch back. Ahaa, we are getting closer. The fastest way to get 1 across and be back is to use 2 to usher 1 across. So let’s put all this together.
1 and 2 go cross
2 comes back
7 and 10 go across
1 comes back
1 and 2 go across (done)
Total time = 2 + 2 + 10 + 1 + 2 = 17 mins

Globe Walker

Question:
How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started?

Answer: The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again!

Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile. So what if we were standing at any point one mile north of this ring? If we walked one mile south, we would be on the ring. Then one mile east would bring us back to same point on the ring (since it’s circumference is one mile). One mile north from that point would bring us back to the point were we started from. If we count, there would be an infinite number of points north of this one mile ring.
So what’s our running total of possible points? We have 1 + infinite points. But we’re not done yet!
Consider a ring that is half a mile in circumference near the South Pole. Walking a mile along this ring would cause us to circle twice, but still bring us to back to the point we started from. As a result, starting from a point that is one mile north of a half mile ring would also be valid. Similarly, for any positive integer n, there is a circle with radius

r = 1 / (2 * pi * n)

centered at the South Pole. Walking one mile along these rings would cause us to circle n times and return to the same point as we started. There are infinite possible values for n. Furthermore, there are infinite ways of determining a starting point that is one mile north of these n rings, thus giving us (infinity * infinity) possible points that satisfy the required condition.
So the real answer to this question is 1 + infinity * infinity = infinite possible points!

Trains and Birds

: A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again, and so forth. The bird continues to do this until the trains collide. How far would the bird have traveled in the meantime?
Answer: Yes, you read it right. The bird is actually the fastest moving object in the problem!
Knowing that the bird is the faster than both the trains, you would only imagine that theoretically, the bird could fly an infinite number of times between the trains before they collide. This is because you know that no matter how close the trains get, the bird will always complete its trip before the crash happens. At the time of the crash, the bird would probably get squashed between the trains!
I bet sometime in school, you learnt how to sum up an infinite series. But do we have to do that?
The concept of relative speed (rings a bell?) can work handy here. Let’s assume that the distance between City X and City Y is d miles. The trains are approaching each other at a relative speed of (20 + 15) = 35 mph. The sum of the distances covered by the trains when they collide is d (i.e. the distance between the cities). Since distance/speed gives us time, we know that the trains collide d/35 hours after they start.
Since the speed of the bird is constant at 25 mph, we know that the bird would have covered

25 * (d/35) miles = 5d/7 miles

before the trains collide

Gold for 7 days of work

Question: You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)
Answer: The trick is not to try and how to cut in such a way to make 7 equal pieces but rather to make transactions with the worker. Make two cuts on the gold bar such that you have the following sizes of bars.
1/7, 2/7 and 4/7. For convenience sake, I would just refer to the bars as 1, 2 and 4.
At the end of Day 1: Give Bar 1 (You- 2 and 4, Worker- 1)
At the end of Day 2: Give Bar 2, Take back Bar 1 (You- 1 and 4, Worker- 2)
At the end of Day 3: Give Bar 1 (You- 4, Worker- 1 and 2)
At the end of Day 4: Give Bar 4, Take back Bar 1 and Bar 2 (You- 1 and 2, Worker- 4)
At the end of Day 5: Give Bar 1 (You- 2, Worker- 1 and 4)
At the end of Day 6: Give Bar 2, Take back Bar 1 (You- 1, Worker- 2 and 4)
At the end of Day 7: Give Bar 1 (You- Empty, Worker- 1, 2 and 4)
That should take care of everything.

The Ant Collision Problem

Question: Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide?

Answer: So let’s think this through. The ants can only avoid a collision if they all decide to move in the same direction (either clockwise or anti-clockwise). If the ants do not pick the same direction, there will definitely be a collision. Each ant has the option to either move clockwise or anti-clockwise. There is a one in two chance that an ant decides to pick a particular direction. Using simple probability calculations, we can determine the probability of no collision.
P(No collision) = P(All ants go in a clockwise direction) + P( All ants go in an anti-clockwise direction) = 0.5 * 0.5 * 0.5 + 0.5 * 0.5 * 0.5 = 0.25




To put this in other way :
Any ant can go clockwise or anti clockwise, so they are mutually exclusive events, so total probability = 2 ^ 3 = 8. There are 2 cases - either all ant go clockwise or they go anticlockwise....then there will be no collision, so P(No collision) = 2 / 8 = 0.25

Is Your Husband a Cheat?

Question: A certain town comprises of 100 married couples. Everyone in the town lives by the following rule: If a husband cheats on his wife, the husband is executed as soon as his wife finds out about him. All the women in the town only gossip about the husbands of other women. No woman ever tells another woman if her husband is cheating on her.  So every woman in the town knows about all the cheating husbands in the town except her own. It can also be assumed that a husband remains silent about his infidelity. One day, the mayor of the town announces to the whole town that there is at least 1 cheating husband in the town. What do you think happens?
Answer: Stumped? Let’s solve this methodically. Say 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 executed 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 executed, they realize that there could only be one explanation – both their husbands are cheaters. Thus, on the second day, 2 husbands are executed.
Through induction, it can be proved that when this logic is applied to n cheating husbands, they all die on the n th day after the mayor’s announcement.

50 trucks with payload

Question: Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.

We want to use as little fuel as possible so we try minimize the number of trucks we use as we go along. Let’s say we start with all 50 trucks with full fuel (5000 miles range). For each mile, we lose 50 miles in range. After two miles, we lose 100 miles leaving us with 4900 miles. This can be supported by 49 trucks so we drop one truck.
As you can see for every 100 miles we lose in range, we drop a truck.
50 trucks: 100/50
49 trucks: 100/49
…
Total distance = 100/50 + 100/49 + 100/48 + … + 100/2 + 100/1 (harmonic series) = 449.920533833

Camel and Banana

Question: The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.

What is the largest number of bananas that can be delivered to the market?

A camel cannot go  to market directly. This is because the camel can never travel more than 500 kilometres into the desert if it should return to the plantation (the camel eats a banana every kilometre it travels!). So there lies point A somewhere in the desert between the plantation and the market such that it returns back and pick up banannas:
<---p1---><--------p2-----><-----p3---->
P---------------------------------------->M

P (plantation)

===forth===> <===back==== ===forth===> <===back==== ===forth===>

A

===forth===> <===back==== ===forth===>

B

===forth===>

M (market)

 Since there are 3000 bananas and camel can only carry 1000 bananas, Camel will have to make 3 trips to carry them all to any point in between.


When bananas are reduced to 2000 then Camel can shift them to another point in 2 trips and when the number of bananas left are <= 1000, then he should not return and only move forward.

In the first part, P1, to shift the bananas by 1Km Camel will have to

1. Move forward with 1000 bananas – Will eat up 1 banana in the way forward
2. Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back
3. Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward
4. Leave 998 banana after 1 km and return with 1 banana - will eat up 1 banana in the way back
5. Will carry the last 1000 bananas from point a and move forward – will eat up 1 banana

Note: After point 5 the camel does not need to return to point A again.

At KM#0, we have 3000 bananas. The maximum bananas the camel can carry is 1000 so the camel must at least make 3 trips from the start point. (Leave #0, Return to #0, Leave #0, Return to #0, Leave #0).
If we move just 1km, we need 1 banana for each step mentioned above thus making a total of 5 bananas for each km.
So to shift 3000 bananas by 1km Camel will eat up 5 bananas.

After moving to 200 km the camel would have eaten up 1000 bananas and is now left with 2000 bananas.

Hence the length of part P1 is 200 Km.

Now in the Part P2, the Camel need to do the following to shift the Bananas by 1km.

1. Move forward with 1000 bananas - Will eat up 1 banana in the way forward
2. Leave 998 banana after 1 km and return with 1 banana - will eat up this 1 banana in the way back
3. Pick up the next 1000 bananas and move forward - Will eat up 1 banana in the way forward

Note: After point 3 the camel does not need to return to the starting point of P2.
At #200km, we will have 2000 bananas
At this point, we only need to make 2 trips (Leave #200, Return to #200, Leave #200). This will cost 1 banana for each step thus making a total of 3 bananas for each km.

So to shift 2000 bananas by 1km Camel will eat up 3 bananas.

After moving to 333 km the camel would have eaten up 1000 bananas and is now left with the last 1000 bananas.

The camel will actually be able to cover 333.33 km, I have ignored the decimal part because it will not make a difference in this example.

Hence the length of part P2 is 333 Km.

Now, for the last part, P3, the Camel only has to move forward. He has already covered 533 (200+333) out of 1000 km in Parts P1 & P2. Now he has to cover only 467 km and he has 1000 bananas.

He will eat up 467 bananas on the way forward, and at point B the Camel will be left with only 533 Bananas. 

Red, Green and Yellow Balls - heavy and light

Question
You are give two red balls, two green balls and two yellow balls. One ball from each color is heavier than the other one. All the heavier balls weigh the same and all the lighter balls weigh the same. You are only provided with a weighing balance. How many tries would it take to identify which one is heavier and which one is lighter?
Answer: Let’s label the balls R1, R2 (Red ones), G1, G2 (Green ones) and Y1, Y2 (Yellow ones).

Step 1
First weigh R1, G1 on one side and R2, Y1 on the other.

Scenario 1 - they balance out equal
If they are equal, we know that one of G1 or Y1 is heavy. We can just weigh them both (G1 and Y1) and find out which one is heavier. If G1 is heavy, the heavier set is {G1, R2, Y2} and the others are lighter. If Y1 is heavy, the heavier set is {G2, R1, Y1}.

Scenario 2
If R1, G1 is heavy, we know that either G1 is heavy or Y1 is light. We proceed to weigh G1, Y1 with G2, Y2. If they are equal, G1 is the heavy one. The heavier set is {G1, Y2, R1}. If G1, Y1 is heavy, G1 and Y1 are both heavy. The heavier set is {Y1, G1, R1}. If G2, Y2 is heavy, G2 and Y2 are both heavy. The heavier set is {R1, G2, Y2}.

Scenario 3
If R2, Y1 is heavy, we know that either Y1 is heavy or G1 is light. This is similar to the case above. Try to work it out yourself before continuing with the solution. Weigh G1, Y1 with G2, Y2. If they are equal, Y1 is heavy. The heavier set is {Y1, R2, G2}. If G1, Y1 is heavy, G1 and Y1 are both heavy. The heavier set is {G1, Y1, R2}. If G2, Y2 is heavier, G2 and Y2 are both heavy. The heavier set is {G2, Y2, R2}.
Therefore, in any of these cases, we only need two tries with the balance.

A box of defective ball

Question: 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?

Answer: For convenience sake, let’s name the boxes from 1 to 10.
In order to solve this problem, you have to leverage the fact that you know exactly what each good ball is supposed to weigh and what each defective ball is supposed to weigh. Many of us instinctively will take one ball out of each box and try to find a way to make it work but the trick to take different number of balls from each box.
The number of balls you pick from each bag is equal to the box number. For example, pick 1 ball from box 1, 2 balls from box 2 and so on. In total you will have 55 balls. If all of the boxes have good balls, then the total weight of these balls would be 550gm.
If box 1 has defective balls, then the total weight should be 1gm less than expected (only one ball weighing 9 gm). If box 2 has defective balls, then the total weight should be 2gm less than expected (two balls weighing 9 gm). So once you weigh the set of chosen balls, find out the difference between the total weight and the expected weight. That number represents the box number which contains the defective balls.
If you like puzzles with balls and balances, you might like 8 Identical balls problem

12 identical balls problem, one being different (heavier or lighter)

Question: You are give 12 identical looking balls. One of them is fake (could be heavier or lighter) than the rest of the 11 (all the others weight exactly the same). You a provided with a simple mechanical balance and you are restricted to only 3 uses. Find the fake ball.

Answer: For convenience sake, let’s name the balls 1-12. This question is quite tricky. If you want to warm up your skills, you can try this easier 8 ball problem first.
Ok, let’s get on with it.

Step 1
First we weigh {1,2,3,4} on the left and {5,6,7,8} on the right. There are three scenarios which can arise from this.

Scenario 1 - If they balance
Step 2
If they balance, then we know 9, 10, 11 or 12 is fake. Weigh {8, 9} and {10, 11} (Note: 8 is surely not fake)
balance - If they balance, we know 12 is the fake one. Just weigh it with any other ball and figure out if it is lighter or heavier.
Step 3 
If {8, 9} is heavier, then either 9 is heavy or 10 is light or 11 is light. Weigh {10} and {11}. If they balance, 9 is fake (heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {8, 9} is lighter, then either 9 is light or 10 is heavy or 11 is heavy. Weigh {10} and {11}. If they balance, 9 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
Phwww, that was confusing enough but we are not done yet.

Scenario 2 -  {1,2,3,4} is heavier

If {1,2,3,4} is heavier, we know either one of {1,2,3,4} heavier or one of {5,6,7,8} is lighter but it is guarantees that {9,10,11,12} are not fake. This is where it gets really tricky, watch carefully.
Step 2
Weigh {1,2,5} and {3,6,9} (Note: 9 is surely not fake).
Step 3
If they balance, then either 4 is heavy or 7 is light or 8 is light. Following the last step from the previous case, we weigh {7} and {8}. If they balance, 4 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {1,2,5} is heavier, then either 1 is heavy or 2 is heavy or 6 is light. Weigh {1} and {2}. If they balance, 6 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {3,6,9} is heavier, then either 3 is heavy or 5 is light. Weigh {5} and {9}. They won’t balance. If {5} is lighter, 5 is fake (lighter). If they balance, 3 is fake (heavier).

Scenario 3 -  {5,6,7,8} is heavier

If {5,6,7,8} is heavier, it is the same situation as if {1,2,3,4} was heavier. Just perform the same steps using 5,6,7 and 8. Unless maybe you are too lazy to try and reprocess the steps, then you continue reading the solution. Weigh {5,6,1} and {7,2,9} (Note: 9 is surely not fake).
If they balance, then either 8 is heavy or 3 is light or 4 is light. Following the last step from the previous case, we weigh {3} and {4}. If they balance, 8 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {5,6,1} is heavier, then either 5 is heavy or 6 is heavy or 2 is light. Weigh {5} and {6}. If they balance, 2 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {7,2,9} is heavier, then either 7 is heavy or 1 is light. Weigh {1} and {9}. If they balance, 7 is fake (heavier). If they don’t balance then 1 is fake (lighter).

8 identical balls one being heavier

Question: You are given 8 identical looking balls. One of them is heavier than the rest of the 7 (all the others weigh exactly the same). You a provided with a simple mechanical balance and you are restricted to only 2 uses. Find the heavier ball.

Answer: For convenience sake, let’s name the balls 1-8.

Step 1 : First we weigh {1,2,3} on the left and {4,5,6} on the right. There are three scenarios which can arise from this.

Scenario 1  /  Step 2
If the left side is heavier, then we know that one of 1, 2 or 3 is the heavier ball. Weigh {1} on the left and {2} on the right. By doing this, we will know if 1 or 2 is heavier. If they balance out, then 3 is the heavier one.
Scenario 2 / Step 2
If the right side is heavier, then we know that either 4, 5 or 6 is the heavier ball. Weigh {4} on the left and {5} on the right. By doing this we will know if 4 or 5 is heavier. If they balance out, then 6 is the heavier one.
Scenario 3 / Step 2
If {1,2,3} and {4,5,6} balance out, then we know either 7 or 8 is the heavier one. Weigh both of them to find out which one is heavier.

So we got the solution in 2 steps.