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

[anhminh]

Vô hạn ô xếp từ trí qua phải.Đánh số các ô 1,2,3,...
Rải các viên sỏi vào các ô.
Quy tắc chuyển sỏi như sau:
- Nếu ô $N$ và $N+1$ đều có sỏi thì chuyển tất cả sỏi ở 2 ô này sang ô $N+2$.
-Nếu ô $N+1$ có 2 viên mà ô $N$ và $N+2$ không có sỏi thì chuyển 2 viên đó vào 2 ô $N$ và $N+2$.
Chứng minh rằng:
1.Trò chơi kết thúc sau hữu hạn bước.
2.Nếu tồn tại $n$ ô liên tiếp mỗi ô có 1 viên thì trò chơi kết thúc sau $k< n$ bước.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 14:29

[Hr MiSu]

đề bài nên sửa lại, vì nếu có vô hạn ô thì ko thể dừng đc, phải có một số ô nào đó nhất định.

c/m ý 1: Đầu tiên ta chứng minh, khi thực hiện 2 lên ô N+1, chỉ có thể tác động lên ô N+1 tối đa 3 phép toán nữa (xét các ô xung quanh). Do đó đến 1 lúc nào đó, ta ko thể thực hiện 2 được nữa, khi đó ta chỉ có thể thực hiện 1. Như vậy ta chỉ có thể thực hiện 1, mà thực hiện 1 thì ô tác động sẽ tăng dần, (do tác động rồi thì ko thể thực hiện ngược lại), do đó mà đến 1 lúc nào đó, phải dừng lại/