A square grid has the number -3 written in the upper-left square and the number 3 written in the lower-right square. In how many ways can the remaining squares be filled in with integers so that any two adjacent numbers differ by 1, where two squares are adjacent if they share a common edge (but not if they share only a corner)?
Solution
250 If the square in row , column contains the number , let its 'index' be . The constraint on adjacent squares now says that if a square has index , the squares to its right and below it each have index or . The upper-left square has index 5, and the lower-right square has index 7, so every square must have index 5 or 7. The boundary separating the two types of squares is a path consisting of upward and rightward steps; it can be extended along the grid's border so as to obtain a path between the lower-left and upper-right corners. Conversely, any such path uniquely determines each square's index and hence the entire array of numbers - except that the two paths lying entirely along the border of the grid fail to separate the upper-left from the lower-right square and thus do not create valid arrays (since these two squares should have different indices). Each path consists of 5 upward and 5 rightward steps, so there are paths, but two are impossible, so the answer is 250.