MathLabs

Bài 1

Ngân hàng Oslo phát hành hai loại xu: nhôm (ký hiệu AA) và đồng (ký hiệu BB). Marianne có nn xu nhôm và nn 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≤2nk\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ứ kk 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)(n,k) với 1≤k≤2n1\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, nn xu ngoài cùng bên trái đều cùng một loại.
Bước 3 trên 5: Nếu kk nằm hẳn bên trong một chuỗi, hai chuỗi hợp nhất
Bước trướcBước tiếp
Hiểu nôm na

Di chuyển một chuỗi ở giữa lên đầu sẽ nối hai chuỗi lân cận cùng loại của nó thành một, nên tổng số chuỗi chỉ có thể giảm.

B1=[l′,l−1],B2=[m+1,m′]B_1=[l',l-1],\quad B_2=[m+1,m']
Phân tích chi tiết

Giả sử kk nằm trong một chuỗi [l,m][l,m] với l>1l>1 và m<2nm<2n (không phải chuỗi đầu hay chuỗi cuối). Chuyển [l,m][l,m] lên đầu khiến chuỗi B1=[l′,l−1]B_1=[l',l-1] ngay trước nó và chuỗi B2=[m+1,m′]B_2=[m+1,m'] ngay sau nó trở nên kề nhau; vì B1B_1 và B2B_2 cùng loại xu, chúng hợp nhất thành một chuỗi duy nhất, nên tổng số chuỗi giảm chặt.