3

Part of 2007 Putnam

Problems(2)

Source:

k

be a positive integer. Suppose that the integers 1,2,3,\dots,3k \plus{} 1 are written down in random order. What is the probability that at no time during this process, the sum of the integers that have been written up to that time is a positive integer divisible by

3

? Your answer should be in closed form, but may include factorials.

Putnamprobabilitycountingdistinguishabilityfactorialfunctionbinomial coefficients

Source:

Let x_0 \equal{} 1 and for

n\ge0,

let x_{n \plus{} 1} \equal{} 3x_n \plus{} \left\lfloor x_n\sqrt {5}\right\rfloor. In particular, x_1 \equal{} 5,\ x_2 \equal{} 26,\ x_3 \equal{} 136,\ x_4 \equal{} 712. Find a closed-form expression for

x_{2007}.

\lfloor a\rfloor

means the largest integer

\le a.

Putnamfloor functionlogarithmscalculusintegrationfunctioninduction