Bốc sỏi C

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. Tại mỗi nước đi, đấu thủ buộc phải bốc tối thiểu 1 quân, tối đa nửa số quân trong đống. Đấu thủ nào đến lượt mình không đi nổi thì thua. Cả hai đấu thủ đều chơi rất giỏi. Cho biết A thắng hay thua.

Chú ý:

s         Nếu số quân lẻ thì bốc nửa non,

s         Đống nào còn 1 quân thì không có cách bốc ở đống đó,  vì 1 div 2 = 0 trong khi yêu cầu của luật chơi là phải bốc tối thiểu 1 quân.

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

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

Sơ đồ 2: Khảo sát 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)
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) ß T(N = 3)
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 = 2k - 1, k ³ 1

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, … theo lập luận lùi từ thế thua nhỏ nhất trở đi. X có thể là thế thắng V hoặc thế thua T.

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(k) có N viên sỏi: T(k) = N.
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 N viên sỏi. T(k) ß  V(k) = N + d; 1 £  d  £ N.
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) = N + d; 1 £ d £ N. T(k) ß  V(k) = N + d; 1 £ d £ N ß T(k+1) = Max {V(k)} + 1 = N+N+1
Bước 4.5	Chứng minh công thức T(k) bằng qui nạp: T(k) = 2k-1.

  

Gọi T(k) là thế thua khảo sát tại bước thứ k. Ta có,

Thế thua nhỏ nhất T(0) = 1: nếu có 1 viên sỏi thì không đi nổi: chịu thua.

Giả sử thế thua tại bước thứ k là T(k) = N

Khi đó các thế thắng dẫn đến thế T(k), theo luật chơi sẽ là V(k) = T(k)+d,
                1 £ d £ T(k) và thế thua tiếp sau đó phải là T(k+1) = T(k)+T(k)+1 = 2T(k)+1.

Tổng hợp lại ta có

   T(0) = 1,

   T(1) = 2T(0)+1 = 2+1,

   T(2) = 2T(1)+1 = 2(2+1) + 1 = 2²+2+1,

   T(3) = 2T(2)+1 = 2(2²+2+1)+1 = 2³+2²+2+1.

   ...

   Áp dụng công thức a^k+1 - 1= (a^k + a^k-1+...+a+1) (a-1) ta dự đoán: 

   T(k) = 2^k + 2^k-1+...+2+1 = (2^k+1 - 1)/(2-1) = 2^k+1 - 1.

   Ta dùng qui nạp toán học để chứng minh rằng T(k) = 2^k+1 - 1.

   Với k = 0, ta có T(0) = 2¹ - 1 = 2 - 1 = 1. Vậy T(k) đúng với k = 0.

   Giả sử T(k) =    2^k+1 - 1. Ta chứng minh  T(k+1) =    2^k+2 - 1.

   Ta có, T(k+1) = 2T(k)+1 = 2(2^k+1-1)+1 = 2^k+2-2+1 = 2^k+2-1, đpcm.

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

Nếu số sỏi N có dạng 2k - 1, k ³ 1 thì đấu thủ nào đi trước sẽ thua.

               

                Các số dạng 2^k - 1 được gọi là số Mersenne mang tên nhà toán học Pháp thế kỉ thứ XVII,  người đầu tiên nghiên cứu chúng.

                Với giả thiết A là đấu thủ đi trước, ta viết hàm Ket(N) cho ra giá trị 1 nếu A thắng, ngược lại hàm cho giá trị 0 nếu A thua. Hàm chỉ đơn thuần kiểm tra xem N có phải là số Mersenne hay không. Nếu đúng như vậy thì đấu thủ A sẽ thua, ngược lại là A thắng.

Marin Mersenne (1588-1648) là con một gia đình nông dân Pháp. Lúc đầu ông học thần học và triết học, sau chuyển sang nghiên cứu toán học và âm nhạc. Ông để lại những kết quả lý thú về cơ sở toán học của âm nhạc, hình học và lý thuyết số.

Ta để ý rằng N = 2^k-1 tương đương với N+1 = 2^k. Vì các số nguyên trong máy tính đều được biểu diễn dưới dạng nhị phân, nên để tính giá trị 2^k ta chỉ việc dịch số 1 qua trái k bit.

(* Pascal *)

function Ket(N : integer) : integer;

var m,n1: integer;

begin

   n1 := N + 1; m := 1;

   while (m < n1) do m := m shl 1;

  { m = 2^k ³ n1 = N+1 ==> N £ 2^k-1 }

   if m = n1 then Ket := 0 else Ket := 1;

end;

                Hàm CachDi dưới đây sẽ xác định số sỏi cần bốc cho mỗi tình huống. Trước hết hàm kiểm tra xem số sỏi trong đống có phải là số Mersenne hay không qua hệ thức N+1 = 2^k ? Nếu N = 2^k -1 thì người nào đi sẽ thua, do đó ta chọn cách đi chậm thua nhất bằng việc bốc 1 viên sỏi. Dĩ nhiên nếu N = 1 thì ta phải chịu thua bằng cách gán CachDi = 0. Ta xét trường hợp N không phải là số Mersenne. Khi đó tồn tại một số nguyên k thỏa 2^k - 1 < N < 2^k+1 - 1. Ta cần bốc bớt số sỏi chênh lệch là s =  N-(2^k -1)  để số sỏi còn lại có dạng 2^k - 1. Ta chứng minh 1 £ s £ N/2, tức là cách đi này là hợp lệ theo quy định của đầu bài.  Thật vậy, do 2^k - 1 < N nên s = N-(2^k -1) ³ 1. Mặt khác, nếu s > N/2 tức là N-(2^k-1) > N/2 thì N/2 > 2^k-1 hay N > 2^k+1-2. Từ đây suy ra N ³ 2^k+1-1 mâu thuẫn với điều kiện của k. Vậy ta phải có s £ N/2.

(* Pascal *)

function CachDi(N : integer) : integer;

var m, n1: integer;

begin

   n1 := N + 1; m := 1;

   while (m < n1) do m := m shl 1;

  { m = 2^k ³ n1 = N+1 ==> N £ 2^k-1 }

   if m = n1 then { N = 2^k - 1:  Thua }

   begin

      if N = 1 then CachDi := 0 

        else CachDi := 1;

      exit;

   end;

   { m = 2^k > N+1 }

    m := m shr 1;

   { m = 2^k-1 < N+1 < 2^k = 2m ==> m-1 < N < 2m-1 }

    CachDi := N-m+1;

end; 

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH