Question

[Lê Song Phương]

 Trong không gian cho 7 điểm phân biệt sao cho không có bốn điểm nào đồng phẳng. Tất cả các điểm đó được nối với nhau bởi các đoạn thẳng. Mỗi đoạn thẳng được tô bởi hai màu xanh, đỏ hoặc không được tô màu. Tìm số \(k\) nhỏ nhất sao cho với mọi cách tô màu \(k\) đoạn thẳng bất kì trong các đoạn thẳng đó, luôn tồn tại một tam giác có ba cạnh cùng màu. 

Answer 1

[Phạm Trường Vinh]

法定函谷关个GIz,zz  

Answer 2

[Hồ Thị Hiền]

Gọi 7 điểm phân biệt là A_1, A_2, A_3, A_4, A_5, A_6, A_7. Tổng số đoạn thẳng được tạo ra là \binom{7}{2} = \frac{7 \times 6}{2} = 21. Xét một điểm bất kì, ví dụ A_1. Có 6 đoạn thẳng nối A_1 với 6 điểm còn lại. Giả sử k đoạn thẳng trong số này được tô màu đỏ. Nếu trong 6-k đoạn thẳng còn lại có 2 đoạn thẳng cùng màu xanh, thì ta có một tam giác cùng màu xanh. Nếu trong k đoạn thẳng được tô màu đỏ có 2 đoạn thẳng cùng màu đỏ, thì ta có một tam giác cùng màu đỏ. Để không có tam giác nào cùng màu, ta cần: \begin{itemize} \item Trong 6 đoạn thẳng nối A_1 với các điểm còn lại, số đoạn thẳng màu đỏ không quá 2 và số đoạn thẳng màu xanh không quá 2. \end{itemize} Tức là k \le 3 và 6-k \le 3, suy ra 3 \le k \le 3, vậy k=3. Xét trường hợp tổng quát. Chọn một điểm, chẳng hạn A_1. Có 6 đoạn thẳng nối A_1 với 6 điểm còn lại. Giả sử có k đoạn thẳng màu đỏ và 6-k đoạn thẳng màu xanh. Nếu k \ge 3, theo nguyên lý Dirichlet, tồn tại ít nhất 3 đoạn thẳng cùng màu đỏ. Nếu trong 3 đoạn thẳng này có 2 đoạn thẳng cùng màu đỏ, ta có tam giác đỏ. Nếu không có 2 đoạn thẳng nào cùng màu đỏ, thì 3 đoạn thẳng còn lại cùng màu xanh, ta có tam giác xanh. Vậy k \le 2. Tương tự, 6-k \le 2, suy ra k \ge 4. Xét đồ thị đầy đủ K_7 có 7 đỉnh. Mỗi cạnh được tô màu đỏ hoặc xanh. Xét một đỉnh v. Có 6 cạnh xuất phát từ v. Theo nguyên lý Dirichlet, có ít nhất 3 cạnh cùng màu, giả sử là màu đỏ. Gọi 3 đỉnh đầu mút của 3 cạnh này là x, y, z. Nếu một trong các cạnh xy, yz, zx màu đỏ, ta có tam giác đỏ. Nếu cả 3 cạnh xy, yz, zx màu xanh, ta có tam giác xanh. Vậy số k nhỏ nhất là 9.