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 5 trên 5: Nêu đáp số cuối cùng

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

(n,k):\ n\le k\le\lceil3n/2\rceil

Phân tích chi tiết

Kết hợp hai cách xây dựng phản ví dụ với lập luận hợp nhất, các cặp luôn thành công chính xác là những cặp có $n\le k\le\lceil3n/2\rceil$ .