Giả sử rằng trên đường tròn đã có http://dientuvietnam...n/mimetex.cgi?n ô(http://dientuvietnam...tex.cgi?0,1.Một phép toán thực hiện theo luật sau:Chọn một ô http://dientuvietnam...n/mimetex.cgi?C nào đó có kí hiệu http://dientuvietnam...etex.cgi?1,biến đổi nó thành http://dientuvietnam...n/mimetex.cgi?0 và biến đổi các kí hiệu http://dientuvietnam...mimetex.cgi?x,y trong hai ô kề với ô http://dientuvietnam...n/mimetex.cgi?C thành http://dientuvietnam...x.cgi?1-x,1-y.Ở trạng thái ban đầu có một ô mang kí hiệu http://dientuvietnam...n/mimetex.cgi?1 còn các ô khác mang kí hiệu http://dientuvietnam...metex.cgi?0.Tìm các giá trị http://dientuvietnam.net/cgi-bin/mimetex.cgi?n sao cho sau một số hữu hạn bước thực hiện phép toán trên,ta có thể đưa các kí hiệu trên các ô về toàn là http://dientuvietnam.net/cgi-bin/mimetex.cgi?0.
Cái vòng toàn 0 và 1
Bắt đầu bởi QUANVU, 14-04-2005 - 20:17
#1
Đã gửi 14-04-2005 - 20:17
1728
#2
Đã gửi 15-05-2005 - 16:10
Với n không chia hết cho 3 thì rất dễ để thấy rằng sau một số hữu hạn bước thực hiện thuật toán sẽ đưa được về trạng thái như đề bài đòi hỏi (chứng minh điều này không khó lắm, các bạn về làm thử ha). Sau đây ta chứng minh rằng với n là bội của 3 thì không thể đưa về được bằng cách chỉ ra một bất biến. Chọn 1 ô bát kì làm gốc và đánh số theo chiều kim đồng hồ. Gọi a,b,c lần lượt là số các số 1 ở các ô có kí hiệu chia 3 dư 0,1,2. Đặt S=|a-b|+|b-c|+|c-a|. Bất biến chính là số dư của S khi chia cho 4.
Ghé thăm blog nhé:
http://360.yahoo.com/steppe2205
http://360.yahoo.com/steppe2205
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh