Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 6.8 National olympiad Prove it North Macedonia

We define a grid of type (n1,n2,...,nm)(n_1, n_2, ..., n_m), n1n2...nmn_1 \ge n_2 \ge ... \ge n_m in the following way: we put n1n_1 squares horizontally, one next to each other, then we put n2n_2 squares horizontally under the first n1n_1 squares. We repeat the procedure until we get a grid of squares having n1n_1 squares in the first row, n2n_2 in the second, nin_i in the ii-th row, so that in the end n=n1+n2+...+nmn = n_1 + n_2 + ... + n_m squares are formed. The rows are left-aligned, as in the example. We fill out this grid with the numbers from 1 to nn in such a way that the numbers form an increasing sequence in each row (from the leftmost square to rightmost square) and in each column (from the uppermost square to the lowermost square). An example for such a grid of type (5,4,2,1) filled out in one possible way is:
Figure 1

Find the number of possibilities to fill out a grid of type (4,3,2)!

Solution

We define a function ff on the mm-tuples (n1,n2,...,nm)(n_1, n_2, ..., n_m) in the following way: f(n1,n2,...,nm)=0f(n_1, n_2, ..., n_m) = 0 for the mm-tuples for which it does not hold that:
n1n2nm0.(1) n_1 \ge n_2 \ge \dots \ge n_m \ge 0. \tag{1}
If n1n2nm0n_1 \ge n_2 \ge \dots \ge n_m \ge 0, then it holds that
f(n1,n2,,nm,0)=f(n1,n2,,nm).(2) f(n_1, n_2, \dots, n_m, 0) = f(n_1, n_2, \dots, n_m). \qquad (2)
f(n1,n2,,nm)=f(n11,n2,,nm)+f(n1,n21,,nm)++f(n1,n2,,nm1).(3) f(n_1, n_2, \dots, n_m) = f(n_1 - 1, n_2, \dots, n_m) + f(n_1, n_2 - 1, \dots, n_m) + \dots + f(n_1, n_2, \dots, n_m - 1). \quad (3)
f(n)=1, for n0.(4) f(n) = 1, \text{ for } n \ge 0. \qquad (4)
The function ff is well-defined. We will show that f(n1,n2,,nm)f(n_1, n_2, \dots, n_m) is the number of grids of type (n1,n2,,nm)(n_1, n_2, \dots, n_m). It is clear that conditions (1) and (4) must be fulfilled for the required grid (a row of nn squares can be filled in a unique way with nn numbers such that they form an increasing sequence :1,2,3,,n:1, 2, 3, \dots, n). Condition (2) is also clear. To show that a grid of type (n1,n2,,nm)(n_1, n_2, \dots, n_m) satisfies condition (3), we consider the number nn. That number has to be the last number in one of the rows, so if we delete the square having number nn, we get a grid with n1n-1 numbers that fulfills the conditions of the problem. It can happen that several rows may have the same number of squares so that the number nn can be in the last row in the rightmost square. If, for example, n1=n2n_1=n_2, then f(n11,n2,,nm)=0f(n_1-1, n_2, \dots, n_m) = 0 since n11<n2n_1-1 < n_2. Therefore in condition (3) all expressions
f(n11,n2,,nm),f(n1,n21,,nm),,f(n1,n2,,nm1) f(n_1-1, n_2, \dots, n_m), f(n_1, n_2-1, \dots, n_m), \dots, f(n_1, n_2, \dots, n_m-1)
appear, which are zero if the above condition holds.
We use the previously-defined function ff to get the number of grids of type (4,3,2)(4,3,2).

f(4,3,2)=f(3,3,2)+f(4,2,2)+f(4,3,1)==(f(3,2,2)+f(3,3,1))+(f(3,2,2)+f(4,2,1))+(f(3,3,1)+f(4,2,1)+f(4,3,0))==2f(3,2,2)+2f(3,3,1)+2f(4,2,1)+f(4,3)==2(f(2,2,2)+f(3,2,1))+2(f(3,2,1)+f(3,3,0))+2(f(3,2,1)+f(4,1,1)+f(4,2,0))+(f(3,3)+f(4,2))==2f(2,2,2)+6f(3,2,1)+2f(4,1,1)+3f(4,2)+3f(3,3)==2(f(2,2,1))+6(f(2,2,1)+f(3,1,1)+f(3,2,0))+2(f(3,1,1)+f(4,1,0))+3(f(3,2)+f(4,1))+3(f(3,2))==8f(2,2,1)+8f(3,1,1)+12f(3,2)+5f(4,1)==8(f(2,1,1)+f(2,2,0))+8(f(2,1,1)+f(3,1,0))+12(f(2,2)+f(3,1))+5(f(3,1)+f(4,0))==16f(2,1,1)+20f(2,2)+25f(3,1)+5f(4)==16(f(1,1,1)+f(2,1,0))+20(f(2,1))+25(f(2,1)+f(3,0))+5==16f(1,1,1)+61f(2,1)+25f(3)+5=16(f(1,1,0))+61(f(1,1)+f(2,0))+25+5==77f(1,1)+61f(2)+30=77(f(1,0))+61+30=77f(1)+91=77+91=168.\begin{align*} f(4,3,2) &= f(3,3,2) + f(4,2,2) + f(4,3,1) = \\ &= (f(3,2,2) + f(3,3,1)) + (f(3,2,2) + f(4,2,1)) + (f(3,3,1) + f(4,2,1) + f(4,3,0)) = \\ &= 2f(3,2,2) + 2f(3,3,1) + 2f(4,2,1) + f(4,3) = \\ &= 2(f(2,2,2) + f(3,2,1)) + 2(f(3,2,1) + f(3,3,0)) + 2(f(3,2,1) + f(4,1,1) + f(4,2,0)) + (f(3,3) + f(4,2)) = \\ &= 2f(2,2,2) + 6f(3,2,1) + 2f(4,1,1) + 3f(4,2) + 3f(3,3) = \\ &= 2(f(2,2,1)) + 6(f(2,2,1) + f(3,1,1) + f(3,2,0)) + 2(f(3,1,1) + f(4,1,0)) + 3(f(3,2) + f(4,1)) + 3(f(3,2)) = \\ &= 8f(2,2,1) + 8f(3,1,1) + 12f(3,2) + 5f(4,1) = \\ &= 8(f(2,1,1) + f(2,2,0)) + 8(f(2,1,1) + f(3,1,0)) + 12(f(2,2) + f(3,1)) + 5(f(3,1) + f(4,0)) = \\ &= 16f(2,1,1) + 20f(2,2) + 25f(3,1) + 5f(4) = \\ &= 16(f(1,1,1) + f(2,1,0)) + 20(f(2,1)) + 25(f(2,1) + f(3,0)) + 5 = \\ &= 16f(1,1,1) + 61f(2,1) + 25f(3) + 5 = 16(f(1,1,0)) + 61(f(1,1) + f(2,0)) + 25 + 5 = \\ &= 77f(1,1) + 61f(2) + 30 = 77(f(1,0)) + 61 + 30 = 77f(1) + 91 = 77 + 91 = 168. \end{align*}

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 and solution reproduced as published; topic and difficulty added by this site.