Maths Olympiad Prep

Library / /671 of 740

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

An 88 by 88 grid of numbers obeys the following pattern:

1) The first row and first column consist of all 11s.

2) The entry in the iith row and jjth column equals the sum of the numbers in the (i1)(i-1) by (j1)(j-1) sub-grid with row less than ii and column less than jj.

What is the number in the 88th row and 88th column?

Solution

Solution:

Answer: 25082508

Let xi,jx_{i, j} be the number in the iith row and the jjth column. Then if i,j2i, j \geq 2, xi+1,j+1xi+1,jxi,j+1+xi,jx_{i+1, j+1} - x_{i+1, j} - x_{i, j+1} + x_{i, j} only counts the term xi,jx_{i, j} since every other term is added and subtracted the same number of times. Thus xi+1,j+1=xi+1,j+xi,j+1x_{i+1, j+1} = x_{i+1, j} + x_{i, j+1} when i,j2i, j \geq 2. Also, x2,i=xi,2=ix_{2, i} = x_{i, 2} = i so xi+1,j+1=xi+1,j+xi,j+1x_{i+1, j+1} = x_{i+1, j} + x_{i, j+1} holds for all i,j1i, j \geq 1 except for (i,j)=(1,1)(i, j) = (1,1) where x2,2x_{2,2} is one less than expected. This means that xi,jx_{i, j} is the number of ways of travelling from (1,1)(1,1) to (i,j)(i, j), minus the number of ways of travelling from (2,2)(2,2) to (i,j)(i, j), which is (147)(126)=2508\binom{14}{7} - \binom{12}{6} = 2508.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.