The proverbial Alice and Bob play a game. A subset S of the closed unit interval, S⊂[0, 1], plays an important role in the game. So let such a subset be fixed.

Alice moves first, choosing any real a₁ in the open interval (0, 1): 0 < a₁ < 1. Bob then chooses b₁ strictly between a₁ and 1: a₁ < b₁ < 1. On subsequent moves, the players must choose a point strictly between the two most recent choices:

n > 0. Letting a₀ = 0 and b₀ = 1, the inequalities apply to n ≥ 1.

Since a monotone increasing sequence {a_n} is bounded from above, it has a limit α = lim_n→∞a_n. &alpha is a well defined real number between 0 and 1. Alice wins the game if α ∈ S. Bob wins if α ∉ S.

A set X is countable if there is a mapping from the set of natural numbers onto X. In other words, X is countable if its elements can be sequenced x₁, x₂, ..., wherein the sequence may or may not be finite. Usually the empty set ø is also considered countable.

Proposition

Proof

If S = ø, the conclusion is immediate. Otherwise, assuming S countable, let S = {s₁, ..., s_k, ...}. The winning strategy for Bob is as follows. For n ≥ 1, he chooses b_n = s_n, if possible. Otherwise, he chooses any legal a_n randomly. Due to this strategy, for each n, either s_n ≤ a_n, or s_n ≥ b_n. Since, for all n, a_n < α < b_n, it follows that α ∉ S, confirming that the strategy is indeed winning for Bob.

Corollary

Proof

For S = [0, 1], Alice always wins!

Reference

1. M. H. Baker, Uncountable Sets and Infinite Real Number Game, in Mathematical Wizardry for a Gardner, A K Peters, 2009

Copyright © 1996-2009 Alexander Bogomolny