[tc11][T11/504 Toán học & tuổi trẻ số 504, tháng 6 năm 2019] Cho số nguyên dương $k\geq 2$ và số nguyên dương $n\geq\dfrac{k(k+1)}{2}$. Tìm số nguyên dương $m$ lớn nhất để trong $n$ số nguyên dương phân biệt bất kì không vượt quá $m$ luôn tồn tại $k+1$ số phân biệt mà một số bằng tổng của $k$ số còn lại.

Lời giải

Ta thấy $m\geq n\geq k$. Xét $n$ số nguyên dương $m-n+1$, $m-n+2$, $\cdots$, $m-n+k$,$\cdots$, $m$. Tổng của $k$ số phân biệt nhỏ nhất bằng $$m-n+1+m-n+2+\cdots+m-n+k=k(m-n)+\dfrac{k(k+1)}{2}$$ suy ra $$m\geq k(m-n)+\dfrac{k(k+1)}{2}\Leftrightarrow (k-1)m\leq kn-\dfrac{k(k+1)}{2}\Leftrightarrow m\leq\dfrac{kn}{k-1}-\dfrac{k(k+1)}{2(k-1)}.$$ Suy ra $m\leq\left\lfloor\dfrac{kn}{k-1}-\dfrac{k(k+1)}{2(k-1)}\right\rfloor$. Ta sẽ chứng minh $m=\left\lfloor\dfrac{kn}{k-1}-\dfrac{k(k+1)}{2(k-1)}\right\rfloor$ thỏa mãn đề bài. Thật vậy, giả sử $a_1 < a_2 < \cdots < a_n$ là các số nguyên dương không vượt quá $m$. Đặt $$s=\left\lfloor\dfrac{m-n-1}{k-1}\right\rfloor +1+k.$$ Ta có $$s-k=\left\lfloor\dfrac{m-n-1}{k-1}\right\rfloor +1 > \dfrac{m-n-1}{k-1}.$$ Suy ra $$(s-k)(k-1) > m-n-1\Rightarrow (s-k)(k-1)\geq m-n\Rightarrow s\geq\dfrac{m-n}{k-1}+k.$$ Gọi $t$ là số nguyên nhỏ nhất sao cho $t(s-k)\geq m-n$ thì $t\leq k-1$ và $(t-1)(s-k) < m-n$. Đặt $$p=(m-n)-(t-1)(s-k)+k-t+1=(m-n)-t(s-k)+s-t+1$$ thì $k-t+1 < p\leq s-t+1$. Xét các số nguyên dương $$a_n-a_1 > a_{n+1}-a_1 > \cdots > a_2-a_1$$ và $$\begin{align*} a_2+a_3+\cdots+a_{k-1}+a_k& < a_2+a_3+\cdots+a_{k-1}+a_{k+1} < \cdots < \\ & < a_2+a_3+\cdots+a_{k-2}+a_{k-1}+a_s < a_2+a_3+\cdots+a_{k-2}+a_{k}+a_s\\& < \cdots < a_2+a_3+\cdots+a_{k-3}+a_{k-2}+a_{s-1}+a_s\\& < a_2+a_3+\cdots+a_{k-3}+a_{k-1}+a_{s-1}+a_s\\& < \cdots < a_2+a_3+\cdots+a_{k-3}+a_{s-2}+a_{s-1}+a_s\\& < \cdots < a_2+\cdots+a_{k-t}+a_{k-t+2}+a_{s-t+2}+\cdots+a_s\\& < \cdots < a_2+\cdots+a_{k-t}+a_{p}+a_{s-t+2}+\cdots+a_s. \end{align*}$$ Số các số đang xét là $(n-1)+(t-1)(s-k)-1+(p-k+t+1)=m$. Ta có $$a_n-a_i=(a_n-a_{n-1})+(a_{n-1}-a_{n-2})+\cdots +(a_{i+1}-a_i)\geq n-i.$$ Suy ra $a_i\leq a_n-n+i\leq m-n+i$ với mọi $i=1,2\cdots,n-1$. Do đó, $$\begin{align*} &a_2+\cdots+a_{k-t}+a_p+a_{s-t+2}+\cdots+a_s\\\leq& (k-1)(m-n)+2+\cdots+(k-t)+p+(s-t+1)+\cdots+s\\ =&(k-1)(m-n)+\dfrac{(k-t+2)(k-t-1)}{2}+m-n-t(s-k)+s-t+1+\dfrac{(2s-t+2)(t-1)}{2}\\ =&k(m-n)+\dfrac{k(k+1)}{2}-1\leq m-1. \end{align*}$$ Hơn nữa, $a_n-a_1\leq m-1$. Như vậy $m$ số nguyên dương đang xét không vượt quá $m-1$ nên theo nguyên lí Dirichlet tồn tại hai số bằng nhau. Hai số này phải có dạng $a_i-a_1$ và $$a_{i_1}+a_{i_2}+\cdots+a_{i_{k-1}}$$ với $2\leq i\leq n$ và $2\leq i_1 < i_2 < \cdots < i_{k-1} < s$ nào đó, tức là $$a_i-a_1=a_{i_1}+a_{i_2}+\cdots+a_{i_{k-1}}$$ hay $a_i=a_1+a_{i_1}+a_{i_2}+\cdots+a_{i_{k-1}}$. Khi đó $a_i > a_{i_{k-1}}$ nên $i > i_{k-1}$. Như vậy $k+1$ số $a_1,a_{i_1},a_{i_2},\cdots, a_{i_{k-1}}$ thỏa mãn đề bài. Vậy số nguyên lớn nhất thỏa mãn đề bài là $$m=\left\lfloor\dfrac{kn}{k-1}-\dfrac{k(k+1)}{2(k-1)}\right\rfloor.$$