2010-09-27

Easy Month: Rock Paper Scissors

Bengt and Alban are playing Rock-Paper-Scissors. Unsurprisingly, it soon turns into a discussion of game theory.
"Suppose you get one point for every round you win." says Bengt.
"Sounds reasonable."
"And suppose you play forever."
"Sounds a lot less reasonable."
"Oh, you know what I mean. You play for a really long time so that everything becomes statistical and stuff."
"Okay, sure."
"So, question: What is the optimal strategy?" asks Bengt.
"That depends on what the other guy does."
"Yeah, but assuming you don't know anything about the enemy's strategy."
"Enemy?"
"Or opponent, whatever."
"There isn't one."
"Right. There isn't any strategy that makes sure you win. So we just slightly redefine 'optimal', just for the sake of this problem, to mean the strategy which makes sure you play even. In the long run."
"Actually, it's very unlikely that you'll play even, in a very long game."
"Oh, you know what I mean. You'll sort of play even, almost."
"It's not like you to be so vague."
"All right, how about this: The optimal strategy is the strategy such that regardless of the enemy's strategy the expectation value of one's score minus the enemy's score is zero."
"Sounds good. And that strategy is to pick a sign at random."
"Specifically, with the same probability for each sign. That's important."
"Okay, sure. What's your point?"
"Well, it's boring. It's no fun if you can't win. Maybe we could ban the use of that strategy?"
"I don't think that would work."
"Fine. Let's think of some other games. Here's one: It works the same, except that if you win with a rock, you get two points instead of one."
"Eh, sounds like fun... Here's one I've heard of: Rock-Paper-Scissors-Lizard-Spock. It's like the normal game but with five signs. Lizard beats paper and Spock, Spock beats rock and scissors."
"Oh, I have another one: Rock-Paper-Water-Lichen-God."
"Okay, how does that work?"
"Well, paper beats rock as usual, and it also beats lichen, because, I don't know, you can scrape it up with the paper or something. Lichen beats rock and water, because it grows on the rock and drinks water. Water beats paper, obviously, and it also beats rock, because dripping water can wear down the rock."
"Wait, so they all beat rock?"
"Yup. And God beats all of them. But rock beats God."
"How does rock beat God?"
"It's the rock from the Omnipotence Paradox."
"Oh, that rock. I see."

  1. In the original game, the so called optimal strategy is, as Alban said, to pick each sign with equal probability. But what happens when you make the modification that winning with rock gives two points? What distribution should you use to be "optimal"?
  2. How about the five-sign game, Rock-Paper-Scissors-Lizard-Spock? With equal points, the optimal strategy is again of course to use equal distribution, but what if winning with rock scores double?
  3. Finally, Bengt's own invention. Now we give one point per win again. What is the optimal distribution?
  4. Alban is of course right in saying that you are unlikely to play even, after a large number of games. After n games, what is the expectation value of the (absolute) point difference?

2010-09-18

Easy Month: How to Start a Rebellion

Alban is trying to convince Bengt to play a table-top role-playing game, one of those things with lots of little warlike figurines.

"This guy doesn't like your leadership, he's decided to start a rebellion." says Bengt.
"What? No he hasn't."
"Has too."
"Well, he can't do anything about it, because the other orcs will blow his head off if they find out."
"Aren't the orcs supposed to be some kind of fantasy monster kind of guys? You mean they have guns?"
"They sure do, and they don't like traitors."
"But they're also not happy with the way that guy in black is pushing them around. In fact, out of the n soldiers, I believe a fraction k (so k*n soldiers) would like to join the rebellion."
"Oh really. But in that case, there are also p*n soldiers who would kill those rebels if they knew about it."
"Why p?"
"I don't know, p for… peace? No, I know: Police."
"Haha, yeah, okay."
"What, why did you pick k?"
"K for constant, duh. Anyway, that leaves a fraction 1-p-k, let's call it… r, for remaining. A total of r*n soldiers who couldn't care less."
"Or at least they don't care very much. It might be that they care slightly, but not enough."
"True. So, each of the instigators of the rebellion…"
"…who are infinitesimally few compared to n…"
"…but many compared to 1/k, he asks one other orc at a time whether he would like to join the revolution. If it's a k-type guy, he joins, and goes on to ask other random guys. If it's a p-type, he shoots the guy for asking. If it's an r-type, he just says no."
"And how does it end?"
"Well, the rebels keep track of the opinions of all the guys they have previously asked, so they don't ask them again. When they have asked everyone, they start the rebellion."
"Do you think they can win?"
"That's not part of the question."

  1. What conditions must p and k satisfy for the rebellion to spread?
  2. Suppose the potential rebels (the k-guys) are not so keen on getting shot, so they only agree to asking two other random guys. What are the conditions?
  3. As in a, but suppose when a rebel asks a p-guy, they both have equal chances of shooting the other guy.
  4. As in c, but as in b, not as in a.
  5. As in d, but now suppose if the asking guy gets shot, the rebels don't know who the askee was, so they will eventually ask him again.
  6. Sort of like in a, but now the rebels are a little more cautious: The instigators all know each other, but each new rebel knows only the identity of his recruiter (and recruitees). Each day, each rebel who has not already asked q people ask one more. They might therefore ask a guy who has actually already joined, in which case that guy thus effectively has another recruiter. If a rebel asks a p-guy, they both get shot. If a rebel has no recruiters still alive, he loses contact with the group and reverts to the same state as before he joined (also resetting his asking quota). When the instigators determine that half the soldiers have been asked, they start the rebellion. What should q be in order to make the rebellion likely to happen?
    (This one might be more difficult. You can solve it next month, if you like.)

2010-09-07

Easy Month: Jumping in the Lift

Bengt is watching "QI" on BBC. It's the kind of show which really gets Bengt going, because he doesn't want to accept that people know things he doesn't.
The show brings up the old myth of the falling lift - that if you are in a lift, and the cable snaps so that the lift falls, you can save yourself by jumping just before the lift hits the ground. Since you are not standing on the lift floor when it hits the ground, you would supposedly be unaffected by the impact. Bengt doesn't believe in the myth, of course, and has nothing but contempt for anyone who does. But still, it gets him thinking.

By jumping just before impact, you would after all get a certain speed upward, to be added to the speed downward which you already have. How high can a person jump? Bengt looks for the world record for standing high jump; his sources claim that it is 1.914 m. This, incidentally, very closely matches the height of Stephen Fry, the host of the show. Bengt pictures one Stephen Fry jumping over another Stephen Fry, and finds the image very amusing. Now, that record isn't for the center of mass, and we can't expect an average lift jumper to match the world record anyway, so Bengt decides a person can jump 1 m, for physics purposes.

How high would the lift fall? Not every lift goes up hundreds of meters, Bengt reasons. Suppose you fall 4 storeys. How high is a storey? Well, Bengt thinks, it should be high enough that Stephen Fry wouldn't bump his head if he jumped, so that makes 2.914 m. (Bengt is forgetting that floors aren't infinitely thin, but it doesn't matter.) In the lift, hitting your head on the ceiling shouldn't be a problem, if you jump at the right moment.

Bengt realises that this problem would be tricky to solve without a calculator, and therefore gives you the extra clue that (2*√(2.914)-1)^2 / 2 = 2.914.

  1. The impact after jumping would be equivalent to falling from a slightly lower height. How many storeys might that be?
  2. The show claims that the best thing to do is to lie down on a fat person to cushion your fall. Why might it be tricky to lie down in a falling lift?
  3. A lot of people are afraid of lifts, partly because they think that the cable might snap and the lift fall down. In fact, this is extremely unlikely. In the year 2000, modern lifts had been around for about 150 years, and there were 6 milliard people in the world. According to Bengt's mysterious sources, there was one lift per 1000 people, and the average lift made 200 transportations of people per day. By assuming that the lifts were built at constant speed - the number increased linearly from 1850 to 2000 - Bengt is able to calculate the risk of such an accident happening to a given person on a given lift ride; it is 0.000000000003%, making the modern cable lift probably the safest vehicle ever invented.
    How many times had such an accident happened?

2010-09-02

Easy Month: A Ton of Feathers

It's time for another of the fabled Theme Months, and this month, despite lack of better judgement, Bengt has decided to do something truly wild and uncharacteristic and give you some problems that are in fact not insanely difficult! Let us savour the moment. The idea is that these problems should be possible to solve not only without a degree in science, but also without a calculator.

There's an old joke which goes: "Which is heavier, a ton of lead or a ton of feathers? Drop it on your toes and you'll see!" Now, for some reason, Bengt has got himself a big cube of some sort of fabric material stuffed with feathers. He's has some vague plans of using it in a giant board game, but for now, he amuses himself by dropping it on his feet. There's no need to worry; it doesn't hurt at all. But having a scientific and somewhat peculiar mind, he wants to find out just how fast the cube is falling when it hits his foot. The cube is 1 m high, and we can ignore air friction and the height of Bengt's toes.

  1. Suppose Bengt drops the cube from 1m. What is the speed when it hits his toes?
  2. Suppose instead that he balances the cube on its edge, and lets it fall. At which speed will the fastest part of the cube move when it hits his toes?
  3. Suppose he instead balances it on a corner?
  4. If you put them on a pair of (very large) scales, which would seem to be heavier, a ton of lead or a ton of feathers?