Daniel Martin

We visited family in northern Wisconsin over New Year's, and one of the things that happened there is that we were introduced to the show "The Big Bang Theory", and I watched the whole first season on DVD.

So we've been working our way through the second season's DVDs here the past few weeks. As you may know if you've seen the show, in one episode this season they introduce the game of "Rock, Paper, Scissors, Lizard, Spock" (a game originally described here as "Rock Paper Scissors Spock Lizard"), an extension of "Rock, Paper, Scissors". (I'm going to call this game "RPSSL" in this post)

This got me thinking more generally about extensions to "Rock, Paper, Scissors", (hereafter, RPS) so let me define:

A degree-n RPS extension, where n is an odd number >= 3, is a two-player game in which players secretly select one of n symbols and then simultaneously reveal their choices; assuming the player selected differently from each other, the winner of the game is determined by the game's ruleset. The ruleset of an RPS extension must specify that every token wins against (n-1)/2 of the other tokens, and loses against the other (n-1)/2 tokens.

So RPSSL is a degree-5 RPS extension, because for any choice player A makes, exactly two choices for player B will let A win (and exactly two will let B win).

Two RPS extensions are equivalent if you can obtain one from the other merely by renaming tokens.

So here's what I've come up with:

• There's at least one degree-n RPS extension for every odd n >= 3.
  
• Up to equivalency, there's only one degree-5 RPS extension.
  
• Up to equivalency, there are at most two degree-7 RPS extensions.

I need to work more with the two different degree-7 extensions I have to prove that they definitely aren't equivalent. Getting some paper and writing it down would probably help, rather than trying to just keep it in my head.

For the other two points, I'll just note that if you re-arrange the tokens in RPSSL into the order:

Rock, Spock, Paper, Lizard, Scissors

And imagine those tokens in a circle, then every token loses to the two tokens that immediately follow it and beats the two that immediately precede it. This shows a general pattern that can work for any n and working out that with five tokens, there must be such an order proves the second point.

Okay, haven't posted in two whole months, I haven't told you what it's like working at Google since the first day, etc. I will say that my lack of blogging here has absolutely nothing to do with my internal-to-Google blog, since I haven't actually signed up for that either.

And this post isn't going to interest most of you who have me on your friends list, but if I waited for that, it'll be another two months or more before I post anything again. So here's a post on something I was thinking about this morning.

I was reading through some of Steve Yegge's old blog ("who is he?", you ask? He's just this guy that used to work at Amazon, now works for Google, and had an Amazon-internal blog that he made mostly public after leaving Amazon. Some of it's interesting) about interviewing programmers and he gave this as an example of the naive solution to the problem "find the nth Fibbonacci number":

static long fib(int n) {
  return n <= 1 ? n : fib(n-1) + fib(n-2);
}

One of the comments noted that they'd expect any candidate to be able to tell that that implementation as it stands is O(2ⁿ).

That didn't feel right to me - I mean, clearly it is O(2ⁿ) in the sense that big O provides an upper bound, but it's not a tight bound - that is, it isn't ϴ(2ⁿ). So what is a tight bound?

It turns out that this algorithm is actually ϴ(fib(n)), which is to say that it's ϴ(φⁿ), where φ is the golden ratio (1 + √5)/2.

Why is this? Well, I think I'll leave that as an exercise for the reader, or maybe I'll add it later to this post underneath a cut tag. Suffice it to say that there's a nice recurrence relation that defines the number of invocations of fib necessary to calculate the nth Fibbonacci number, and that it requires a bit of fiddling after that, but not too much.

Anyway, that's something I was thinking about this morning.

So in the effort to get me posting about anything, and prevent my journal from idling for another month, I'm going to talk about a toy I bought myself on eBay a few weeks ago.

It's a slide rule.

It's a moderately nice one, though the sight on it is slightly askew, such that if I don't touch it, the line isn't quite vertical. It's only a 10 inch model; the really accurate 20-inch and longer ones aren't selling on eBay, or are too pricey.

It has scales L, C, D, A, B, K, Ci, CF, DF, CiF, S, T, ST, LL1, LL2, LL3, LLO, and LLOO.

Just think - there was a time when every engineering student would know what all of those scales meant. I've included a discussion of what those scales mean, and what it means I can compute with this, below the cut.
( The rest gets rather math-heavy )

A math problem vaguely inspired by life:

Say you have to walk from point A to point B. Now, the catch is that you have to take each step so as to not wake the baby sleeping at point A. If you wake her, you have to go back to point A and spend the time during which you could take n steps comforting her until she goes back to sleep. The probability of the baby waking during any step is equal to the portion of the distance covered during that step - in other words, if you try to go from A to B in one step, she'll certainly awaken (longer steps are louder, you see). If you try to take it in two equal-sized steps, you have a 1/4 chance of making it across.

Now, you're trying to get to point B as quickly as possible. (Assume that each step takes the same amount of time). What's your optimal strategy? What is the expected number of steps taken?

First take this problem with n = 0; that is, the only penalty for waking the baby is that you have to start over from point A.

What if we change things so that the probability of her waking is equal to k times the portion of the distance covered? (So that for k=2, she is certain to wake if we try to cover half the distance in a single step)

So the gospel lesson this week was Mark 6:30-44 which says in part:

³⁸ And he said to them, How many loaves have you? Go and see. And when they knew, they say, Five, and two fishes. ³⁹ And he commanded them to make them all sit down, arranging the guests on the green grass. ⁴⁰ And they sat down, arranged in hundreds, and fifties. ⁴¹ And when he had taken the five loaves and the two fishes, raising his eyes to heaven, he blessed, and brake the loaves, and gave to the disciples to set before them, and divided the two fishes among them all. ⁴² And they all ate, and were satisfied. ⁴³ And they carried away twelve baskets full of the fragments and of the fishes. ⁴⁴ Now they who had eaten were about five thousand men.

So there you have it - Biblical justification for the axiom of choice. I don't know why the connection hadn't occurred to me before.