Đóng góp cho topic 1 bài diriclet
Có 9 điểm trên mặt phẳng, bất cứ điểm nào cũng là đỉnh của một tam giác mà cạnh được tô bởi màu xanh hoặc đỏ trong đó bao giờ cũng có cạnh màu đỏ. CMR tồn tại 1 tứ giác có các cạnh và đường chéo cùng màu đỏ
Trường hợp $1$ : Trong $9$ điểm tồn tại $1$ điểm $a$ là đầu mút của $4$ cạnh xanh.
Ta xét $4$ đỉnh kề với $a$ bởi các cạnh xanh. Khi đó $4$ đỉnh này sẽ lập thành $1$ tứ giác mà các cạnh và đường chéo được tô màu đỏ .
Vì nếu trong tứ giác mà tồn tại $1$ cạnh màu xanh thì cạnh đó cùng với $2$ cạnh trong $4$ cạnh xanh kia sẽ lập nên $1$ tam giác không có cạnh màu đỏ.
Trái với giả thiết . Vậy tứ giác đó là tứ giác cần tìm
Trường hợp $2$ : Tất cả các đỉnh có số cạnh xanh xuất phát từ đỉnh đó không vượt quá $3$. Khi đó tồn tại $1$ đỉnh mà có số cạnh xanh xuất phát từ nó $\leq 2$ .
Vì nếu tất cả các đỉnh đều có số cạnh xanh là $3$ thì số cạnh xanh của đồ thị là $\frac{9.3}{2}=\frac{27}{2}$ (vô lý)
Gọi $a$ là đầu mút có nhiều nhất $2$ cạnh xanh , khi đó $a$ có ít nhất $6$ cạnh đỏ
Xét $6$ đỉnh kề với $a$ mà được nối với $a$ bởi cạnh màu đỏ, $6$ điểm này lập thành $1$ đồ thị đủ $6$ đỉnh mà các cạnh mà các cạnh được tô bởi $2$ màu xanh và đỏ.
Áp dụng định lí Ramsey : Nếu tô màu các cạnh của đồ thị đầy đủ $6$ đỉnh $K_6$ với $2$ màu xanh đỏ , thì luôn tồn tại $1$ đồ thị đầy đủ $3$ đỉnh $K_3$ là đồ thị con của đồ thị này và tất cả các cạnh của nó hoặc cùng màu đỏ hoặc cùng màu xanh
Theo định lí trên, luôn tồn tại $3$ đỉnh lập thành $1$ tam giác mà các cạnh được tô cùng một màu xanh hoặc đỏ
Nhưng tam giác này không thể là màu xanh vì nó không chứa cạnh màu đỏ , trái với giả thiết. Vậy tam giác đó chỉ có thể là màu đỏ
Khi đó $3$ đỉnh này cùng với đỉnh $a$ lập thành một tứ giác mà tất cả các cạnh và đường chéo cùng được tô màu đỏ . (ĐPCM)