Bốc bi

Đề bài:

Trên bàn có 2 đống bi, đống thứ nhất có 2013 viên bi, đống thứ hai có 20132013 viên bi. A và B lần lượt bốc bi theo nguyên tắc sau: Mỗi lần được phép chọn 1 đống và bốc từ đống đó tối thiểu 1 viên và tối đa một nửa số bi trong đống. A là người bốc trước, đến lượt mình mà ai không thể thực hiện được nước đi là người thua cuộc. Hỏi ai là người có chiến thuật dành chiến thắng?

Lời giải:

Ta xét bài toán tổng quát với số bi ở 2 đống là $m,n$.

Ta sẽ chứng minh:

$(m,n),m\ge n$ là một vị trí thua khi $m+1=2^k(n+1),k\in\mathbb{N}$           (*)

Ta sẽ chứng minh (*) bằng quy nạp theo $p=k+n$.

Dễ thấy $(1;1)$ là một vị trí thua nên (*) đúng với $p=1$.

Giả sử (*) đúng với mọi $\forall p\le p_0$.

Ta xét vị trí $(m_0,n_0),m_0\ge n_0$ thỏa mãn $m_0+1=2^{k_0}(n_0+1)$ trong đó $k_0+n_0=p_0+1$ và đến lượt A bốc bi.

Nếu A bốc $r$ viên ở đống có $n_0$ viên bi thì B bốc $2^{k_0}r$ viên ở đống kia, số bi ở 2 đống được đưa về trạng thái $(m_0-2^{k_0}r,n_0-r)$, đây là một vị trí thua theo giả thiết quy nạp.

Nếu A bốc $r$ viên ở đống có $m_0$ viên bi thì B bốc tiếp $2^{k_0-1}(n_0+1)-r$ viên ở đống đó, số bi ở 2 đống được đưa về trạng thái $(m_0-2^{k_0-1}(n_0+1),n_0$, đây là một vị trí thua theo giả thiết quy nạp.

Suy ra các vị trí $(m_0,n_0),m_0\ge n_0$ thỏa mãn $m_0+1=2^{k_0}(n_0+1)$ trong đó $k_0+n_0=p_0+1$ là các vị trí thua.

Theo nguyên lý quy nạp thì (*) đúng với mọi $p=k+n$.

Như vậy, ở bài toán này, A sẽ là người chiến thắng vì A có thể bốc 3633326 viên ở đống thứ 2 để đưa số bi ở 2 đống về vị trí thua.