Maths Olympiad Prep

Library / /164 of 377

Combinatorics Difficulty 5.0 AIME, harder Prove it United States

Problem:
Find the number of solutions in positive integers (k;a1,a2,,ak;b1,b2,,bk)\left(k ; a_{1}, a_{2}, \ldots, a_{k} ; b_{1}, b_{2}, \ldots, b_{k}\right) to the equation
a1(b1)+a2(b1+b2)++ak(b1+b2++bk)=7. a_{1}\left(b_{1}\right)+a_{2}\left(b_{1}+b_{2}\right)+\cdots+a_{k}\left(b_{1}+b_{2}+\cdots+b_{k}\right)=7 .

Solution

Solution:
Let k,a1,,ak,b1,,bkk, a_{1}, \ldots, a_{k}, b_{1}, \ldots, b_{k} be a solution. Then b1,b1+b2,,b1++bkb_{1}, b_{1}+b_{2}, \ldots, b_{1}+\cdots+b_{k} is just some increasing sequence of positive integers. Considering the aia_{i} as multiplicities, the aia_{i}'s and bib_{i}'s uniquely determine a partition of 77. Likewise, we can determine aia_{i}'s and bib_{i}'s from any partition of 77, so the number of solutions is p(7)=15p(7)=15.

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.