CombinatoricsDifficulty 5.3AIME, harderFind the answer
How many 48-tuples of positive integers (a1,a2,…,a48) between 0 and 100 inclusive have the property that for all 1≤i<j≤48,ai∈/{aj,aj+1} ?
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=48 and a1+…+ak+1=53 with di≥1,ai≥1 for 2≤I≤k, and a1,ak+1≥0. Notice that there are (k54) solutions to the second equation and then there are d1!⋯dk!48! solutions for each {di} set. Then this gives that the answer is ∑1≤k≤48(k54)∑d1+…+dk=48∏i=1kdi!48!=48![x48]∑1≤k≤48(ex−1)k(k54)=48![x48]∑0≤k≤54(ex−1)k(k54)=4854=5448.
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.