Math Labs

Bài 5

Cho một hoán vị (a0,a1,…,an)(a_0, a_1, \ldots, a_n) của dãy số 0,1,…,n0, 1, \ldots, n. Một phép đổi chỗ aia_i với aja_j được gọi là hợp lệ nếu ai=0a_i = 0 với i>0i > 0, và ai−1+1=aja_{i-1} + 1 = a_j. Hoán vị (a0,a1,…,an)(a_0, a_1, \ldots, a_n) được gọi là chính quy nếu sau một số phép đổi chỗ hợp lệ nó trở thành (1,2,…,n,0)(1, 2, \ldots, n, 0). Hỏi với những số nn nào thì hoán vị (1,n,n−1,…,3,2,0)(1, n, n-1, \ldots, 3, 2, 0) là chính quy?
Bước 1 trên 5: Phân tích quy tắc tất định và kiểm tra các giá trị nhỏ n=1,2n = 1, 2
Bước trướcBước tiếp
Hiểu nôm na

Không có sự lựa chọn nào cả: trò chơi tự vận hành một cách tất định cho đến khi 00 rơi vào vị trí ngay sau nn và dừng lại.

ai=0 (i>0)  ⟹  aj=ai−1+1;n=1  ⟹  (1,0),n=2  ⟹  (1,2,0)a_i = 0 \ (i > 0) \implies a_j = a_{i-1} + 1; \qquad n = 1 \implies (1, 0), \quad n = 2 \implies (1, 2, 0)
Phân tích chi tiết

Mỗi khi ai=0a_i = 0 với i>0i > 0, một phép đổi chỗ hợp lệ xét phần tử ai−1a_{i-1} đứng ngay trước 00 và đổi chỗ 00 với aj=ai−1+1a_j = a_{i-1} + 1. Như vậy tại mỗi thời điểm có nhiều nhất một phép đổi chỗ hợp lệ, và không thể thực hiện tiếp khi và chỉ khi đứng ngay trước 00 là nn (hoặc i=0i = 0, điều không bao giờ xảy ra vì 11 luôn ở a0a_0 hoặc ai−1≥1a_{i-1} \ge 1). Với n=1=21−1n = 1 = 2^1 - 1 và n=2n = 2, hoán vị ban đầu (1,0)(1, 0) và (1,2,0)(1, 2, 0) đã có sẵn dạng (1,…,n,0)(1, \ldots, n, 0), nên cả n=1n = 1 và n=2n = 2 đều chính quy.