Bài 4

Cho

n

và

k

là hai số nguyên dương. Cathy chơi trò chơi sau. Có

n

viên bi và

k

chiếc hộp, các viên bi được đánh số từ

1

đến

n

. Ban đầu, tất cả các viên bi nằm trong một hộp. Mỗi lượt, Cathy chọn một hộp rồi chuyển viên bi có nhãn nhỏ nhất, giả sử là

i

, sang một hộp trống bất kỳ hoặc sang hộp đang chứa viên bi

i+1

. Cathy thắng nếu tại một thời điểm nào đó có một hộp chỉ chứa duy nhất viên bi

n

. Xác định mọi cặp số nguyên

(n,k)

sao cho Cathy có thể thắng trò chơi này.

Bước 1 trên 4: Bất biến đoạn liên tiếp và tính khả nghịch

Bước trước Bước tiếp

\text{Every non-empty box holds a consecutive interval }\{a,a+1,\ldots,b\};\ \text{moves are reversible}

Phân tích chi tiết

Ban đầu hộp xuất phát chứa $\{1,\ldots,n\}$ . Vì Cathy luôn chỉ lấy phần tử nhỏ nhất của một hộp rồi đặt vào hộp trống hoặc ghép vào phần tử nhỏ nhất $i+1$ của hộp khác, mỗi hộp khác rỗng luôn chứa một đoạn nhãn liên tiếp, và phép đảo ngược của mọi nước đi hợp lệ cũng hợp lệ.