I haven’t put up a contest problem in a while but this one is just fantastic. This is one of the prettiest problems I have seen lately; although it looks very messy at first, it has a clean solution. This comes from 1986 NYSML power round.

Let F(r,c) be defined for all nonnegative integers r,c>=0, according to the following rules:

1) F(r,0) = 1 for r >=0

2) F(r,c) = 0 when c>r

3) If F(r,c) = F(r,c+1), then F(r+1,c+1) = 0

4) If F(r,c) not equal F(r, c+1), then F(r+1,c+1) = 1

I a)Complete the entries on the printed table for 0<= r,c <=10.

b)Compute the value of each of the following: F(1986,1), F(1986,2), F(1986,1986), F(1986,993)

II a) Prove: If 0 <= c <= r, then F(r,c) = F(r,r-c).

b) Prove: If r = 2m+1 is odd then F(r,0) + F(r,2) +…+F(r,2m) = F(r,1) + F(r,3) +…+F(r,2m+1).

c) Let S_r be the sum of the entries in row r. Form and prove a conjecture about the value of S_r.

III a) Compute the sum of the entries in row r, where r = 2^100+1

b) Compute all values of r where 7<=r<=63, for which S_r = 8

c) Compute S_1934.

Written

on April 1, 2014