Question

[Lê Song Phương]

 Một mảnh đất hình vuông \(5\times5\), mỗi ô được chia cho một gia đình ở. Biết rằng mỗi gia đình mâu thuẫn với không quá 3 gia đình khác. CMR có thể chia ô đất cho 25 gia đình sao cho 2 gia đình có mâu thuẫn không ở 2 ô chung cạnh.

Answer 1

[lê quang vinh]

Để giải quyết bài toán này, ta có thể sử dụng phương pháp đồ thị. 

 

Xét ô đất như một đỉnh trên đồ thị, và việc chia ô đất cho gia đình tương đương với việc nối các đỉnh trên đồ thị bằng các cạnh. Ta sẽ xây dựng đồ thị với 25 đỉnh (tương ứng với 25 ô đất) và xem xét các điều kiện sau đây:

 

1. Mỗi đỉnh kề với đỉnh khác trên cạnh chung:

 

 - Xếp 5 hàng, mỗi hàng có 5 ô.

 

 - Cả hàng ngang và hàng dọc đều được xem xét là kề với nhau.

 

2. Mỗi đỉnh không kề với đỉnh khác trên cạnh chung:

 

 - Khi xếp 5 hàng, mỗi hàng sẽ không kề với hàng đối diện (cùng cột).

 

 - Khi xếp 5 cột, mỗi cột sẽ không kề với cột đối diện (cùng hàng).

 

Ta sẽ xây dựng đồ thị dựa trên các điều kiện trên. Đồ thị có 25 đỉnh và các cạnh được nối giữa các đỉnh mà thỏa mãn các điều kiện trên. Nếu ta có thể xây dựng được đồ thị như v