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.

Red Marbles, Blue Marbles

Problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a jar.


Solution

Chance! chance is easy if you know how to do the formula. we know that we have two choices to make. first we’ll pick a jar, and each jar will have a 1/2 chance of being picked. then we’ll pick a marble, and depending how we stack the marbles, we’ll have a (# of red marbles in jar)/(# of total marbles in jar) chance of getting a red one.

for example, say we put all the red marbles into jar A and all the blue ones into jar B. then our chances for picking a red one are:

1/2 chance we pick jar A * 50/50 chance we pick a red marble
1/2 chance we pick jar B * 0/50 chance we pick a red marble

do the math and you get 1/2 chance for a red marble from jar A and a 0/2 chance for a red marble from jar B. add ‘em up and you get the result = 1/2 chance for picking a red marble.

think about it for awhile and see if you can figure out the right combination. we had a 50/50 (guaranteed) chance in picking a red marble from jar A, but we didn’t have to have 50 red marbles in there to guarantee those fantastic odds, did we? we could’ve just left 1 red marble in there and the odds are still 1/1. then we can take all those other marbles and throw them in jar B to help the odds out there.

let’s look at those chances:

1/2 we pick jar A * 1/1 we pick a red marble
1/2 we pick jar B * 49/99 we pick a red marble

do the math and add them up to get 1/2 + 49/198 = 148/198, which is almost 3/4.

we can prove these are the best odds in a somewhat non-formal way as follows. our goal is to maximize the odds of picking a red marble. therefore we can subdivide this goal into maximizing the odds of picking a red marble in jar A and maximizing the odds of picking a red marble in jar B. if we do that, then we will have achieved our goal. it is true that by placing more red marbles into a jar we will increase the chances of picking a red marble. it is also true that by reducing the number of blue marbles in a jar we will increase the odds also. we’ve maximized the odds in jar A since 1/1 is the maximum odds by reducing the number of blue marbles to 0 (the minimum). we’ve also maximized the number of red marbles in jar B. if we added any more red marbles to jar B we would have to take them out of jar A which reduce the odds there to 0 (very bad). if we took any more blue ones out of jar B we would have to put them in jar A which reduce the odds there by 50% (very bad).

it wasn’t really a good proof, but QED anyway :-P