### 54th Putnam 1993

Problem A6

Let a0, a1, a2, ... be a sequence such that: a0 = 2; each an = 2 or 3; an = the number of 3s between the nth and n+1th 2 in the sequence. So the sequence starts: 233233323332332 ... . Show that we can find α such that an = 2 iff n = [αm] for some integer m ≥ 0.

Solution

Let bn be the index of the nth 2, so b0 = 0, b1 = 3, b2 = 7, b3 = 11, b4 = 14, ... . Then we are told that bn = (a0 + 1) + (a1 + 1) + ... + (an-1 + 1). Now each ai = 2 or 3, so bn = 4n - (number of bms in 0, 1, 2, ... , n-1).

Suppose that bn = [nα] as claimed. Then the number of bms in 0, 1, ... , n-1 is the number of [mα] < n, which is the same as the number of (mα) < n (since α is irrational). And that is just 1 + [n/α]. So we have [nα] = 4n - 1 - [n/α]. But 4n - [n/α] = [4n - n/α] + 1 (since n/α is irrational), so [nα] = [4n - n/α] = [nβ], where β = 4 - 1/α. But this holds for all n, so we must have β = α. Solving the quadratic gives α = 2 ± √3. But clearly α > 3, so α = 2 + √3.

We are not done yet. All we have done is shown that if it is true that bn = [nα] for some α, then α must be 2 + √3. But we can work the previous argument in reverse. Suppose we define dn = [n(2 + √3)]. Then the argument shows that dn = 4n - (number of dms in 0, 1, 2, ... , n-1) and that is sufficient to identify dn and bn.