$
\def\r#1{\textcolor{red}{#1}}
\def\arr{\quad{\leftrightarrow}\quad}
\colsep{0pt}{\begin{array}{ll}
4=\r4\\
4=\r3+1&\arr1=1\\
4=\r2+2&\arr2=2\\
4=\r2+1+1&\arr2=1+1\\
4=\r1+3&\arr3=3\\
4=\r1+2+1&\arr3=2+1\\
4=\r1+1+1+1&\arr3=1+1+1
\end{array}}$
а) Разбиение числа $n$ в сумму натуральных слагаемых будем называть отмеченным, если одно из слагаемых выделено среди остальных (подчёркнуто); отмеченные разбиения, отличающиеся только порядком слагаемых, мы будем считать одинаковыми. (На рисунке изображены все отмеченные разбиения числа 4; выделенные слагаемые показаны красным цветом.) Заметим, что если $k$ — разброс некоторого разбиения (неотмеченного), то из этого разбиения можно получить ровно $k$ отмеченных разбиений. Поэтому общее количество отмеченных разбиений числа $n$ равно $q(n)$. С другой стороны, если из любого отмеченного разбиения, кроме разбиения, состоящего из единственного слагаемого, выкинуть подчёркнутый элемент, получится разбиение некоторого числа, меньшего чем $n$. И наоборот, если $m\lt n$, то по любому разбиению числа $m$ можно однозначно восстановить отмеченное разбиение числа $n$: надо к разбиению числа $m$ добавить слагаемое $n-m$ и подчеркнуть его (на рисунке изображено взаимно-однозначное соответствие между отмеченными разбиениями числа 4, кроме разбиения $4=4$, и разбиениями чисел, меньших 4). Но количество разбиений чисел, меньших $n$, равно $p(1)+p(2)+\ldots+p(n-1)$. Следовательно, $q(n)-1=p(1)+p(2)+\ldots+p(n-1)$.
Другими словами идею этого решения можно изложить так: если к каждому из $p(1)+p(2)+\ldots+p(n-1)$ разбиений чисел $m=1$, 2, $\ldots$, $n-1$ добавить одно слагаемое $n-m$, то мы получим каждое разбиение числа $n$ (кроме тривиального $n=n$) столько раз, каков его разброс.
б) Достаточно доказать, что разброс любого разбиения числа $n$ в сумму натуральных слагаемых не превосходит $\sqrt{2n}$. Докажем это утверждение. Пусть $a_1$, $\ldots$, $a_k$ — все различные слагаемые, входящие в некоторое разбиение (с разбросом $k$), причём $0\lt a_1\lt\ldots\lt a_k$. Тогда, с одной стороны, $a_1+a_2+\ldots+a_k\le n$, а с другой стороны, $a_1\ge1$, $a_2\ge2$, $\ldots$, $a_k\ge k$ (действительно, $a_1\ge1$; $a_2\gt a_1\ge1$, следовательно, $a_2\ge2$; $a_3\gt a_2\ge2$, следовательно, $a_3\ge3$, и т. д.). Поэтому $$n\ge a_1+a_2+\ldots+a_k\ge1+2+\ldots+k=\dfrac{k(k+1)}{2}\ge\dfrac{k^2}2,$$ т. е. $k\le\sqrt{2n}$.
