The Hanover Collaboration

I have a feeling the puzzle section is going to be dominated by probability type questions for a little while. I apologize if that isn’t your cup of tea. It isn’t mine either. That’s why I am reading a lot of books about it right now. Calling this a puzzle is somewhat inappopriate but hey, it’s an intersting problem. To tell the truth, it’s going to be a chapter in my thesis, so any idea is welcome. The best responses will be cited.

Lets say that Boeing wants me to make a screw for their answer to the Airbus A380. (Damn those European subsidies! Don’t they believe in the free market like we do?)

Rather than giving me a spec, Boeing supplied me with a simulation platform on which to test my screws. It exactly simulates use. The trouble is, I can’t look inside the tester. I can, however, collect a perfect history of the tests performed by the machine by putting strain gauges on my screw.

Assume that my screw doesn’t wear/fatigue. This makes every simulation independent and also lets me send them a screw that I have already tested.

Boeing says, “We need a screw that fails no less than once per 10⁹ uses.” But they give me a deadline which means I can only test my screw 10⁸ times. How confident can I be in my screw? Make whatever assumptions you want but you have to be able to justify them to the FAA.

Bonus 1: Now pretend that you are a real aircraft component manufacturer. Your components fatigue during testing. You have time for 10^8 total trials (to be split between test parts and on your deliverable part). What do you do and how confident are you?

Bonus 2: if we are trying to be realistic here lets chop that 10⁸ down to 10⁵ and that 10⁹ to “the best you can promise.” How good can you promise and how trustworthy are you?

Bonus 3: Why hasn’t the US made any major aircraft advances since the space race?

Lets say I have a regular polyhedron. It has N faces and E edges. I also have M different colors of paint with which to color the figure.

How many distinct ways can I do it?

I have two identical Crystal Orbs and I want to know the limit of how high I can drop them from without them breaking. In particular, I live in a hundred story building and I want to find out what is the highest floor of that building from which I can drop the an orb without it breaking.

I don’t mind breaking both my orbs to get this information.

What orb dropping strategy should I use if I want to minimize the number of times I have to drop the orbs in the worst-case?

If an orb breaks, you can’t use it anymore.

You want harder? If you insist. What strategy should I use if I want to minimize my (worst-case) time in the elevator or stairs instead of number of drops?

Harder still?! You’ve got to be nuts. Assume some sort of prior probability distribution over orb-break heights and minimize the expected number of drops or elevator time.

Nasty: Building with N floors M crystal balls. Feel free to use a computer. Algorithms will be rated on their big O running time for solving all M,N < R for some large R. To clarify, I am not interested in a fast solution for single querries of M,N. At the end, I want strategies and worst case drop numbers for every querry. Let me suggest Cormen et al, chapter on dynamical programming.

Here’s a kinda mathy one taken unabashedly from someone named Sudipta Das.

A handful of pirates distributed some golden coins among themselves, such that:

• the share of Pirate 1 plus half the total share of the rest (all pirates except #1)
• = the share of Pirate 2 plus 1/3 of the share of the rest (all pirates except #2)
• = ...
• = the share of Pirate N plus 1/(N + 1) of the share of the rest (all pirates except #N)

Captain Cutthroat, the puzzle-loving pirate, informed his captive Jolly Rogers of this strange method of distribution. Moreover, he promised to set Jolly free if he could correctly tell him the share of each pirate.
“The total number of coins is less than 1000, and more than 50% of us received an odd number of coins.”
Jolly Rogers got to work immediately, and after some time, asked the Captain, “Can you give me a little hint?”
“The least a pirate got is this number.”
Jolly Rogers was still not sure until the Captain boasted, “And I got more than 10 times that fellow.”

Can Jolly tell him certainly how many pirates and how many coins did each get? Assume that he had a pen and paper available.

Answer added

Seeing how I haven’t spent enough time on last weeks puzzle to throw down an adequate solution, I am going to leave it open for a little while longer. If you know the answer, I welcome you to submit it even if you found it in a book. Here’s the new one.

You are taking part in a game show. The host introduces you to two envelopes. He explains carefully that you will get to choose one of the envelopes, and keep the money that it contains. He makes sure you understand that each envelope contains a cheque for a different sum of money, and that in fact, one contains twice as much as the other. The only problem is that you don’t know which is which.

The host offers both envelopes to you, and you may choose which
one you want. There is no way of knowing which has the larger sum in, and so you pick an envelope at random. The host asks you to open the envelope. Nervously you reveal the contents to contain a cheque for 40,000 pounds.

The host then says you have a chance to change your mind. You may choose the other envelope if you would rather. You are an astute person, and so do a quick sum. There are two envelopes, and either could contain the larger amount. As you chose the envelope entirely at random, there is a probability of 0.5 that the larger check is the one you opened. Hence there is a probability 0.5 that the other is larger. Aha, you say. You need to calculate the expected gain due to swapping. Well the other envelope contains either 20,000 pounds or 80,000 pounds equiprobably. Hence the expected gain is 0.5×20000+0.5×80000-40000, ie the expected amount in the other envelope minus what you already have. The expected gain is therefore 10,000 pounds. So you swap.

Does that seem reasonable? Well maybe it does. If so consider this. It doesn’t matter what the money is, the outcome is the same if you follow the same line of reasoning. Suppose you opened the envelope and found N pounds in the envelope, then you would calculate your expected gain from swapping to be 0.5(N/2)+0.5(2N)-N = N/4, and as this is greater than zero, you would swap.

But if it doesn’t matter what N actually is, then you don’t actually need to open the envelope at all. Whatever is in the envelope you would choose to swap. But if you don’t open the envelope then it is no different from choosing the other envelope in the first place. Having swapped envelopes you can do the same calculation again and again, swapping envelopes back and forward ad-infinitum. And that is absurd.

That is the paradox. The question is: What is wrong? Where does the fallacy lie, and what is the problem? Some of you might think the answer is trivial. It is not. Anyone familiar with the St. Petersburg paradox?

Answer in comments

Congratulations to last weeks winner, Peter North.

I forget where this is from. Knuth I think or maybe Cormen. The shitty bonus problems are my design, as usual.

The boss is interviewing N canditates for 1 job. He wants to maximize the probability that he hires the single best qualified candidate for the job. The problem is that he must either hire or reject a candidate on the spot, before seeing the next candidate. That means he can’t interview everyone and then call the best one back. The candidates will be interviewed in random order.

You, his brilliant intern, are charged with coming up with a strategy. What strategy do you advise him to use and what are the odds? Makes no assumptions about the distribution of talent that he’ll see.

Assume everything necessary to make this work. In particular that there is a unique worst to best ordering of candidates and that the boss can always correctly tell who is the better in any comparison.

Feel free to assume N large if it helps the math.

Bonus 1a) What if he is more interested in maximizing the probability that he gets a candidate in the top M people?

Bonus 1b) What if he is hiring P people instead of only one and wants to hire all P of the top guys?

Bonus 1c) What if he would rather hire P of the top M people?

Bonus 2) What if he wants to maximize the expectation of ‘R,’ the rank of the person that he hires (or the sum of the ranks of the people)? R is an integer from P to roughly PN. What do you advise that he do and what is E[ R ]?

Real world version) I don’t think most MBAs would be into those answers. So instead, he issues issues an IQ test. The scores of the test are assumed to be gaussian and to relate linearly with a candidate’s qualifications. What strategy do you suggest he use to maximize the score(s) of who he hires?

Most of you have seen this one but maybe not the version that I am about to give. The solution to this one is so much more asthetically pleasing than the standard version.

There are 12 seemingly identical golden balls, one of which weighs slightly more or slightly less than the other 11. I have a ballance and want to determine which of the 12 balls is the odd one and also determine whether that ball is heavier or lighter thean the rest.

We only get to use the scale 3 times due to a callibration issue.

The part that is different than you’ve heard before is this: Before I weigh anything, you will tell me which balls go on which side of the scale for all three weighings. Then I will perform those three weighings. Then I will tell you the outcomes. Then you will tell me which ball and whether it is heavy or light. In that order.

In other words, your method cannot be adaptive.

Answer is in the comments

I gave everyone an extention because I though Michael was going to get it and primarily because I had a shit-ton of work to do during the last three days. I put my solution in the comments. I guess that means I won last week.

We decided to go with quality over originality. That means we are going to poach Joel for a while since he has the best collection of smart riddles I have ever seen. I would recommend not checking over there since it will ruin our weekly riddle schedule. I guess if you are into cheating, go ahead and click this link but, just so you know, Jon and I watch the link traffic.

Those super-rational pirates just nabbed some booty and are trying to divide it up. They use the following scheme: The pirates are ranked from most senior to least senior. The most senior pirate proposes a division of the loot and then all the other pirates vote on that division. If the vote passes, they divide the loot and return to pirating. If the vote fails, they make the pirate who presented the division walk the plank. Then the next most senior pirate proposes a division of the loot.

Since they are ultra-rational, the pirates vote in a deterministic manner.

#vote in favor of surviving

#given two choices have eqaul survival, they vote in favor of more booty

#given two choises of equal booty, they vote “no” to try to kill the most senior pirate.

There are N pirates and M gold coins. To unify notation, let pirate N be the most senior pirate and pirate 1 be the least senior pirate.

problem 1a) with M>N, what does pirate N propose? ties pass.
problem 1b) same as 1a) but ties fail.
problem 2) with M = 1 what does pirate N propose? ties pass.
problem 3) solve for any N,M passes tie or fail.

I welcome solutions for fixed N (e.g. 5,6 or 7) but the winner will be the first person with highest N.

We could potentially have multiple winners this week… I am so excited.

Addition: Brayt pointed out that a pirate can often make several equally good proposals. In that case, a pirate will randomly choose one, each with equal probability.

This requires that we modify rule 2 to say: ”... they vote in favor of more expected booty.” And rule 3 to say: “given two choices of equal expected booty…”

“Expected” means how much booty they can expect to get on the average if we repeated many times.

For instance, let’s say a pirate is voting on a scheme that gives him one coin now. Also suppose that if it fails, either he or another pirate gets two coins. He will vote “no” to the first scheme.

Answer added

Congratulations to Jourdan, last weeks winner, who edged out Scot by mere minutes.

There is a real difficulty in finding puzzles that are both obscure and high quality. Would you prefer an obscure geometry problem or this great one ripped off of Joel?

N super-logical pirates want to lock their gold in a treasure chest. They want to lock it with multiple locks so that it can be opened if and only if M of the pirates are present.

How many locks do you need and how do you distribute the keys?

Details for the picky: You can have as many copies of a key as you want. But to keep it simple, a lock can only be opened by one distinct key and a key can only open one distinct lock.

While seeing the pattern is certainly an acceptible form of solution, there are bonus points avalable for a clear explaination.

clue: I put a clue in the comments.
the answer is in there too

Brad won our inaugural puzzle, so it seems appropriate that we honor his recent post with my favorite mind teaser. I don’t remember who deserves credit for this one. Joran (again) perhaps?

There are four characters.

Arnob is 20 years old and works as a chef in a restaurant his father owns, but only until he can save enough to start a place of his own in California. Bob is unemployed, but thinking about serving his country in Iraq. Until then he’s living at home. They’re good looking guys, and they throw good game. Arnob has genital warts. He got it from a 26 year old waitress, and mother of two, who works at his restaurant. Bob, while working as a Counselor-in-Training at UpState Summer Camp after seventh grade, experimented with the tennis instructor, named Seth. The result was hepatitis C.

Yvonne, at age 33, has two years on her slightly more attractive (unless you really go for big boobs) little sister, Zanthe. Both earn respectable salaries, are self made, single, and childless. Each puts in about 70 hours a week at her job, though only Zanthe has to keep track of hours to bill. They’re leisure time is directed in whole to the pursuit of younger men to take advantage of. Yvonne will admit to having slept with 17 men. She picked up a case herpes, that rarely acts up, from her first lover (an ill advised fling with a street performer during college, while studying in Paramaribo, Suriname.) Zanthe is somewhat more honest, to use the word loosely, about her number, and luckier about her infection: HPV

Early one Saturday morning, the four find themselves at Zanthe’s apartment, drunk, high on E, and horney. A perfect storm of regretted decisions as is brewing, and you are their only hope.

Fortunately for everyone, they have condoms.

Unfortunately, they only have two condoms. For notational connivence, you should consider calling them 1* and *2.

Fortunately for you, you don’t have to be there. You only have to think about it.

2 men. 2 women. Each with a different sexual transmitted disease. Only 2 condoms. What can be done? Is there any way for both of the girls to nail each of the guys without anyone getting sick(er)?

While A, B, Y , and Z are often open to experimentation, today they’re only interested in normal, missionary-style, heterosexual intercourse. You can assume that the condom, provided it is strained to hold no more than a bread box, will not break. A correct solution to this problem will involve only condom management. It will not involve masturbation, curing the relevant diseases (be they curable or not), oral sex, dry-humping, alternative orifices, suppression of orgasm, other people, condom sterilization or cleaning, human sterilization, creative use of inanimate, battery-powered, or electronic devices, pornography, prostitutes, further chemical stimulation, differential geometry, or abstinence.

[UPDATE: Answer is in the comments. Don’t look if you don’t want to ruin it. Jourdan Abel took the victory on this one, by a hair over Scott Meek, who certainly had started answering before Jourdan hit the send button. I personally attribute the victory to Jourdan’s excellent implementation of the suggested notation (in addition, she developed her own system of condom notation, which the author has since amended to the problem description.)]

aha factor: !!

Since Joel hasn’t posted a new problem in ages and the puzzler often dissapoints, I though Jon and I might be willing to share some of our favorite riddles from time to time.

This one came from a Dartmouth math class.
There is a remote island where n of the m natives have blue eyes. Their religion also holds that anyone who has blue eyes must throw themselves off a particularly high cliff at midnight of the day they find out.

They never talk about anyone’s eye color and naturally, they are very careful about reflections.

There was a Christian missionary trying to convert them without success. When the Missionary gave up, he spitefully declared “At least one of you has blue eyes” and left.

What happens?

Too easy? Here’s the kicker: What, if any, new information did the missionary give?

This week’s winner was Brad Plummer. Don’t read the comments unless you want to hear the answer.