Olympiad Maths Prep

Track / Stage 5 / 14 of 400 #614 of 2000

Problem 614

AIME late
Combinatorics Difficulty 5.0 Find the answer

1. How many ordered (integer) quadruples (i,j,k,h)(i, j, k, h) satisfy the condition 1i<jk<hn+11 \leqslant i<j \leqslant k<h \leqslant n+1 ?

Official solution

1. The mapping (i,j,k,h)(i,j,k+1,h+1)(i, j, k, h) \rightarrow(i, j, k+1, h+1) is a one-to-one mapping from the set A={(i,j,k,h)1i<jk<hn+1}A=\{(i, j, k, h) \mid 1 \leqslant i<j \leqslant k<h \leqslant n+1\} to the set B={(i,j,k,h)1i<j<k<hn+2}B=\left\{\left(i, j, k^{\prime}, h^{\prime}\right) \mid 1 \leqslant i<j<k^{\prime}<h^{\prime} \leqslant n+2\right\}, so A=B|A|=|B|. And B|B| is clearly the number of four-element subsets of the set {1,2,,n+2}\{1,2, \cdots, n+2\}, which is Cn+24C_{n+2}^{4}. Therefore, A=Cn+24|A|=C_{n+2}^{4}.

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