Maths Olympiad Prep

Library / /644 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

A 5×55 \times 5 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)?

A number or a short expression. Spacing and $ signs are ignored.

Solution

250 If the square in row ii, column jj contains the number kk, let its 'index' be i+jki+j-k. The constraint on adjacent squares now says that if a square has index rr, the squares to its right and below it each have index rr or r+2r+2. 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 (105)=252\binom{10}{5}=252 paths, but two are impossible, so the answer is 250.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.