Cho một bảng $5.5$ các bóng đèn bị thiếu đi một số bóng. Một lần tắt - mở ta có thể chọn một bóng và thay đổi trạng thái của bóng đó cùng với các bóng cùng hàng và cùng cột, tắt thành mở, mở thành tắt. Ban đầu tất cả các bóng đều tắt. Sau một số lần tắt - mở thì có đúng một bóng sáng. Tìm tất cả các cách sắp đặt các bóng ban đầu có thể.
#2
Đã gửi 01-04-2007 - 22:55
vnm
-
- Thành viên
-
- 160 Bài viết
Trung sĩ
ta gọi 1 ô là tốt nếu tồn tại 1 thuật toán để cuối cùng còn duy nhất đèn ô đó sáng
Dễ thấy nếu 1 ô là tốt thì các ô đối xứng với nó qua 1 trong 2 đường chéo chính là tốt
Xét tập S các ô thuộc hàng 1;3;5 trừ 3 ô (1;3);(3;3);(5;3)
tính M= số ngọn đèn thuộc S sáng;tính chẵn lẻ của M là bất biến.Thật vậy nếu ta thực hiên cho 1 đèn ko thuộc S thì do nó có 1 số chẵn các ô kề thuộc S nên M hoặc ko đổi hoặc tăng2 hoặc giảm 2 nên tính chẵn lẻ ko đổi;nếu ta thực hiên cho 1 ô thuộc S thì do nó có đúng 1 ô thuộc S kề nó nên tính chẵn lẻ của M cũng ko đổi
Ban đầu M=0 nên 1 ô tốt không thể thuộc S
các ô (1;3);(2;1);(4;1);(2;5);(4;5) cũng không tốt vì nó đối xứng với 1 ô thuộc S
Vậy còn lại 5 ô,ta có thể kiểm tra chúng đều tốt
Dễ thấy nếu 1 ô là tốt thì các ô đối xứng với nó qua 1 trong 2 đường chéo chính là tốt
Xét tập S các ô thuộc hàng 1;3;5 trừ 3 ô (1;3);(3;3);(5;3)
tính M= số ngọn đèn thuộc S sáng;tính chẵn lẻ của M là bất biến.Thật vậy nếu ta thực hiên cho 1 đèn ko thuộc S thì do nó có 1 số chẵn các ô kề thuộc S nên M hoặc ko đổi hoặc tăng2 hoặc giảm 2 nên tính chẵn lẻ ko đổi;nếu ta thực hiên cho 1 ô thuộc S thì do nó có đúng 1 ô thuộc S kề nó nên tính chẵn lẻ của M cũng ko đổi
Ban đầu M=0 nên 1 ô tốt không thể thuộc S
các ô (1;3);(2;1);(4;1);(2;5);(4;5) cũng không tốt vì nó đối xứng với 1 ô thuộc S
Vậy còn lại 5 ô,ta có thể kiểm tra chúng đều tốt
The day you were born, you cried but the others were smiling; Live your life in a way that one day you die with a smile and all the others cry
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh
