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 2 trên 5: Loại trừ

k>\lceil3n/2\rceil

bằng một chu trình bốn chuỗi

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

\lfloor n/2\rfloor,\ \lceil n/2\rceil,\ \lceil n/2\rceil,\ \lfloor n/2\rfloor

Phân tích chi tiết

Với $k>\lceil3n/2\rceil$ , lấy bốn chuỗi kích thước $\lfloor n/2\rfloor,\lceil n/2\rceil,\lceil n/2\rceil,\lfloor n/2\rfloor$ xen kẽ $A,B,A,B$ ; vì chuỗi cuối có ít nhất $\lfloor n/2\rfloor$ xu, $k$ luôn rơi vào trong đó, và di chuyển nó lên đầu chỉ đơn giản xoay bốn chuỗi, nên hình mẫu lặp lại mãi mãi mà không bao giờ tạo ra $n$ xu ngoài cùng bên trái trùng loại.