Thursday, November 8, 2007

The Intersection Game

Okay, if you're not mathematically inclined, you might want to bail now.

Let's play a game. Take some closed bounded interval of the real line. Partition this interval between two players. The first player chooses a subset of positive length of the original interval, the second player chooses another subset of positive length of this new interval, and this continues. One wins when a subset is reached which is entirely contained within their interval.

An example. Take [0,1]. We partition it such that I have [0,.5] and you have (.5,1]. Obviously, whoever goes first will win: I'll choose my subset of [0,1] as [0,.3], and if you went first, you might choose [.8,.9]. In either case, this ends the game right away.

Another. Suppose I have {0, 1/2, 1/3, 1/4, 1/5,...} and you have the rest of [0,1]. You'll always win this game, regardless of who goes first.

Suppose you go second. What sort of partition of the interval would you demand to have a chance of winning the game? Hint: A dense set won't always do it, e.g. if you're stuck with the rationals versus the irrationals, you'll always lose.

Interestingly enough, if you choose a random interval, your probability of winning is then 1. A question which I do not have the answer to is when given any interval, how much would you play the game from the first-mover position? The second-mover position?

POSTSCRIPT: My distribution of marks in this course is bizarre. An A+, 3 A's, 3 B's, 1 C, and 3 F's.

POST-POSTSCRIPT: If you want to cheat/learn, see here.

1 comment:

Table Mountains said...

i gave up after the first sentence. i noticed the last line that said, "If you want to cheat/learn, see here."

i did want to cheat so i went to do it. i also gave up after the first sentence i read there.

: )