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.