Tìm [imath]n[/imath] nhỏ nhất sao cho mọi cách chọn [imath]n[/imath] phần tử rừ tập [imath]{1,2,...,2022}[/imath] đều có 3 phần tử là cạnh của 1 tam giác
UlyanaGọi [imath]n[/imath] phần tử đó là [imath]1\leq a_1 <a_2 < \cdots< a_n\leq 2022[/imath]
Nếu [imath]n\leq 15[/imath], ta luôn chọn được 15 số sao cho không tồn tại 3 cạnh tam giác[imath]1,2,4,7,12,20,33,54,88,143,232,376,609,986,1596[/imath].
Nếu [imath]n\geq 16[/imath], ta sẽ chứng minh [imath]n=16[/imath] là số nhỏ nhất thỏa mãn đề bài.
Giả sử [imath]n=16[/imath], không thỏa mãn. Tức 3 phần tử bất kì trong tập đều không phải cạnh tam giác.
Khi đó, ta có: [imath]a_{k+2} \geq a_{k+1} + a_k + 1[/imath] với mọi [imath]k[/imath] nguyên dương
[imath]\Rightarrow (a_{k+2}+1) \geq (a_{k+1} +1) + (a_k+1)[/imath]
Từ đó, với [imath]a_1 +1 \geq 2 = F_3[/imath], [imath]a_2 +1 \geq 3 =F_4[/imath]
Suy ra [imath]a_n +1 \geq F_{n+2}[/imath] với [imath]F_k[/imath] là số Fibonanci thứ [imath]k[/imath].
[imath]\Rightarrow a_{16} \geq F_{18} -1 >2022[/imath] (trái điều kiện)
Vậy giả sử sai, tức luôn tồn tại 3 phần tử là cạnh tam giác.
Ngoài ra mời bạn tham khảo: [Lý thuyết] Chuyên đề HSG: Toán rời rạc
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
