The Hanover Collaboration

Some of you have perhaps heard that the current Powerball jackpot is 365M$. The odds are 55 choose 5 times 42 or 146M to 1. But there are som e caveats. Firstly, a “365M$” prize is actually only 177M$ which they will invest in an annuity and pay out over 30 years. Or you can take the 177M$ right away. Based on the current tax situation and the bond market, I think right away is maybe the way to go.

But we can’t forget the taxes. You are looking at 35% federal and 0-9% by state. So even in NH you’d only be looking at 115M$ which is is notable because it is less than 55 choose 5 times 42.

But there is more bad news, you’re not the only person playing. On wednesday there were 2.54 million minor winners which tells us that there were about 90 million tickets sold. So if you won, there would be a 90/146 chance that another person had won, a (90/146)^2 chance that two had won, etc. If I were more on my game I would find the closed form, but it converges to only 71M$ after taxes and the potential for splitting.

But lets say that you either have a funny $/utility curve or that you derive more than, uh, 51 cents of pleasure from the actual playing. Assuming that pleasure is uniformly distributed over the numbers you pick, you might think that you could do no better than random. But you’ll notice that 30 percent of people pick their own numbers. Amongst those I would expect 1-12 and 1-31 to be badly over-represented. After that, I would expect number to increase in probability from 32 to 55 because of more of the people born in the later years are still alive. So it might be prudent to bias your choice into the places that are under-utilized.

Of the people picking their own numbers I’m going to guess that two thirds are using dates. Let’s assume those dates are uniformly distributed on the calendar (ignoring the periodicity of birth and marriage rates).

I’ve got company and I’ve got to go. I’ll leave the rest of the derivation as a puzzle.

Game makers these days have got to realize that the first thing people are going to do is look at the whole thing with HexEdit. In some cases like Quake 3, that was welcome. All the data for was stored in a .zip archive in individual recognizable files. If you wanted to add bots that looked like, say, girls on the ski team or put writing on the walls in some level it took very little effort to figure out how to do that.

The first game that I hacked on Xbox was Leasure Suit Larry, Magna Cum Laude (nothing modivates a man like sex). There were censor bars on the private parts so I grepped the disk for the ascii representation of “nudity”. It apeared a couple of times. There was a file \data\jamfiles\xbox\AppInit.jam containing the following gem.

// Nudity Setting—set this value to 1 to remove censor bars (for european version) DataLink { Name “NudityMode”Type BooleanData 1 }

Except it used to say “Data 0”. After that, I always looked at my new games to see if there was easily unlockable stuff. It’s nice being rewarded with unlocks but if I’m just renting a game for the week, and I’m not really into it, I definitely don’t feel like putting in the time to beat it on kill your friends hard just to see the alternate ending. But if the game itself doesn’t have something obvious, like the ascii string “unlock” in someplace decypherable (i.e. not the executable) or “hard_mode_finished” in the save game memory, I don’t put more effort into it.

But the buzz surrounding GTA:SA was so much, I had to investigate. If I were the sort who grepped for “sex”, I would have found many many appearances, most of them they are either inocuous like “sex_appeal”, “sexywoman.mdl”, or non-obvious like “SEX” without anything decypherable nearby. But then there is this one, in the file \data\scripts\scripts.img

gf_date.scm00AC00AD00AE00AF00B000B1008800000004000000
gf_meeting.scm000000AE00AF00B000B1008C00000007000000
gf_sex.scm0000AC00AD00AE00AF00B000B1009300000005000000
Here is where I lose the trail. This looks to me like padding, a base address and an offset, but I can’t find what it referrences.

There is an appearance of the same three things, “GF_DATE… GF_MEETING…GF_SEX” in the file \data\scripts\main.scm which suggests to me those files are in there except it is not clear to me how to find them. But it is also not surprising that someone else figured it out.

Finally I get to my whole motivation for posting. I just got Karaoke Revolution Party. It is pretty sweet. They didn’t screw anything up from Karaoke Revolution and the added 1) more songs 2) duets and 3) DDR and singing at the same time.

I wanted to just drop it in and have all the songs. I don’t want to have to gradually earn them. I was also hoping that I could also play the songs from the first one without changing disks or anything. With the first one, it wasn’t a problem. It wasn’t hard to find this in config\db.dta

;; initial unlocked songs are these, plus all showtime songs

But now I’m looking at the second one and there is no such file. Well, there is, it’s just in an .ark file somewhere. All of the important game data (except it seems, the dancing steps) are in these archive files—sort of like quake 3 except these don’t appear to be standard files. They are compressed and have the file info obfuscated (though I think still present). There is a separate file that gives the filenames and structure for what is clearly in there. We know (some of) what is in there because, people have already found playable .ogg files in continuous blocks (I guess since .ogg doesn’t compress further?). But the key is to be to figure out the compression scheme and dig out the file “unlock.dta” that is surely in there.

Now there is a separate tack to take. When you unlock a song and then save your game, the song stays unlocked. Clearly then, there is an unlock record on in the savedata. But it isn’t obvious how that data is organized. I’m going to start over and play and save and check a few times to see what changes. I’ll let you know.

Sorry it’s been so long. I think this one comes from Drysdale in which case several of you have heard it already.

You’re minding the desk at the Infinity Hotel that has infinity¹ rooms, an infinitely large lobby and a very impressive intercom system that allows you to speak with everyone at once just by pressing a button.

It’s labor day and the entire place is booked. Not a single empty room.

0: A weary traveller comes to your desk and asks, “Do you have any vacancies?” to which you reply, “No, but I can still give you a room.”

How do you do it?

Rules: Everyone has to have a finite room number assigned to them. You are only allowed to say finitely many words.

Convenience: This hotel uses keycards that can be reprogrammed automatically.

1: Infinity Bus drops off an infinite tour group who queue to your desk. You’re like, “Shit, my girlfriend will be pissed if I work late tonight.” The tour director comes up to you and says, “Do you have room for us?” to which you reply, “But of course, this is the Infinity Hotel.”

How do you do it and still make it home for dinner?

Convenience: You have a machine that takes a credit card and issues a keycard.

¹ Math geek notice: I’m going to use the word infinite with deliberate sloppiness. Pretend I don’t know better. Let’s not needlessly complicate the discussion. If I see even one aleph in the comments, you’re not getting another puzzle for months.

Which is worse for America, and us as Americans: the biblical flood in New Orleans, or September 11th?

When considering this question, please make causality issues symmetric. That is, either assume that the flood was caused by terrorists, or assume that the crashing planes were a freak natural event. Does it matter which you pick?

Personally, I’m tempted to say New Orleans isn’t as bad. It’s worst effects were concentrated on poor people.

On the other hand, if I had to pick one of the two disasters to get strong, forceful, decisive, instantaneous leadership and action from our Federal government, and the other to get shitty apathetic leadership, then I think I might switch the two.

Anyone else noticed that Slate has started using gmail accounts?

pressbox@slate.com has become slate.pressbox@gmail.com

I can’t see any reason for this. I doubt an online magazine would outsource email to save on expenses. Likewise, I doubt that it is paid placement for gmail. Any thoughts?

Also, is the comment format stifling discussion? I’ll try to make the font bigger, or something.

Here’s one that I’ve been saving for a rainy day. It is one of my favorites. As such, don’t expect to get it right away. If you’ve heard it already, please give other people a chance for the first few days.

I give you an ordinary deck of 52 (distinguishable) cards and ask you to remove 5 cards from it—any 5 you want—and then give them to me.

Of those 5 I choose one that I give back to you. The other four I order in a way that Jon and I have discussed earlier. I hand the 4 cards to Jon, and he promptly tells you which card I handed you.

You suspect foul play and then ask me to repeat the feat but this time with Jon locked in a room, and rather than handing him the cards, you say their values through the door. He is correct again. (In other words there is no information besides value and order, i.e. there is no stupid trick.)

We can repeat this feat with all 52 choose 5 hands you can give me.

0) How do we do it? or rather, what is one possible way in which we can do it?

1) Could this be done with more cards? If there were a 53rd card, could we come up with a new algorithm that could encode that also? If so, present it and say what is the most cards your algo can handle. If not, prove it.

2a) What if I gave you a 6th card, what is the maximum number of cards the deck contain and have your algorithm still work?

2b) What if I gave you N cards, what is the maximum deck you can handle?

3) Prove 2b.

I’ve gotten a few requests for less abstract puzzles. I’ll do my best to oblige while trying to keep them challenging and interesting enough for our brilliant readership.

I’m driving 500mi from Salt Lake City to Reno and my car breaks down. So I call the AAA and they want to know where I am. I tell them that I’m on I80 between SLC and Reno and they say that they need to know precisely where I am before they can help me.

Now I’ve got to tell you something about my car… Neither the speedometer nor odometer work. For some reason, there are no mile-markers on the road. I have a watch that keeps good time but I haven’t set it in ages.

As I am pondering an astronomical solution to my conundrum, a Greyhound bus criuses by. I remember that Greyhound busses leave SLC every hour, on the hour and drive at exactly 60mph towards reno. I ask the AAA lady for the time but she refuses to help me.

1) By how much can I narrow down my position?

Exactly 4 minutes later, a Peter Pan bus cruises by. Peter Pan busses leave SLC at half past the hour and drive at 65mph.

3) Now can I tell AAA where I am?

Suppose the bus companies sent out a bus every minute instead of every hour.

4) Could I still figure out where I was?

Whoa, double banger this week. I just felt bad only doing probability. But Joran and I seem to like them. So here’s the probability one.

Lets say I have this black box random function (or process as some like to say). I push the button on top, there is a painful grinding noise and then a number (on the reals) pops out.

If the number is greater than any previous number, I get excited and write it down.

If I press the button N times in a row without getting a new highest number, I get bored and quit.

0) On average, how many times, t, do I press the button before quitting?
1) what is P(quit|t)
2) what if instead of spitting out a number on R, it spits out a vector on R^m and I write down the max for each individual component. That is, I don’t quit unless I see N consecutive vectors none of which have a component that breaks the record for it’s position.
2b) What if rather than quitting completely if none of them improve, I quit looking at a component if that component fails to improve N times in a row. How long until I quit looking at all the components?

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

I try to optimize my change. Carrying around nickles sucks. But since I have to use laundry machines, I like to get quarters. Since I like to get food from the vending maching that only takes ones I like them too.

Let’s say I have this vector of weights, W, that tells me how much each is worth to me (in the non-monetary sense). What strategy do I use to maximize W’M where M is the amount of money that I have in my pocket? What is the steady-state rate of coin collection?

Assume 1) transactions are uniform over [0… 5$] mod 5$ You can widen that if you want to include weights for larger bills. For instance hundreds scare me so I like to break them..
2) people always give me minimum change in number of coins, except,
3) people will not convert currency. For instance if I buy something at the dollar store and pay 1.25 using [1 0 2 1 0]’ I will not get a quarter back.

1)What if I start the week with only 20s (or hundreds if you are using more weights). During the week I make N transactions. At the end of the week, I take all of my money to the bank and get 20s again. At what rate is the bank acruing each denomination?

2) I have this friend with a different weight vector, W_f. At the end of the week we get together and trade money. Since I know W_f, do I change my change strategy? What is our combined rate of coin capture? How much do we profit by trading?

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?