Harvard-MIT Mathematics Tournament #0i9l

Harvard-MIT Mathematics TournamentHard

Community difficultyNo ratings yetBe the first to rate this problem.

Understand the scale

Scale 0.5: Easiest math competition problems, often solvable even for early middle school students without experience. 1: Problems strictly for beginners, often at a moderate middle school level. 1.5: Problems for stronger beginner students, on the level of the middling problems in most middle school contests. 2: For motivated beginners, harder questions from the previous categories. 2.5: More advanced beginner problems, hardest questions from previous categories. 3: Early intermediate problems that require more creative thinking. 3.5: Tougher early intermediate problems that consistently stretch into higher-level creative thinking or conceptual knowledge. 4: Intermediate-level problems. 4.5: Upper intermediate problems approaching the upper bound for non-invitational sprint math competitions. 5: More difficult AIME problems or simple proof-based Olympiad-style problems. 6: High-level AIME-styled questions or introductory Olympiad-level questions. 7: Tougher Olympiad-level questions, may require more technical knowledge. 8: High-level Olympiad-level questions. 9: Expert Olympiad-level questions. 9.5: The hardest problems appearing on Olympiads which the strongest students could reasonably solve. 10: Historically notorious problems, generally unsuitable for even very hard competitions because they are exceedingly tedious, long, and difficult.

Problem

Problem:

A partition of a number $n$ is a sequence of positive integers, arranged in descending order, whose sum is $n$ . For example, $n=4$ has 5 partitions: $1+1+1+1=2+1+1=2+2=3+1=4$ . Given two different partitions of the same number, $n=a_{1}+a_{2}+\cdots+a_{k}=b_{1}+b_{2}+\cdots+b_{l}$ , where $k \leq l$ , the first partition is said to dominate the second if all of the following inequalities hold:

\begin{aligned} a_{1} & \geq b_{1} ; \\ a_{1}+a_{2} & \geq b_{1}+b_{2} ; \\ a_{1}+a_{2}+a_{3} & \geq b_{1}+b_{2}+b_{3} ; \\ & \vdots \\ a_{1}+a_{2}+\cdots+a_{k} & \geq b_{1}+b_{2}+\cdots+b_{k} . \end{aligned}

Find as many partitions of the number $n=20$ as possible such that none of the partitions dominates any other. Your score will be the number of partitions you find. If you make a mistake and one of your partitions does dominate another, your score is the largest $m$ such that the first $m$ partitions you list constitute a valid answer.