Bài 2. (7,0 điểm) Có $N$ người ngồi thành một vòng tròn (với $N\ge 3$), mỗi người cầm $k$ tấm thẻ (với $k\ge 2$), trên mỗi tấm thẻ được ghi một số thuộc tập $\{1;2;3;\dots ;N\}$. Mỗi số thuộc tập trên được ghi đúng trên $k$ tấm thẻ, tức là có $k$ thẻ được ghi số 1, $k$ thẻ được ghi số 2,$\dots$, $k$ thẻ được ghi số $N$. Cả $N$ người cùng thực hiện trò chơi như sau: Mỗi lượt chơi, mỗi người đều giữ lại những thẻ được ghi số lớn nhất trong những thẻ mà mình đang có (có thể nhiều hơn một thẻ) rồi chuyển cho người bên tay trái những thẻ còn lại. Trò chơi sẽ dừng lại khi xuất hiện ít nhất một người giữ trong tay $k$ thẻ có ghi số giống nhau (có thể họ đang giữ nhiều hơn $k$ thẻ).

a) Với $N=25$, $k=2$, chứng minh rằng trò chơi luôn dừng lại sau hữu hạn lượt chơi mà không phụ thuộc vào việc ban đầu họ cầm thẻ thế nào.

b) Tìm tất cả các giá trị của $k$ và $N$ để trò chơi dừng lại sau hữu hạn lượt chơi mà không phụ thuộc vào việc ban đầu họ cầm thẻ thế nào.

Lời giải (Lim Olympic - Quảng Ngãi TST - P5):

a) Ta sẽ giải bài toán trong trường hợp tổng quát là $k=2$ và $N$ là số lẻ.

Đặt $N=2m+1$. Giả sử phản chứng rằng trò chơi không bao giờ dừng.

Hai thẻ mang số $N$ đứng yên tại hai người khác nhau. Sau đó, hai thẻ mang số $N-1$ sẽ được chuyển qua những người đang giữ thẻ $N$ cho tới khi chúng đến những người không giữ thẻ có số lớn hơn. Khi ấy chúng đứng yên. Nếu chúng cùng đứng yên tại một người thì trò chơi đã dừng, nên chúng phải nằm tại hai người mới khác nhau.

Tiếp tục như vậy, sau hữu hạn lượt, tất cả thẻ mang các số $m+2,m+3,\dots ,2m+1$ đều đứng yên. Có $m$ số như vậy, nên $2m=N-1$ thẻ trên nằm tại $N-1$ người khác nhau.

Gọi $A$ là người duy nhất còn lại.

Xét hai thẻ mang số $m+1$. Tại bất cứ người nào trong $N-1$ người trên, thẻ $m+1$ đều nhỏ hơn một thẻ đang được giữ cố định, nên nó phải được chuyển tiếp.

Vì thế cả hai thẻ $m+1$ cuối cùng đều đi tới $A$.

Khi thẻ thứ nhất tới $A$, nó được giữ lại. Sau đó thẻ thứ hai cũng tới $A$, nên $A$ giữ hai thẻ cùng mang số $m+1$. Trò chơi dừng, mâu thuẫn.

Vậy nếu $k=2$ và $N$ lẻ thì trò chơi luôn dừng.

b) Ta sẽ chứng minh ngoại trừ trường hợp $k=2$ và $N$ lẻ, thì trò chơi đều không dừng lại.

◇ Trường hợp 1: $N$ chẵn.

Đặt $N=2m$. Chia $N$ người thành $m$ nhóm, mỗi nhóm gồm hai người.
Ta dùng $m$ số lớn nhất là $m+1,m+2,\dots ,2m$.

Với mỗi số $r\in \{m+1,m+2,\dots ,2m\}$, lấy $k$ thẻ mang số $r$ và phát cho hai người trong một nhóm: một người nhận $1$ thẻ, người kia nhận $k-1$ thẻ.

Như vậy mỗi người đều có ít nhất một thẻ mang số lớn hơn $m$, nhưng không ai có đủ $k$ thẻ cùng số. Các vị trí còn thiếu được điền bằng toàn bộ các thẻ mang các số $1,2,\dots ,m$.

Trong quá trình chơi, các thẻ mang số lớn hơn $m$ luôn là những thẻ có số lớn nhất tại người đang giữ chúng, nên chúng đứng yên mãi mãi. Mọi thẻ mang số không vượt quá $m$ đều nhỏ hơn các thẻ cố định này, nên sau mỗi lượt chúng đều được chuyển sang người bên trái.

Do đó, phần các thẻ nhỏ mà mỗi người đang giữ chỉ chuyển nguyên sang người bên trái sau mỗi lượt. Ban đầu mỗi người có ít nhất một thẻ lớn, nên có nhiều nhất $k-1$ thẻ nhỏ. Vì vậy không bao giờ có người nào nhận được $k$ thẻ nhỏ cùng số.

Mặt khác, với mỗi số lớn, $k$ thẻ của số đó được chia cho ít nhất hai người và luôn đứng yên, nên cũng không thể có người nào giữ đủ $k$ thẻ cùng số.

Vậy với cách chia ban đầu này, trò chơi không bao giờ dừng.

◇ Trường hợp 2: $N$ lẻ và $k\ge 3$.

Viết $N=2m+3$.

Chia $N$ người thành một nhóm gồm ba người và $m$ nhóm, mỗi nhóm gồm hai người.

Có tất cả $m+1$ nhóm, lấy $m+1$ số lớn nhất trong $\{1,2,\dots ,N\}$ và gán mỗi số cho một nhóm.

☆ Với mỗi nhóm gồm hai người, chia $k$ thẻ mang số tương ứng thành hai phần $1$ và $k-1$.
☆ Với nhóm gồm ba người, chia $k$ thẻ mang số tương ứng thành ba phần $1,1,k-2$. Do $k\ge 3$, cả ba phần đều khác rỗng và mỗi phần đều có ít hơn $k$ thẻ.

Như vậy mỗi người đều giữ ít nhất một thẻ mang một trong $m+1$ số lớn nhất, nhưng không ai giữ đủ $k$ thẻ cùng số. Ta điền các vị trí còn lại bằng tất cả các thẻ mang những số nhỏ hơn.
Hoàn toàn tương tự trường hợp trên, các thẻ mang $m+1$ số lớn nhất đứng yên mãi mãi, còn các thẻ nhỏ hơn chỉ chuyển vòng quanh bàn từ người này sang người bên trái.

Mỗi người có ít nhất một thẻ lớn, nên tại mọi thời điểm phần thẻ nhỏ chuyển tới một người có không quá $k-1$ thẻ. Do đó không thể xuất hiện $k$ thẻ nhỏ cùng số tại một người. Các thẻ lớn cũng đã được chia cho ít nhất hai người nên không thể tạo ra $k$ thẻ cùng số tại một người.

Vì vậy tồn tại cách chia ban đầu để trò chơi không bao giờ dừng.

Từ đây ta suy ra được tất cả các giá trị cần tìm là $k=2$ và $N$ lẻ.