Chủ đề này có 2 trả lời

[minhdat881439]

Trong 64 ô của bàn cờ có đánh dấu 16 ô sao cho mỗi hàng mỗi cột của bàn cờ có đúng 2 ô được đánh dấu.
Chứng minh rằng có thể đặt 8 quân cờ trắng và 8 quân cờ đen vào các ô được đánh dấu sao cho mỗi dòng, mỗi cột của bàn cờ có đúng 1 quân cờ trắng và 1 quân cờ đen

[Mai Duc Khai]

Trong 64 ô của bàn cờ có đánh dấu 16 ô sao cho mỗi hàng mỗi cột của bàn cờ có đúng 2 ô được đánh dấu.
Chứng minh rằng có thể đặt 8 quân cờ trắng và 8 quân cờ đen vào các ô được đánh dấu sao cho mỗi dòng, mỗi cột của bàn cờ có đúng 1 quân cờ trắng và 1 quân cờ đen

Đáp án:
Ta xuất phát từ 1 ô đánh dấu tới ô đánh dấu cùng hàng, tiếp theo tôi ô đánh dấu cùng cột, tiếp theo lại tới ô đánh dấu cùng hàng... nghĩa là thay đổi liên tục hướng đi theo hàng và cột tới các ô đã đánh dấu. Ta dừng lại khi tới ô đầu tiên thuộc đường gấp khúc ta đang đi. Gọi ô đó là M.

- Ta chứng minh ô M chỉ có thể là ô xuất phát của đường gấp khúc đang đi. Giả sử M không phải là ô xuất phát. Dĩ nhiên ô M có 1 ô đánh dấu cùng hàng, gọi đó là A, một ô đánh dấu cùng cột, gọi đó là B. Do M không là ô xuất phát nên A và B cũng thuộc đường gấp khúc đang xét. Để tới M không có cách nào khác là phải từ A hoặc từ B. Do vậy M không thể là ô ta gặp đầu tiên của đường gấp khúc đang xét. Mâu thuẫn với giả thiết về M đặt ra ở trên. Vậy M là ô xuất phát.

- Đường gấp khúc kín này gồm một số đoạn thẳng (dọc, ngang xen kẽ) nên gồm một số chẵn ô đánh đấu, 2 ô liên tiếp là trên cùng một dòng hay cùng một cột. Đánh số 1 từ ô xuất phát, cứ ô lẻ đặt quân cờ đen, ô chẵn đặt quân cờ trắng thì đường gấp khúc kín này thoả mãn: mỗi dòng, mỗi cột có đúng 1 quân cờ trắng 1 quân cờ đen.

- Nếu đường đi chưa hết các ô đánh dấu, ta bắt đầu lại từ 1 ô nào đó chưa đặt quân cờ và đi 1 đường gấp khúc kín như trên, rồi lại đặt các quân cờ trắng, đen theo cách trên. Cứ như vậy ta được một số hữu hạn đường gấp khúc kín đi hết 16 ô đánh dấu thoả mãn điều kiện bài toán: mỗi dòng, mỗi cột có đúng 1 quân cờ trắng, 1 quân cờ đen.

- Hai đường gấp khúc này không thể có chung 1 ô đánh dấu, vì bắt đầu từ ô đó suy ra 2 đường gấp khúc là trùng nhau.

Nguồn: http://www.bachkhoatrithuc.vn

Bài viết đã được chỉnh sửa nội dung bởi Buoc Ngoat: 01-11-2012 - 19:34

[Galoa_82]

Đáp án:
Ta xuất phát từ 1 ô đánh dấu tới ô đánh dấu cùng hàng, tiếp theo tôi ô đánh dấu cùng cột, tiếp theo lại tới ô đánh dấu cùng hàng... nghĩa là thay đổi liên tục hướng đi theo hàng và cột tới các ô đã đánh dấu. Ta dừng lại khi tới ô đầu tiên thuộc đường gấp khúc ta đang đi. Gọi ô đó là M.

- Ta chứng minh ô M chỉ có thể là ô xuất phát của đường gấp khúc đang đi. Giả sử M không phải là ô xuất phát. Dĩ nhiên ô M có 1 ô đánh dấu cùng hàng, gọi đó là A, một ô đánh dấu cùng cột, gọi đó là B. Do M không là ô xuất phát nên A và B cũng thuộc đường gấp khúc đang xét. Để tới M không có cách nào khác là phải từ A hoặc từ B. Do vậy M không thể là ô ta gặp đầu tiên của đường gấp khúc đang xét. Mâu thuẫn với giả thiết về M đặt ra ở trên. Vậy M là ô xuất phát.

- Đường gấp khúc kín này gồm một số đoạn thẳng (dọc, ngang xen kẽ) nên gồm một số chẵn ô đánh đấu, 2 ô liên tiếp là trên cùng một dòng hay cùng một cột. Đánh số 1 từ ô xuất phát, cứ ô lẻ đặt quân cờ đen, ô chẵn đặt quân cờ trắng thì đường gấp khúc kín này thoả mãn: mỗi dòng, mỗi cột có đúng 1 quân cờ trắng 1 quân cờ đen.

- Nếu đường đi chưa hết các ô đánh dấu, ta bắt đầu lại từ 1 ô nào đó chưa đặt quân cờ và đi 1 đường gấp khúc kín như trên, rồi lại đặt các quân cờ trắng, đen theo cách trên. Cứ như vậy ta được một số hữu hạn đường gấp khúc kín đi hết 16 ô đánh dấu thoả mãn điều kiện bài toán: mỗi dòng, mỗi cột có đúng 1 quân cờ trắng, 1 quân cờ đen.

- Hai đường gấp khúc này không thể có chung 1 ô đánh dấu, vì bắt đầu từ ô đó suy ra 2 đường gấp khúc là trùng nhau.

Nguồn: http://www.bachkhoatrithuc.vn

Bạn giúp mình bài này nhé, cảm ơn nhiều:

Các quân xe được đặt trên bàn cờ vua kích thước nxn sao cho nếu ô (i;j) trống thì có ít nhất n quân xe có mặt trên hàng i và cột j đồng thời. CMR có ít nhất n²/2 quân xe trên bàn cờ.