Bốc sỏi B

Cho đống sỏi N viên, hai đấu thủ A và B lần lượt đi, A đi nước đầu tiên. Mỗi nước đi đấu thủ được phép bốc từ 1 đến M viên sỏi. Đấu thủ nào thực hiện nước đi cuối cùng thì thua. Cả hai đấu thủ đều chơi rất giỏi.  Với hai số N và M cho trước hãy cho biết A thắng (ghi 1) hay thua (ghi 0).

                Ta nhận thấy bài này chỉ khác bài Bốc sỏi A  ở điều kiện thua: ai bốc quân cuối cùng sẽ thua.

                Chắc chắn là bạn sẽ có thể xác định ngay được bất biến thua của trò chơi này là
N = k(M+1) + 1, k ³ 0. Tuy nhiên, để hình thành kỹ năng phát hiện luật chơi cho các bài toán khó hơn sau này, bạn hãy gắng thực hiện các bước tìm kiếm theo các sơ đồ sau đây:

Sơ đồ 1: Thử với vài dữ liệu ban đầu: M = 3;  N = 1, 2,…

M = 3	N =	1	2	3	4	5	6	7	8	9	10	11	12	13	…
A thắng (1) hay thua (0)?		0	1	1	1	0	1	1	1	0	1	1	1	0	…
Cách đi: số viên cần bốc để chắc thắng.		#	1	2	3	#	1	2	3	#	1	2	3	#	…
Một vài tình huống cho bài Bốc sỏi B, M = 3; # - đầu hàng/bốc tạm 1 viên

Sơ đồ 2: Tính hai hai thế thua liên tiếp theo lập luận lùi (Nhân - quả).

Sơ đồ tính hai thế thua liên tiếp
Bước 1	Xác định thế thua nhỏ nhất: T (N = 1)
Bước 2	Xác định các thế thắng V dẫn đến T: Từ V có một nước đi dẫn đến T. T(N=1) ß  V(N = 2 | 3 | 4)
Bước 3	Xác định thế thua T dẫn đến V: Mọi cách đi từ T đều rơi vào V. T(N=1) ß  V(N = 2 | 3 | 4) ß T(N=5)
Bước 4	Tổng quát hóa, xây dựng và chứng minh công thức xác định bất biến thua: N = k(M+1)+1, k ³ 0

Sơ đồ 3:  Tổng quát hóa (Chi tiết hóa Bước 4 trong Sơ đồ 2). Trong sơ đồ 3 dưới đây ta kí hiệu X(k) là số viên sỏi tại thế X xét trong bước k = 0, 1, 2... X có thể là thế thắng V hoặc thế thua T, chú ý rằng bước k được xét theo quá trình lập luận lùi chứ không xét theo diễn tiến của trò chơi.

Bước 4. Tổng quát hóa
Bước 4.1	Thế thua nhỏ nhất: T(0) = 1.
Bước 4.2	Giả thiết thế thua tại bước k là T(k) (số viên sỏi để người đi trước thua).
Bước 4.3	Xác định các thế thắng V(k) dẫn đến T(k): Có một cách đi để trên bàn còn T(k) viên sỏi. T(k) ß V(k) = T(k) + d; 1 £ d £ M.
Bước 4.4	Xác định thế thua T(k+1) dẫn đến V(k): Mọi cách đi từ T(k+1) đều rơi vào V(k) = T(k) + d; 1 £ d £ M: T(k) ß V(k) = T(k) + d; 1 £ d £ M ßT(k+1) = Max {V(k)}+1 = T(k)+(M+1)
Bước 4.5	Chứng minh công thức T(k) bằng qui nạp: T(k) = k(M+1)+1

   Dự đoán công thức: Ta có, theo công thức thu được ở Bước 4.4, T(k+1) = T(k)+(M+1),

   T(0) = 1;

   T(1) = T(0)+(M+1) = 1+(M+1);

   T(2) = T(1)+(M+1) = 1+(M+1)+(M+1) = 2(M+1)+1;

   T(3) = T(2)+(M+1) = 2(M+1)+1+(M+1) = 3(M+1)+1;

   ...

   Dự đoán: T(k) = k(M+1)+1.

Chứng mnh bất biến thua: Nếu số sỏi trong đống là T(k) = k(M+1)+1, k ³ 0 thì ai đi trước sẽ thua. 

Cơ sở qui nạp: với k = 0 ta có T(0) = 0.(M+1)+1 = 1. Đây là thế thua nhỏ nhất.

Giả sử với k ³ 1 ta có thế thua là T(k) = k(M+1)+1. Ta chứng minh rằng T(k+1) = (k+1)(M+1)+1 sẽ là thế thua tiếp theo và giữa hai thế thua này là các thế thắng. Thật vậy, vì T(k) là thế thua nên các thế có dạng V(k) = T(k)+d, 1 £ d £ M sẽ đều là thế thắng. Từ đây suy ra thế thua tiếp sau đó phải là T(k+1) = T(k)+M+1 = k(M+1)+1+(M+1) =  (k+1)(M+1)+1.

Kết luận Bài Bốc sỏi B

Nếu số sỏi N =  k(M+1)+1,  k ³ 0 thì đấu thủ nào đi trước sẽ thua.

Ta cũng có thể sử dụng hàm f(N) xác định xem với đống sỏi có N viên thì người đi trước sẽ thắng (f(N) = 1) hay thua (f(N) = 0). Ta có, f(1) = 0 vì với 1 viên sỏi thì ai bốc viên đó sẽ thua. Giả sử f(N) = 0. Dễ thấy, khi đó f(N+d) = 1 với 1 £ d £ M, vì chỉ cần bốc d viên sỏi là dẫn đến thế thua. Tiếp đến f(N+(M+1)) = 0 vì với mọi cách bốc s viên sỏi, 1 £ s £ M đối phương sẽ bốc tiếp u = (M+1)-s để số sỏi còn lại là N viên ứng với thế thua. Từ đó suy ra f(N) = 0 với N = k(M+1)+1; còn lại là f(N) = 1.

Hai hàm Ket(N,M) và CachDi(N,M) với N > 0 khi đó sẽ như sau.

(* Pascal *)

function Ket(N,M: integer): integer; {0: thua; 1: thang}

begin

   if (N mod (M+1) = 1) then ket := 0 else Ket := 1;

end;

function CachDi(N,M: integer): integer;

  var  r: integer;

begin

    r := N mod (M+1);

    if  (r = 1) then { thua: boc tam 1 vien }

      CachDi := 1 else

        if (r = 0)then CachDi := M

              else CachDi := r-1;

end;

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH