Câu hỏi 95
Cho $N$ là một số nguyên dương. Vương quốc Kì Quặc có $N$ lâu đài, giữa mỗi cặp lâu đài có nhiều nhất một con đường. Trên mỗi con đường có nhiều nhất bốn lính canh. Để tiết kiệm chi phí nhân sự, nhà vua ban hành mệnh lệnh sau:
(1) Nếu ba lâu đài đôi một có đường nối với nhau thì không con đường nào trong số đó được có 4 lính canh;
(2) Nếu bốn lâu đài đôi một có đường nối với nhau thì với bất kì lâu đài nào trong số đó, ba con đường từ nó đến ba lâu đài còn lại không được đồng thời đều có 3 lính canh.
Chứng minh rằng dưới mệnh lệnh này, tổng số lính canh trên các con đường của vương quốc không vượt quá $N^2$.
*Chú thích*: Nếu chỉ chứng minh được tổng số lính canh không vượt quá $cN^2$, với $c \gt 1$ không phụ thuộc $N$, thì sẽ được chấm điểm tùy theo giá trị của $c$.
(1) Nếu ba lâu đài đôi một có đường nối với nhau thì không con đường nào trong số đó được có 4 lính canh;
(2) Nếu bốn lâu đài đôi một có đường nối với nhau thì với bất kì lâu đài nào trong số đó, ba con đường từ nó đến ba lâu đài còn lại không được đồng thời đều có 3 lính canh.
Chứng minh rằng dưới mệnh lệnh này, tổng số lính canh trên các con đường của vương quốc không vượt quá $N^2$.
*Chú thích*: Nếu chỉ chứng minh được tổng số lính canh không vượt quá $cN^2$, với $c \gt 1$ không phụ thuộc $N$, thì sẽ được chấm điểm tùy theo giá trị của $c$.