Bốc sỏi F

Cho 2 đống sỏi với số viên sỏi lần lượt là N và M viên, N, M  > 1. Hai người chơi A và B, A luôn đi trước. Lượt chơi: Chọn đống tùy ý, bốc tối thiểu 1 viên và tối đa nửa số viên của đống. Đấu thủ nào đến lượt mình mà  không đi nổi thì thua. Hãy cho biết A thắng hay thua. Giả thiết rằng hai đấu thủ  đều chơi rất  giỏi.

Thuật toán

Mới xem ta thấy rằng bất biến thua cho bài này cũng là N = M. Dự đoán của bạn gần đúng vì N = M chỉ là một trường hợp đặc biệt của bất biến thua. Dễ thấy, nếu N = M =1 thì hết cách đi. Nếu N = M > 1 và A đi trước thì B chỉ việc cân bằng lại số sỏi của hai đống là chắc thắng. Vậy N = M là một điều kiện thua (cho người đi trước). 

Để lập bảng tính trị của hàm f(N,M) ta cũng nhận xét rằng hàm này đối xứng, tức là f(N,M) = f(M,N) vì trật tự của các đống sỏi là không quan trọng. Cũng chính vì f(N,M) là hàm đối xứng nên ta chỉ cần tính trị của f(N,M) với N £ M rồi lấy đối xứng qua đường chéo chính của bảng trị. Với mỗi N cho trước ta lần lượt điền từng dòng N của bảng với M = N, N+1, N+2,… Theo nhận xét trên ta có ngay f(N,N) = 0 với mọi N. Từ thế thua này ta thấy ngay f(N,N+d) = 1 với mọi d = 1,2,…N vì từ các thế này ta có thể bốc d viên từ đống thứ hai (đống có M=N+d viên) để dẫn đến thế thua f(N,N). Từ đây suy ra thế thua tiếp theo sẽ là f(N,N+N+1) = f(N,2N+1). Tương tự, thế thua tiếp sau thế này phải là f(N,2(2N+1)+1) = f(N,2²N+2+1). Tổng qúat hóa ta thu được kết quả sau:

                Nếu đống sỏi thứ nhất có N viên thì các thế thua sẽ có dạng f(N,M) với M = 2^kN+2^k-1+…+2+1 = 2^kN+(2^k-1+…+2+1). Áp dụng công thức

2^k-1 = (2-1)(2^k-1+2^k-2+…+2+1) = 2^k-1+2^k-2+…+2+1

ta thu được M = 2^kN+2^k-1 hay M+1 = 2^k(N+1).

   Vậy

Bất biến thua  cho Bài Bốc sỏi F

Số sỏi trong hai đống thỏa hệ thức (N+1) = 2k(M+1), k ³ 0   (*)

                Từ hệ thức (*) ta suy ra N = M là trường hợp riêng khi k = 0. 

                Hàm Ket và thủ tục CachDi khi đó sẽ như sau.

Để ý rằng các số nguyên trong máy tính được biểu diễn dưới dạng nhị phân nên giá trị 2^k tương đương với toán tử dịch trái 1 k bit,  1 shl k.

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

   var N1,M1,t: integer;

begin

    N1 := N+1; M1 := M+1;

  if N1 < M1 then

    begin

       t := N1; N1 := M1; M1 := t;

    end; { N1 ³ M1 }  

  while M1 < N1 do M1 := M1 shl 1; { 2*M1 }

  if (M1 = N1) then Ket := 0 else Ket := 1;

end;

Với thủ tục CachDi cho tình huống thua thì A đành bốc 1 viên ở đống nhiều sỏi. Trong trường hợp thắng ta cũng chọn đống nhiều sỏi để bốc bớt S viên sao cho số sỏi giữa hai đống thỏa hệ thức (*). Ta tính S như sau. Giả sử N > M và k là số nguyên đầu tiên thỏa hệ thức N+1  <  2^k(M+1). Khi đó, do điều kiện thắng nên ta phải có 2^k-1(M+1) < N+1 < 2^k(M+1) . Vậy số sỏi chênh lệch cần bốc bớt ở đống nhiều sỏi sẽ là S = N+1-2^k-1(M+1). Ta chứng minh rằng 1 £ S £ N/2. Thật vậy, vì 2^k-1(M+1) < N+1 nên S = N+1-2^k-1(M+1) ³ 1. Mặt khác, nếu S > N/2 thì 2S > N hay 2N+2-2^k(M+1) > N. Từ đây rút ra N+1 >  2^k(M+1)-1, hay N+1 ³  2^k(M+1), mâu thuẫn với giả thiết về k.

procedure CachDi(N,M : integer; var D,S : integer);

    var N1,M1,t: integer;

begin

   { N = M = 1: dau hang }

   if (N = M) and (N = 1) then

    begin

       D := 0; S := 0;

       exit;

    end;

   { Chon dong nhieu soi }

   if N > M then D := 1 else D := 2;

   N1 := N+1; M1 := M+1;

   if N1 < M1 then

    begin

       t := N1; N1 := M1; M1 := t;

    end; { N1 ³ M1 }

   while M1 < N1 do M1 := M1 shl 1; { 2*M1 }

   if (M1 = N1) then { Thua }

      begin  { Se Thua }

         S := 1; { boc 1 vien }

         exit;

      end;

   { Cac tinh huong thang }

   M1 := M1 shr 1;

   S := N1-M1;

end; 

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH