Bài 1

Ngân hàng Oslo phát hành hai loại xu: nhôm (ký hiệu

A

) và đồng (ký hiệu

B

). Marianne có

n

xu nhôm và

n

xu đồng xếp thành một hàng theo một thứ tự ban đầu bất kỳ. Một chuỗi là bất kỳ dãy con nào gồm các xu liên tiếp cùng loại. Với một số nguyên dương cố định

k\le2n

, Marianne liên tục thực hiện thao tác sau: xác định chuỗi dài nhất chứa xu thứ

k

từ trái sang, rồi chuyển tất cả các xu trong chuỗi đó về đầu bên trái của hàng. Tìm tất cả các cặp

(n,k)

với

1\le k\le2n

sao cho với mọi thứ tự ban đầu, tại một thời điểm nào đó trong quá trình,

n

xu ngoài cùng bên trái đều cùng một loại.

Bước 1 trên 5: Loại trừ

k<n

bằng một cách sắp xếp bất biến

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

Hiểu nôm na

Nếu $k$ nhỏ, một cách sắp xếp có thể giữ xu thứ $k$ mãi mãi bên trong một chuỗi quá ngắn để không bao giờ đạt tới đầu trái một cách đầy đủ.

A\ldots A\,B\ldots B\,A

Phân tích chi tiết

Với $k<n$ , lấy cách sắp xếp ban đầu $A\ldots A\,B\ldots B\,A$ (một khối các xu $A$ , rồi tất cả $n$ xu $B$ , rồi một xu $A$ cuối cùng), chọn sao cho xu thứ $k$ luôn nằm trong chuỗi $A$ dẫn đầu dài; thực hiện thao tác di chuyển chính chuỗi đó lên đầu và cách sắp xếp không đổi, nên $n$ xu ngoài cùng bên trái không bao giờ cùng loại.