Interesting Stuff

Benazir Bhutto, former Pakistani Prime Minister and frontrunner in the upcoming election, has been assassinated. After speaking to several thousand people at a political rally, her motorcade was shot at and then attacked by a suicide bomber, reminiscent of the attack she survived several weeks ago. Approximately two thirds of the country supported her. The US and Pakistani governments were very quick to blame Al Qaeda (reminiscent of the way the government initially blamed the Oklahoma City bombing on Arab extremists), but counterterrorism groups say there is so far no credible link between the two groups, and Al Qaeda itself isn’t taking credit for this. Edit: Al Qaeda has taken credit for the assassination.

In the meantime, Pakistan has been plunged into protests and riots, and President Musharraf is considering postponing the upcoming elections and possibly even reinstating the martial law he ended scant weeks ago. Even if the elections are not postponed, many political parties are likely to boycott them.

Also courtesy of Steamboat Steven. That guy has all kinds of neat puzzles!

There are n prisoners on a train being taken to a prison. Once they arrive there, they will each be put in separate sensory deprivation chambers. They will have no conception of how long they have been in there. However, sometimes a guard will take one of them into a room with two switches on the wall, make the prisoner flip one of the switches, and send him back to his sensory deprivation chamber. If you wait long enough, every prisoner will go to the switch room an arbitrarily large number of times (i.e., none of them will be “starved” of visits to the switch room). At any time, any prisoner may make the claim that all prisoners have been in the switch room at least once. If he is right when making this claim, they will all be set free. If he is wrong, they will all be killed.

The prisoners can discuss and agree on a strategy for the switches right now, but once they reach the prison they won’t see each other again. They don’t know the initial configuration of the switches. No prisoner will know how many other prisoners have visited the switch room before him; the person who goes to the switch room first won’t know he’s the first. They won’t know how often the guards take people to the switch room, and even if they did they wouldn’t know how much time has passed between their own visits.

How can they be guaranteed to eventually go free?

Steamboat Steven gave me this gem. Unlike my previous discussion of a hat problem, this one can be solved in a reasonably short amount of time.

There are n people on a staircase facing downstairs when a hat is placed on each person’s head. There are c different hat colors, and each hat has a 1/c chance of being each color (that is to say, the color of each hat is independent; some of the c colors might not be used anywhere, while others may be very common). Each person can see the color of every hat downstairs from her, but not the color of her own hat or any hat upstairs. Starting at the top of the stairs and working down to the bottom, each person guesses the color of her own hat. Each person can hear all previous guesses.

The group as a whole gets 1 point for every correct guess, and nothing for incorrect guesses. If the group is allowed to discuss and to agree upon a strategy ahead of time, how many correct guesses can they guarantee?

One naïve strategy would be to have people 1, 3, 5, &c simply say the color of the hat in front of them, and have people 2, 4, 6, &c repeat that color, guaranteeing n/2 correct guesses. It turns out you can do a lot better. How?

I’ve been working off and on to find the optimal strategy for the final round of a game of liar’s poker. I’ve gotten a bit farther on it, and it now looks solveable. I’ve now solved the 12-card deck version (i.e. if the deck only contains aces, kings, and queens), and I suspect I’ve got an algorithm that will solve the whole problem in a reasonable amount of time.

A few more lemmata →

Randall Munroe, creator of the hilarious webcomic XKCD, gave a talk at work last week, and it was pretty interesting. I bring this up because he discussed the current comic in his talk. When the Google Labs Aptitude Test came out, Randall decided he was going to apply, but he didn’t want to turn it in until he had gotten all of the questions. He couldn’t get the resistor question, and eventually asked his physics professor about it. They filled up an entire blackboard without getting anywhere on the problem (see the alt text in the comic). Randall gave up on the GLAT and never turned it in. However, he eventually looked up some literature on the resistor problem: it wasn’t actually solved until the 60’s, and wasn’t solved elegantly until the 90’s. Both proofs required math so complex that he didn’t recognize it. He no longer feels bad about not solving the problem, though.

One of the other things he mentioned in the talk is that now that people read his comic, he has nothing new to talk about at parties; everyone has heard all of his stories and jokes already.

After a rousing match, the Good News squadron has beaten the Bad News team 2-1!

Bad News got off to an early start when a 1st grade teacher was sentenced to 15 days in jail for allowing her students to name a stuffed animal Mohammed. This apparently counts as blasphemy under Sharia, which seems ludicrous to me. People name their kids Mohammed all the time; I don’t see how this is any different. Although this was a sharp blow against Good News, their defense rallied when the Sudanese president commuted the jail sentence into just deportation back to the teacher’s native Britain.

At this point, the Good News offense kicked into high gear, and scored a huge goal when 17 US intelligence agencies declassified a report saying that Iran halted their nuclear weapons programme in 2003, contradicting the Bush administration’s warmongering and FUD on the topic. This is wholly consistent with what IAEA has said in the past (which I’ve mentioned several times). Bush has claimed not to have known about this report for more than a week, which seems like a lie considering that he’s been blustering about Iran for months.

My coworker commented that some of his faith in the government has been restored since this report came out; he had previously expected that even if such a report existed, it would be suppressed in order to push the hawkish agenda of those in power. However, I think enough people remember what happened with the Iraq intelligence problems and are afraid of repeating those mistakes that they could actually stand up and force the truth to light. Hurrah for some people in government not being totally corrupt!

These events shook up the Bad News team so much that they gave up another small gain to the Good News players in the last round of the match. Facebook has apologized for Beacon, with its poor implementation. Initially, this system would track people’s purchases on third party sites, even if these people were not logged into Facebook at the time, which founder Mark Zuckerberg has deemed, “simply… a bad job.” They have fixed it so that people can actually opt out of Beacon entirely, and thereby keep their private lives private. This is the second time Facebook has screwed up and fixed it several days later. Hopefully this time they’ll get the hang of what people actually want out of their site.

That led to the final score of the match, with Good News beating Bad News by a goal. Good News fans everywhere are rejoicing, as their team rarely beats the Bad News squad these days. Perhaps this is a sign that their new coaches and strategies will lead the team to better things in the future.

I have a friend in the movie business, and he had a very interesting take on the current writers’ strike. The writers’ guild has their contract up for negotiation right now, but the actors’ guild and the directors’ guild are both up for contract renewal very soon. My friend says that the reason the writers guild negotiations went to a strike is because the studio executives want to instill fear into the actors (and to a lesser extent the directors) over this sort of thing. The studios can survive for months if not years with all the scripts they’ve stockpiled (not counting topical TV shows like The Daily Show). However, if the actors strike, the studios will be in trouble. They hope the actors get scared enough from this strike that they’ll make extra concessions in their new contracts.

On the other side, the writers’ demands are a little silly; they are requesting royalties even before the producers have recouped their investment in the movie (i.e., if it cost $10 million to make the movie, the writers are requesting royalties before that $10 million is made up). I suspect this occurred because the guild began by requesting more than they really wanted (so they could be “negotiated down” to what they were actually after), and the movie studios took a hard line to scare the other guilds, and simply didn’t negotiate. My friend expects the strike to be over as soon as the actors guild finishes renegotiating their contract. I suspect it will resolve so that writers get royalties on all electronic media after the studios have gotten their investment back.

On a semi-related note, I had no idea how much money writers earned! Apparently movie scripts are purchased for $250,000-$5,000,000, not counting any royalties that come in after the film has been made. If you manage to sell one script every three years, you’re sitting pretty.

I don’t know how much of this is correct and how much is just my friend’s opinion. However, he has more of an insiders perspective than anyone else I know, so I thought I’d put this out there. Can anyone confirm or deny that this is what’s going on?

I recently wrote about a card game called Liar’s Poker and my endeavours to find an optimal strategy for the final round. Some extra progress has been made, but it’s still a long ways off. Despite what I wrote when I edited my previous post, I’m no longer convinced that we can adapt Simplex or a gradient descent algorithm to solve this. It turns out that although the gradient function is piecewise linear, there are an exponential number of different linear regions in it, and I’m not convinced we can do something like Simplex without enumerating them all. but here’s some other stuff Reid and I have done on the problem:

More strategies and proofs and stuff →

Liar’s Poker is a card game we sometimes play around the office. It’s a pretty simple game to learn if you’re already familiar with poker hands: the rules to Liar's Poker, followed by some work figuring out the strategy for the final round →

I really ought to finish this entry. Better late than never, eh?

Yesterday (being about a week and a half ago), I woke up at 3:30 AM, which was strange, because it was a full half-hour before my alarm was set to go off. I needed to get an early start on the day if I was going to be in Victorville (over 100 miles away) by 7:00. Find out what I was doing →