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 4 trên 5: Chứng minh số chuỗi tiếp tục giảm khi

n\le k\le\lceil3n/2\rceil

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

n\le k\le\lceil3n/2\rceil\ \Rightarrow\ \text{chains keep merging until }2\text{ remain}

Phân tích chi tiết

Nếu $k$ rơi vào chuỗi đầu tiên $[1,l]$ với $l\ge k\ge n$ , thì $l=n$ chính xác, đây đã là kết luận mong muốn. Nếu thay vào đó $k$ rơi vào chuỗi cuối cùng, một phép đếm theo nguyên lý Dirichlet cho thấy khi có ít nhất $4$ chuỗi, có một chuỗi với ít hơn $2n-k+1$ xu nên không thể luôn chứa vị trí cuối giữ $k$ ; do đó $k$ cuối cùng phải rơi vào một chuỗi bên trong (kích hoạt việc hợp nhất ở bước trước) hoặc vào một cấu hình chỉ còn $2$ hay $3$ chuỗi, và lặp lại lập luận này đưa số chuỗi xuống $2$ , lúc đó $n$ xu ngoài cùng bên trái cùng một loại.