Maths Olympiad Prep

Library / Harvard-MIT Mathematics Tournament /150 of 352

Harvard-MIT Mathematics Tournament

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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.