A list of \(n\) positive integers \(a_1, a_2,a_3,\ldots,a_n\) is said to be good if it checks simultaneously: \(\bullet a_1<a_2<a_3<\cdots<a_n,\) \(\bullet a_1+a_2^2+a_3^3+\cdots+a_n^n\le 2023.\) For each \(n\ge 1\), determine how many good lists of \(n\) numbers exist.
Problem
Source: Cono Sur 2023 #1
Tags: inequalities, Sum of powers, cono sur
egg185
08.08.2023 02:36
Bump! notice that the good list‘s n can’t be too big. $1^1+2^2+\cdots +n^n \le a_1^1+\cdots +a_n^n$
rilarfer
08.08.2023 02:42
Due to the fact that the positive integers \(a_i\) are distinct for \(i=1,2,\ldots,n\), then \(a_i\ge i\). Then if \(n\ge 5\), then \(a_5^5\ge 5^5>2023\), contradiction. Therefore, \(n\le 4\).
Case \(n=4\). If \(a_4\ge 7, \Rightarrow a_4^4\ge 7^4=2401>2023\), hence \(a_4\le 6\), furthermore
\[a_1+a_2^2+a_3^3+a_4^4\le 3+4^2+5^3+6^4=1440<2023,\]so we only have to select \(4\) elements from the set \(\left\lbrace 1,2,3,4,5,6\right\rbrace\). This is \({6\choose 4}=15\) good lists.
Case \(n=3\). If \(a_3\ge 13, \Rightarrow a_3^3\ge 13^3=2197>2023\), hence \(a_3\le 12\), furthermore
\[a_1+a_2^2+a_3^3 \le 10+11^2+12^3=1859<2023,\]so we only have to select \(3\) elements from the set \(\left\lbrace 1,2,\ldots,11,12\right\rbrace\). This is \({12\choose 3}=220\) good lists.
Case \(n=2\). If \(a_2\ge 45, \Rightarrow a_2^2\ge 45^2=2025>2023\), hence \(a_2\le 44\), furthermore
\[a_1+a_2^2\le 43+44^2=1979<2023,\]so we only have to select \(2\) elements from the set \(\left\lbrace 1,2,\ldots,43,44\right\rbrace\). This is \({44\choose 2}=946\) good lists.
Case \(n=1\), we can choose any number from the set \(\left\lbrace 1,2,\ldots,2022,2023\right\rbrace\). This is \(2023\) good lists.
We conclude that there are: \({6\choose 4}+{12\choose 3}+{44\choose 2}+{2023\choose 1}=3204\) good lists.
YLG_123
19.09.2023 22:08
Similar to CIIM 2023 - Problem 6.