Câu hỏi 98
Một vương quốc có $10$ thị trấn. Một số cặp thị trấn khác nhau có cầu nối giữa chúng, sao cho giữa hai thị trấn khác nhau bất kì có nhiều nhất một cây cầu. Hai thị trấn có một cây cầu nối giữa chúng được gọi là hai *đầu mút* của cây cầu đó.
a) Chứng minh rằng có ít nhất hai thị trấn là *đầu mút* của cùng một số cây cầu.
b) Nhà vua ra lệnh cho thần dân xây thêm hoặc phá bỏ một số cây cầu, sao cho một nửa số thị trấn là *đầu mút* của $3$ cây cầu và nửa còn lại là *đầu mút* của $4$ cây cầu. Mệnh lệnh đó có thể thực hiện được không?
a) Chứng minh rằng có ít nhất hai thị trấn là *đầu mút* của cùng một số cây cầu.
b) Nhà vua ra lệnh cho thần dân xây thêm hoặc phá bỏ một số cây cầu, sao cho một nửa số thị trấn là *đầu mút* của $3$ cây cầu và nửa còn lại là *đầu mút* của $4$ cây cầu. Mệnh lệnh đó có thể thực hiện được không?