[ QUOTE ]
[ QUOTE ]
To choose 5 nonadjacent numbers out of 39 to mark with an X rather than an O, choose 5 positions out of 35, then replace the first 4 with XO and the last with X.
[/ QUOTE ]
I agree with this answer. Nice solution, pzhon. Did you think up this method yourself, or have you seen it before?
[/ QUOTE ]
Thanks. I came up with it myself, but I'd be surprised if the argument were new. This problem is a dimension lower than the
hard square problem, which has been studied by many people. The 1-dimensional analogue of the hard square constant is phi = (sqrt(5)+1)/2, since the total number of nonadjacent subsets of {1,...,n} is (n+1 choose 0) + (n choose 1) + (n-1 choose 2) + ... = the n+2nd Fibonacci number.