Chủ đề này có 1 trả lời

[Ispectorgadget]

Cho dãy số $\left( {{a}_{n}} \right)$ với $n\in {{N}^{*}}$, gồm các số tự nhiên, được xác định như sau:

${{a}_{1}}=2$,  $\,{{a}_{n+1}}=(n+1){{a}_{n}}+1$, $\forall n\in {{N}^{*}}$.

 

Với mỗi $n\in {{N}^{*}}$, xét ${{a}_{n}}+1$ điểm khác nhau cùng nằm trên một mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Mỗi đoạn thẳng nối hai trong ${{a}_{n}}+1$ điểm này được tô bằng một trong $n$ màu khác nhau. Chứng minh rằng, tồn tại tam giác có đỉnh là ba trong ${{a}_{n}}+1$ điểm đã cho và các cạnh đều được tô cùng một màu.

 

[whatever2507]

Ta CM bài toán bằng quy nạp.

• Với $n=1$ ta có ngay đpcm.
• Giả sử KL đúng đến $n$.
• Xét đồ thị $(n+1)a_n+2$ đỉnh được tô bằng $n+1$ màu $x_1 \rightarrow x_{n+1}$
  .

Xét một đỉnh $A$ bất kỳ của đồ thị này, đỉnh $A$ được nối với $(n+1)a_n+1$ đỉnh khác bằng các cạnh được tô bằng $n+1$ màu. Theo nguyên lý Đirichlet tồn tại $a_n+1$ cạnh cùng màu, giả sử là màu $x_1$. Xét $a_n+1$ đỉnh nối với $A$ bằng màu $x_1$, nều tồn tại $2$ điểm $B, C$ trong chúng được nối với nhau bằng màu $x_1$ thì $\bigtriangleup ABC$ thỏa mãn ycbt. Nếu các cạnh nối $a_n+1$ đỉnh này chỉ được tô bằng $n$ màu $x_2 \rightarrow x_{n+1}$ thì theo gtqn ta cũng có $1$ tam giác có các cạnh cùng màu. Tóm lại KL đúng đến $n+1$ và ta có đpcm.

Bài viết đã được chỉnh sửa nội dung bởi whatever2507: 05-06-2013 - 18:46