Định lýĐã chứng minh

Định lý dừng nhờ đơn biến trên tập sắp thứ tự tốt

Phát biểu

Giả sử mỗi bước đi hợp lệ $s \to s'$ của một quá trình đều làm giảm một hàm nhận giá trị nguyên $M: \mathcal{S} \to \mathbb{Z}$ ít nhất $1$ đơn vị, tức $M(s') \le M(s) - 1$ , và $M(s) \ge 0$ với mọi trạng thái $s \in \mathcal{S}$ . Khi đó xuất phát từ trạng thái $s_0$ bất kỳ, quá trình buộc phải dừng sau nhiều nhất $M(s_0)$ bước.

Vì sao đúng?

Bạn không thể bước xuống một cầu thang cao $M(s_0)$ bậc quá $M(s_0)$ lần nếu mỗi bước đều xuống ít nhất một bậc và không bao giờ xuống thấp hơn tầng trệt $0$ .

Phác thảo chứng minh

**Bước 1 (chặn quy nạp sau $k$ bước).** Cho $s_0 \to s_1 \to s_2 \to \cdots \to s_k$ là một dãy $k$ bước đi hợp lệ bất kỳ. Áp dụng giả thiết $M(s_{i}) \le M(s_{i-1}) - 1$ với $i = 1, 2, \dots, k$ rồi cộng dồn rút gọn cho ta $M(s_k) \le M(s_0) - k$ .

**Bước 2 (chặn trên cho $k$ ).** Vì $M(s_k) \ge 0$ với mọi trạng thái đạt được $s_k \in \mathcal{S}$ , kết hợp hai bất đẳng thức ta có $0 \le M(s_k) \le M(s_0) - k$ , suy ra ngay $k \le M(s_0)$ . Vậy không có quỹ đạo hợp lệ nào dài $k > M(s_0)$ , và quá trình phải dừng sau nhiều nhất $M(s_0)$ bước.

Chủ đề chứa định lý này

Bất biến và đơn biến

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Arthur Engel (1998). Problem-Solving Strategies · DOI:10.1007/b97682
Jessica Striker (2017). Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance · DOI:10.1090/noti1539