Consider a $10\times 2$ grid of unit squares. Two different squares are adjacent if they share a side. The number of ways in which exactly nine squares can be marked such that no two marked squares are adjacent is k, then k is divisible by

 

       
Case 1) First column is empty
Number of ways = 2 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 = 2
Case 2) Last column is empty
Number of ways = 2 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 = 2
Case 3) Any other column is empty
Number of ways =  (2 x 2 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1) = 32
Total number of ways = 2 + 2 + 32 = 36