1 reply to this topic

[quangminhltv99]

Cho $n\ge 2$ nguyên dương và dãy $(s_i)$ gồm $n$ phần tử. Ta gọi "lớp" của dãy $(s_i)$ là dãy $(a_1,a_2,...,a_{n-1})$ trong đó $a_i$ bằng $1$ nếu $s_{i+1}=s_i$ và bằng $-1$ trong các trường hợp khác.

Tìm số nguyên dương $m$ nhỏ nhất sao cho tồn tại dãy số thực $(w_i)$ có độ dài $m$ sao cho với mọi lớp có thể của dãy có độ dài $n$, tồn tại một dãy con của $(w_i)$ có lớp như thế.

Edited by JUV, 18-12-2016 - 17:32.

[JUV]

Ta sẽ chứng minh bằng quy nạp rằng $m=2n+1$ là giá trị nhỏ nhất cần tìm. Dễ thấy mệnh đề đúng với $n=2$, giả sử mệnh đề đúng với $n=k$. Xét dãy gồm $m$ số $a_1,a_2,...,a_m$ thoả mãn với mọi lớp có thể có độ dài $k+1$, tồn tại một dãy con của dãy đó có lớp như thế. Giả sử $a_1=a_2$, ta xét các lớp có dạng $(-1;i_1;i_2;...;i_k)$ với $i_t\in \left \{ -1;1 \right \}\forall t=\overline{1,k}$ và $a_{t_1};a_{t_2};...;a_{t_{k+2}}$ là dãy có lớp như thế với $t_1<t_2<...<t_{k+2}$. Có $a_{t_1}\neq a_{t_2}$ nên $t_2>2$. Cũng có dãy $a_{t_2};a_{t_3};...;a_{t_{k+2}}$ là một dãy con có lớp $(i_1;i_2;...;i_k)$ và dãy đó là một dãy con của dãy $a_3,a_4,...,a_m$ nên khi cho các số $i_t$ thay đổi tạo thành tất cả các lớp có thể có độ dài $k$ thì dãy $a_3,a_4,...,a_m$ luôn có một dãy con có lớp như thế. Dãy trên gồm $m-2$ số nên theo giả thiết quy nạp thì $m-2\geq 2k+1$ nên $m\geq 2k+3$. Nếu $a_1\neq a_2$ thì lập luận tương tự với lớp độ dài $k+1$ có dạng $(1;i_1;i_2;...;i_k)$ với $i_t\in \left \{ -1;1 \right \}\forall t=\overline{1,k}$, cũng có $m\geq 2k+3$. Vậy giả thiết quy nạp đúng, hay $m\geq 2n+1$. Có thể xét dãy $2n+1$ số sau: $1,0,1,0,1,0,...,0,1$($n+1$ số $1$ và $n$ số $0$ xếp xen kẽ).

Edited by JUV, 18-12-2016 - 17:31.