Box 'o Numbers

Problem: Arrange the numbers 1 to 8 in the grid below such that adjacent numbers are not in adjacent boxes (horizontally, vertically, or diagonally).

       ___
     | 1 |
 =============
 | 6 | 4 | 3 |
 =============
 | 2 | 7 | 5 |
 =============
     | 8 |
     =====

The arrangement above, for example, is wrong because 3 & 4, 4 & 5, 6 & 7, and 7 & 8 are adjacent.

Solution:

The key (as I see it) is putting the 1 & 8 in the centre spots - which is required, because those spots both border all but one of the other spots, and 1 & 8 are the only numbers that are only adjacent to one number.

From there, the 2 & 7 are forced, then you have your choice of the next number, which then forces the rest. Really, though there are only two valid solutions, and they are mirror images of each other.

Oil Mogul

Problem: You are an oil mogul considering the purchase of drilling rights to an as yet unexplored tract of land.

the well's expected value to its current owners is uniformly distributed over [$1..$100]. (i.e., a 1% chance it's worth each value b/w $1..$100, inclusive).

bcause you have greater economies of scale than the current owners, the well will actually be worth 50% more to you than to them (but they don't know this).

the catch: although you must bid on the well before drilling starts (and hence, before the actual yield of the well is known), the current owner can wait until *after* the well's actual value is ascertained before accepting your bid or not.

what should you bid

Solution:

This problem amounts to properly defining the expected value of the well to you.

The following equation does it:

(1%) * [(1.5 - 1)] +

(1%) * [(3 - 2) + (1.50 - 2)] +

(1%) * [(4.5 - 3) + (3 - 3) + (1.5 - 3)] +

. . .

(1%) * [(150-100) + ... + (3-100) + (1.5-100)]

Each line represents your expected value from a bid of 1$, 2$, ..., 100$, respectively.

eg, consider line 2 above. if you bid $2...

With 98% probability you won't win the contract, so your profit is 0. With 1% probability, you will win something worth (150%*1) = 1.5, for which you paid 2$ With 1% probability, you will something worth worth (150%*2) = 3, for which you paid 2$

So, your goal is to maximize the following function of x, where x is your bid.

f(x) = 1% * Sum_{i = 1 to floor(x)}{ x - 1.5*i }

There's no benefit to non-integer bets, so re-write the maximization function as :

ARGMAX(k) {1% * Sum_{i = 1 to k}{1.5*i - k}}

(=) ARGMAX(k) {Sum_{i=1 to k}{1.5*i - k}} /* 1% isn't a function of k or i, so toss it */

(=) ARGMAX(k) {Sum_{i=1 to k}{1.5*i} - Sum_{i=1 to k}{k}} /* Split the summation */

(=) ARGMAX(k) {(0.75)(K)(K+1) - K^2 }} /* Closed form for summations */

(=) ARGMAX(k) {(0.75)(k)-(0.25)(K^2)}} /* Algebra */

And that function is maximized at k = 1 and k = 2.

When choosing b/w $1 and $2, you should bid $1 because of time-value, reinvestment risk, etc, of the extra dollar.

(ie, if you don't have to spend the extra $$ now, don't)

Classic coin weighing (Hard)

Problem: You have 12 coins. one of them is counterfeit. all the good coins weigh the same, while the counterfeit one weights either more or less than a
good coin.

your task is to find the counterfeit coin using a balance-scale in 3 weighs. moreover, you want to say whether the coin weighs more or less
than is should and, and this is the real kicker, your weighs must be non-adaptive.

that is, your choice of what to put on the balance for your second weigh cannot depend on the outcome of the first weigh and your
decision about what to weigh for round 3 cannot depend on what happened on either your first or second weigh.

for example, you can't say something like "take coin #1 and coin #2 and weigh them. if they balance, then take coins 3,4,5 and weight them
against 6,7,8...if 1 and 2 don't balance, then weigh #1 vs #12..." you have to say something like:

round #1: do this
round #2: do this
round #3: do this

if the results are left tilt, balanced, and left tilt, respectively, then coin #11 is heavier than it should be.

this problem is solvable...it took me about 1-2 hours of working on it to get it. i think even finding the counterfeit using an adaptive solution is tough. then non-adaptive constraint makes it quite hard and having to find whether it's heavier and lighter is cruel and unusual riddling ;-)

Hen

Problem: If a hen and a half lay an egg and a half in a day and a half, how many hens does it take to lay six eggs in six days?

Solution:

If 1.5 hens lay 1.5 eggs in 1.5 days (or 36 hours) then: 1 hen lays 1 egg in 1,5 days or 4 eggs in six days thus 1.5 hens lay 6 eggs in 6 days

Duel

Problem: You find yourself in a duel with two other gunmen. you shoot with 33% accuracy, and the other two shoot with 100% and 50% accuracy, respectively. the rules of the duel are one shot per-person per-round. the shooting order is from worst shooter to best shooter, so you go first, the 50% guy goes second, and the 100% guy goes third.

where or who should you shoot at in round 1?

Solution:

You have 3 options to consider:

(1) Shoot at 50% guy. Death comes with: 72% likilhood (2) Shoot at the 100% guy. Death comes with: 63.64% likihood (3) Shoot into the air (purposely miss). Death comew with 58.33% likihood.

So, you shoot into the air and hope for the best.

Calculations:

The p in the probabilities below represents your probability of dying at some point if you MISS either guy in the first round. It'll be filled in later.

(1) if you shoot at the 50% guy and get him, you're guaranteed to get shot the next round.

prob of dying at some point by aiming at the 50% guy:

(=) (33.3%)(100%)+(66.67%)*(p)

(=) (33.3%)+(66.67%)(p)

(2) if you shoot at the 100% guy and get him, you're left with this geometric sum of probability of getting shot by the 50% guy at some point in the future...it converges.

(=) [(50%)] +

[(50%)(66.67%)(50%)] +

[(50%)(66.67%)(50%)(66.67%)(50%)] + ...

(=) 50% * { 1 + (1/3) + (1/3)^2 + ... }

(=) 50% * {3/2)

(=) 75%

so, your prob of getting shot if you shoot at the 100% guy is:

(=) (33.3%)(75%)+(66.67%)(p)

(=) (24.75%) + (66.67%)(p)

still crummy, but it dominates the alternative, for positive p.

(3) What happens if you miss? ie, what's (p)?

if you miss, the second guy has a choice to make...does he shoot at you, or the other guy? his options:

(1) Shoot you: if he gets you, he's guaranteed to die on the next shot.

if he misses, he has q chance of dying (which we'll get later).

(=) (50%)(100%)+(50%)(q)

(=) (50%)+(0.5)(q)

(2) Shoot at the 100% dude:

If he gets the 100% guy, there some infinite sum representing his probability of getting shot by you:

[(33.33%)] +

[(66.67%)(50%)(33.33%)] +

[(66.67%)(50%)(66.67%)(50%)(33.33%)] + ...

(=) 33.33% * [ 1 + (1/3) + (1/3)^2 + ... ]

(=) 33.33% * [(3/2)]

(=) (50.0%)

So, he chances of getting shot if he shoots at the 100% guy are:

(=) (50%)*(50%) + (50%)(q)

(=) (25%)+(.5)q

No matter what q is, he'd prefer shooting the 100% guy to shooting you.

Now, what happens if *he* misses (the 100%) guy? ie, what's q? if he misses, then the 100% guy has to make a decision:

(1) Shoot you:

he's guaranteed to get you, so his chances of dying are just 50%. (game ends after the next round...the 50% gets only one shot)

prob of dying: 50%

(2) Shoot the 50% guy:

by the same logic, he'd have a 33.33% chance of death (getting shot by you).

So, he prefers to shoot the 50% guy.

So, q is 100% (ie, if the 50% guy misses, the 100% guy shoots him immediately). From that, we know the 50% guy's optimal move, if everyone's around on his first shot. He'd prefer shooting at the 100% guy to shooting at you or purposely missing.

Now, we need to get p, which is our probability of dying if we purposely miss either guy (shoot into the air).

We know the 50% guy shoots at the 100% guy if we miss.

(1) With 50% probability, the 50% guy kills the 100% guy, resulting in a shootout b/w us and the 50% guy.

(=) (50%) * [ (66.67%)*(50%) + (66.67%)*(50%)*(66.67%)(50%) + ...

(=) (50%) * [ (1/3) + (1/3)^2 + ... ]

(=) (50%) * [0.5]

(=) (25%)

(2) He misses him. Then, we get one shot at the 100% guy (after the 100% guy shoots the 50% guy).

Our chances of death are:

(50%)*(66.67%) = (33.33%)

So, p is (25%)+(33.33%) = 58.3%

So, again, our three choices are

(1) Shoot at 50% guy. Death comes with:

(=) (33.3%)+(66.67%)(p)

(=) 72% likilhood

(2) Shoot at the 100% guy. Death comes with:

(=) (24.75%) + (66.67%)(p)

(=) 63.64% likihood

(3) Shoot into the air (purposely miss).

(=) p

(=) 58.33% likelihood.

Vienna

Problem: It's the middle ages, you're travelling across europe and you want to find the way to vienna. you come to a crossroads, now there are two ways to go. at the crossroads stand a knight and a knave. the knight answers every question truthfully. the knave answers every question falsely. you don't know which guy is which. how can you figure out which road leads to Vienna by only asking one question?

Solution:

Many people try "what would the other man say if I asked him which way to Vienna?" But for that to work, the knight would have to know that the other man is a knave, and the knave would have to know that the other man is a knight; it's not clear that either of these is a given.

To cope with that, you can ask "assuming the other man has the opposite predilection regarding truth-telling from what you do, what would he say if I asked him which way to Vienna?"

More interestingly, you can ask "if you were to ask yourself which way to Vienna, what would you say?" But before risking that question, I'd want a few more details about how the knave is wired up. What does it mean, to lie to oneself? Is such a thing even possible, regardless of what psychoanalysts might claim?

Furthermore, travelling through Europe in the middle ages, it's a bit of a rash assumption that people you meet at a crossroad would understand English. If you only have 1 question, you have to frame a question that is meaningful in all locally spoken languages (like writing a program that is both legal Fortran and legal C). Your question doesn't have to mean exactly the same thing in each language, as long as each possible answer carries in itself an indication of which language it is in.

Or you could try the universal language of mime. Say "Vienna" and open your arms wide with a questioning look. But how would you mime "if you were to ask the other man ..." (or "if you were to ask yourself ...") ?

100 Factorial!

Problem: How many trailing zeroes are there in 100! (100 factorial)?

Solution:

One per factor of 10, and one per factor of 5 (there are more than enough 2's to pair with the 5's), plus one per factor of ten squared (one occurrence) and one per factor of 5 squared (three occurrences).

So if I'm counting correctly, that'd be 10 + 10 + 1 + 3== 24 zeroes.

Assuming the question meant *trailing* zeroes. It'd be much harder to also count the intermingled zero digits in the entire expansion.