Maths Olympiad Prep

Library / /545 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

How many 48-tuples of positive integers (a1,a2,,a48)\left(a_{1}, a_{2}, \ldots, a_{48}\right) between 0 and 100 inclusive have the property that for all 1i<j48,ai{aj,aj+1}1 \leq i<j \leq 48, a_{i} \notin\left\{a_{j}, a_{j}+1\right\} ?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

(With Ashwin Sah) The key idea is write the elements of the sequence in increasing order. These sets are in bijection with solutions to d1++dk=48d_{1}+\ldots+d_{k}=48 and a1++ak+1=53a_{1}+\ldots+a_{k+1}=53 with di1,ai1d_{i} \geq 1, a_{i} \geq 1 for 2Ik2 \leq I \leq k, and a1,ak+10a_{1}, a_{k+1} \geq 0. Notice that there are (54k)\binom{54}{k} solutions to the second equation and then there are 48!d1!dk!\frac{48!}{d_{1}!\cdots d_{k}!} solutions for each {di}\left\{d_{i}\right\} set. Then this gives that the answer is 1k48(54k)d1++dk=4848!i=1kdi!=48![x48]1k48(ex1)k(54k)=48![x48]0k54(ex1)k(54k)=48![x48](ex)54=5448\sum_{1 \leq k \leq 48}\binom{54}{k} \sum_{d_{1}+\ldots+d_{k}=48} \frac{48!}{\prod_{i=1}^{k} d_{i}!} =48!\left[x^{48}\right] \sum_{1 \leq k \leq 48}\left(e^{x}-1\right)^{k}\binom{54}{k} =48!\left[x^{48}\right] \sum_{0 \leq k \leq 54}\left(e^{x}-1\right)^{k}\binom{54}{k} =48!\left[x^{48}\right]\left(e^{x}\right)^{54} =54^{48}.

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.