The Hanover Collaboration

This riddle is called The Unexpected Hanging Paradox

A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to the prisoner. He will not know the day of the hanging until the executioner knocks on his cell door at noon that day. Having reflected on his sentence, the prisoner draws the conclusion that he will escape from the hanging. His reasoning is in several parts. He begins by concluding that the “surprise hanging” can’t be on a Friday, as if he hasn’t been hanged by Thursday, there is only one day left – and so it won’t be a surprise if he’s hanged on a Friday. Since the judge’s sentence stipulated that the hanging would be a surprise to him, he concludes it cannot occur on Friday. He then reasons that the surprise hanging cannot be on Thursday either, because Friday has already been eliminated and if he hasn’t been hanged by Wednesday night, the hanging must occur on Thursday, making a Thursday hanging not a surprise either. By similar reasoning he concludes that the hanging can also not occur on Wednesday, Tuesday or Monday. Joyfully he retires to his cell confident that the hanging will not occur at all. The next week, the executioner knocks on the prisoner’s door at noon on Wednesday — which, despite all the above, will still be an utter surprise to him. Everything the judge said has come true.

What is wrong? Is anybody abusing logic here? If so, who?

Suppose that he was told the execution would be either Monday or Tuesday (equivalently, the week only has two days) and he was executed on Monday. Is this case different?

Somebody at work asked about the chicken scratchings I used in the snack room and in response to my solution said something fawning about how neat it was that I could just change my number representation however it suited me.

As Jon would guess, that led to a conversation about balanced tertiary, and the following problem arose.

You have a balance with two pans and an object with integer mass, N, that you would like to determine. You have the following known masses:
let k be an odd, positive integer. You have (_k_ – 1)/2 of each mass of weight kⁿ for n in the non-negative integers. With this set of masses, each integer will have a unique representation.

You would like to determine N in a minimum number of weighings. Any time you add or remove a single mass from the scale counts as a weighing.

For instance let k=3, and I wanted to put 128g (=243-81-27-9+3-1) on the scale when 256g (=243+9+3+1) was on their previously. To do so counts as 6 weighings.

I’m looking for the big-Oh (in terms of N,k) of your strategy. From the above example I think it would be easy to argue that binary search is O(log ² (N)). Can anyone do better?

At work we’ve got a snack room and there is a tab on the wall. Attached to it is a pen rather than a pencil as you would expect in a perfect world… Anyway, I’m struck by how inefficiently most people use the space in it, forcing it to be pages and pages long.

All the prices are divisible by five and go from 5c up to $1 with 45, 55, 65, and 95cents all absent. Come up with a scheme for keeping track of the cumulative sum of transactions that doesn’t use a lot of space.

Benchmark: You’ve got enough room for about 80 characters, so you should be able to get at least 160 items before starting another page.

Hard version: You maintain a fixed number strings of {0,1}*. After each transaction (containing potentially multiple items) you may add as many characters to whatever strings you’d like. From these strings you need to be able to construct the sum of the transactions.

You can assume each transaction comes from a finite set with a known probability distribution. Come up with a scheme that minimizes the expected bits per transaction. You’re welcome to make limiting case arguments, but winners are going to be picked at 640 bits.

In a desperate effort to stem inflation President Imajarhead of Iran is issuing a new currency. For whatever reason, it is very important to him that he can make all possible change denomitations, from one centiroentgen up to ninety-nine, using at most two coins. His first idea was to have a one cR coin and then all of the evens. Although the person who told him that this was sub-optimal has been imprisoned, he had the sense to contact you, the well known Mathematician, to determine a set of denominations that requires the fewest distinct coins. What are they?

Bonus. Impressed by your quick success on the Iran job, the government of Japan contacts you to determine a minimum set for 1 to 999 rin.

Also, I’ve posted the solution to last weeks puzzle. Congrats to Liz for solving it and retaining a shred of her previous sanity.

Either you guys took THC off your RSS readers or last week was too abstract for the first time back. This should be more concrete¹, which is not to say easier. If nobody answers this one, we’ll try easier.

Remember Labyrinth the tour de force by Jim Henson, George Lucas and David Bowie? At one point, the heroine was faced with two guards, one who always lied and another who always told the truth.

Imagine that you find yourself in the following, similar situation. Three guards block your path and will bar your way unless you can name them. You know that their names are Godel, Escher and Quine and that Godel always answers correctly, Escher always lies and Quine answers randomly. However, you do not know which is which. You may ask three yes/no questions, sequentially, to guards of your choice.

What do you do?

¹ Ironically, while working on this problem, my advisor asked what I was working on and I had to come up with an equivalent abstract problem off the top of my head. I said something about model-diagnosis and finding a faulty device in a logic circuit.

Bonus: There is an even better version of this on Wikipedia with the title the hardest logic puzzle ever. In that problem, the guards answer in an unknown language with “da” or “ja” and you don’t know which is “yes” and which is “no”.

Solution:

• Let T_n be the statement, “Person n always tells the truth.”
  
  
  
• Let F_n be the statement, “Person n always lies.”
  
  
  
• Let X_n be the statement, “Person n answers randomly.”
  
  
• Let 4 be a universally true statment, e.g., “2 + 2 = 4”.
  
  
  
• Let D be the statement, “ `Da’ means `True.’ “
  
  
  
• For any statement S, S? denotes the question, “Is S true?”
  
  
  

Consider the question = “4 if and only if D?.” If “da” means “false”, then the statement is false and therefore the answer (if put to the honest person) would be “da.” If, on the other hand, “da” means “true,” then the statement is true and the answer will still be “da.”

Now consider the question “ 4 if and only if D?” If “da” means “true”, then the statement is false and the honest answer would be “ja.” If, on the other hand, “da” means “false”, then the statment is true and the answer would still be “ja.”

You can see that if we ask “S? if and only if D?”, we can pretend that we simply asked S? and interpret “da” to be “true” and “ja” to be “false.” Hitherto, I will strip this and assume that the people answer in English.

What makes the problem tricky is that you might ask your first question to the random guy. So it would be logical to assume that our second question will be to somebody different than the first question. It would be nice if the second question were surely put to someone other than the random guy. That would be some question, the answer to which has the following truth table. Assume that we ask the first person.

1	2	3
T	F	X	T
T	X	F	F
F	T	X	T
F	X	T	F
X	T	F	T/F
X	F	T	F/T

If the answer is “True,” then we know that the second person is not random and if it is “False,” we know that the third is not random. Now let’s try to come up with such a question.

Consider the statement “F₂ and X₃.” hitherto abrevieated F₂X₃.
Consider also the statement X₂T₃. Finally consider “F₂X₃ or X₂T₃“ hitherto abreviated F₂X₃+X₂T₃.

1	2	3	F2X3	X2T3	F2X3+X2T3
T	F	X	T	F	T
T	X	F	F	F	F
F	T	X	T	T	T
F	X	T	T	F	F

Which is that for which we were looking.

So now we’ve identified a person who is surely not random and we still have two questions left. It should be pretty easy from here. We can simply ask the non-random person X₁? and 4? and that will unambiguously identify the case.

For completeness, let’s write out what I would actually say for the first question.

Is it the case that,

• person two is the liar and,
  
  
  
• person three is random
  
  
  

           or,

• person two is random and,
  
  
  
• person three is always truthful
  
  
  

if and only if

• “da” means “true?”

Liz came up with a terse and elegant version of the same question, “If asked [4], would person three be more likely to say `da’ than person two?” As a result, she is now tied for second place with 4 points.

---

File translated from
T_EX
by
T_TH,
version 3.85.
On 2 Feb 2009, 15:30.

By popular demand. The score stands at

• Brayton: 4
• Fromberger: 4
• Joran: 4
• Jourdan: 4
• North: 4
• Plumer: 4
• Shea: 4
• Cosmo: 0
• Tom: infinity

It’s a tight race for second!

Recall the classic twelve ball, three weighing problem. Of the K balls, one is either heavier or lighter and your goal is to determine which (and whether it is heavy or light) by using a balance N times.

The problem for this week is to determine the most balls that can be distinguished in N weighings. Your anwer is allowed to be adaptive. In fact, I’m suspicious that your anwer must be adaptive.[2]

Feel free to define it as a recursion, i.e. assume you have a method for determining K’ balls in N-1 weighings and then use K’ in your expression for K. If you do this, be sure to define a base case e.g. N=2 or N=3.

Bonus. Suppose that I have marked exactly one of the K balls and tell you that the marked ball is either normal or light; it is surely not heavy. How does this change your answer?

² Bonus to anyone who proves or disproves this.

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

(kUnlockSong believe bornto
...

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.

Okay, if you insist, the bonuses.

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?