Trò chơi NIM có xuât xứ từ Trung Hoa, dành
cho hai đấu thủ A và B với các nước đi lần lượt đan nhau trên một đấu trường
với N đống sỏi. Người nào đến lượt đi thì được chọn tùy ý một đống sỏi và bốc
tối thiểu là 1 viên, tối đa là cả đống đã chọn. Ai đến lượt mình không thể thực
hiện được nước đi sẽ thua. Ta giả thiết là A luôn đi trước và hai đấu thủ đều
chơi rất giỏi. Cho biết A thắng hay thua?
Thuật toán
Gọi số viên sỏi trong
các đống là S1, S2,…,
SN.
Kí hiệu Å là tống loại trừ (xor). Đặt x = S1Å S2
Å
… Å
SN. Ta chứng minh rằng bất biến thua của trò chơi NIM là x = 0,
tức là nếu x = 0 thì đến lượt ai đi
người đó sẽ thua.
Trước hết nhắc lại một số tính chất của phép toán Å theo
bit.
1) a Å b = 1 khi và chỉ khi a ≠ b.
2) a Å 0 = a
3) a Å 1 = not a
4) Tính giao hoán: a Å b = b Å a
5) Tính kết hợp: (a Å b) Å
c = a Å
(b Å c)
6) Tính lũy linh: a Å a = 0
7) a Å b Å a = b
8) Tính chất 7 có thể mở rộng như sau: Trong một biểu thức
chỉ chứa phép xor ta có thể xóa đi chẵn lần các phần tử giống nhau, kết quả sẽ
không thay đổi.
Để dễ nhớ ta gọi phép toán này là so khác – so xem hai đối tượng có khác
nhau hay không. Nếu khác nhau là đúng (1) ngược lại là sai (0).
Bất biến x = 0 có
ý nghĩa như sau: Nếu viết các giá trị Si,
i = 1..N dưới dạng nhị phân vào một bảng thì số lượng số 1 trong mọi cột
đều là số chẵn.
|
|
Dạng
nhị phân
|
|||
|
S1
= 13
|
1
|
1
|
0
|
1
|
|
S2
= 14
|
1
|
1
|
1
|
0
|
|
S3
= 6
|
0
|
1
|
1
|
0
|
|
S4
= 7
|
0
|
1
|
1
|
1
|
|
S5
= 2
|
0
|
0
|
1
|
0
|
|
Å x = 0
|
0
|
0
|
0
|
0
|
Bảng bên cho ta S1ÅS2ÅS3ÅS4ÅS5 = 13Å14Å6Å7Å2 =
0.
Nếu x là tổng xor
của các Si, i = 1..N, với mỗi i = 1..N ta kí hiệu K(i) là tổng xor khuyết i của các Si
với cách tính như sau: K(i) = S1
Å
S2 Å … Å Si-1 Å Si+1Å … Å SN. Như vậy K(i) là tổng xor của các Sj sau khi đã loại trừ phần
tử Si và x chính là tổng xor đủ của các Si, i = 1..N. Do Si Å Si
= 0 và 0 Å
y = y với mọi y nên K(i)
= x Å Si. Để cho tiện,
ta cũng kí hiệu K(0) chính là tổng
xor đủ của các Si, i = 1..N. Với thí dụ đã cho ta tính được các
tổng khuyết như sau:
K(0) = S1ÅS2ÅS3ÅS4ÅS5 = 13Å14Å6Å7Å2 = 0.
K(1) = S2ÅS3ÅS4ÅS5 = 14Å6Å7Å2 =
13,
K(2) = S1ÅS3ÅS4ÅS5 = 13Å6Å7Å2 =
14,
K(3) = S1ÅS2ÅS4ÅS5
= 13Å14Å7Å2 =
6,
K(4) = S1ÅS2ÅS3ÅS5
= 13Å14Å6Å2 =
7,
K(5) = S1ÅS2ÅS3ÅS4
= 13Å14Å6Å7 =
2.
Ta
phát hiện được qui luật lí thú sau đây:
Mệnh đề 1. Cho x là tổng xor của N số tự nhiên, Si,
x = S1ÅS2Å...ÅSN.
Khi đó K(i) = x Å Si, i =
1,2,...,N. Tức là muốn bỏ một số hạng trong tổng Å ta chỉ việc Å thêm
tổng với chính số hạng đó. Nói riêng, khi x = 0 ta có K(i) = Si, i = 1,2,...,N.
Chứng minh
Gọi x
là tổng xor đủ của các số đã cho, x =
S1ÅS2Å...ÅSN. Vận dụng ính giao hoán và tính lũy đẳng ta có thể
viết x Å Si = (S1ÅS2Å...ÅSi-1ÅSi+1ÅSN)Å(SiÅSi) = K(i) Å 0 = K(i), i
= 1,2,...,N, đpcm.
Ta chứng minh tiếp các mệnh đề sau:
Mệnh đề 2. Nếu x ≠ 0 thì có cách đi hợp lệ để biến đổi x =
0.
Chứng minh
Do x ¹ 0 nên ta xét chữ số 1 trái nhất trong
dạng biểu diễn nhị phân của x = (xm,
xm-1,…,x0), xj = 1, xi
= 0, i > j. Do x
là tổng xor của các Si, i
= 1..N, nên tồn tại một Si = (am, am-1,…,a0) để chữ số aj = 1. Ta chọn đống Si này (dòng có dấu *). Khi
đó, ta tính được K(i) = x
Å Si = (xmÅam, xm-1Åam-1,…,x0Åa0) = (bm,
bm-1,…,b0) với bi = xiÅai, 0 £ i
£ m. Ta có nhận xét sau đây:
* Tại các cột i > j: bi = ai, vì bi = xiÅai = 0 Å ai
= ai,
* Tại cột j ta có:
bj = 0, vì bj = xj Å aj
= 1 Å 1 = 0.
Do aj = 1, bj = 0 và mọi vị trí
i > j đều có bi = ai nên Si > K(i).
Nếu ta thay dòng Si bằng
dòng K(i) thì tổng xor y khi đó
sẽ là
|
|
Dạng nhị phân
|
|||
|
x3
|
x2
|
x1
|
x0
|
|
|
S1 = 12
|
1
|
1
|
0
|
0
|
|
S2 = 14
|
1
|
1
|
1
|
0
|
|
* S3 = 6
|
0
|
1
|
1
|
0
|
|
S4 = 3
|
0
|
0
|
1
|
1
|
|
S5 = 2
|
0
|
0
|
1
|
0
|
|
Å x = 5
|
0
|
1
|
0
|
1
|
y
= (x Å Si) Å K(i) = K(i) Å K(i) = 0.
Vậy, nếu ta bốc tại đống i số viên sỏi v = Si-K(i) thì số sỏi còn lại
trong đống này sẽ là K(i) và khi đó tổng xor sẽ bằng 0, đpcm.
Mệnh
đề 3. Nếu x = 0 và còn đống sỏi khác 0 thì
mọi cách đi hợp lệ đều dẫn đến x
≠ 0.
Chứng
minh
Cách đi hợp lệ là cách đi làm giảm thực sự số sỏi của một
đống Si duy nhất nào đó, 1 £ i £
N. Giả
sử đống được chọn là Si
= (am,
am-1,…,a0). Do Si bị sửa nên chắc chắn có một bit nào đó bị đảo (từ 0
thành 1 hoặc từ 1 thành 0). Ta gọi bít bị sửa đó là aj. Khi đó tổng số bít 1 trên cột j sẽ bị tăng hoặc giảm
1 đơn vị và do đó sẽ không còn là số chẵn. Từ đó suy ra rằng bit j trong x sẽ là 1, tức là x ≠ 0
đpcm.
Phần
lập luận chủ yếu trong mệnh đề 2 nhằm mục đích chỉ ra sự tồn tại của một tập Si thỏa tính chất Si > xÅSi. Nếu tìm được tập Si như vậy ta sẽ bốc Si-(xÅSi) viên tại đống sỏi i.
Giả thiết rằng mảng S[1..N]
kiểu nguyên chứa số lượng sỏi của mỗi đống đã khởi tạo như một đối tượng dùng
chung, ta viết hàm Ket và thủ tục CachDi
như sau.
Hàm Ket sẽ cho ra giá
trị là tổng xor x của các đống sỏi.
Như vậy, khi x = 0 thì người nào đi
sẽ thua, ngược lại, khi x ≠ 0 thì người
nào đi sẽ thắng.
function Ket(N: integer): integer;
var x, i: integer;
begin
x := 0;
for i := 1 to N do x :=
x xor S[i];
Ket := x;
end;
Thủ tục CachDi hoạt động như
sau:
Gọi hàm x = Ket.
Nếu x = 0 tức là sẽ thua thì chọn một
đống còn sỏi, thí dụ đống còn nhiều sỏi nhất, để bốc tạm 1 viên nhằm kéo dài
cuộc chơi. Nếu x = 0 và các đống đều hết sỏi thì đương nhiên là phải chịu
thua. Trường hợp x ¹
0 thì ta tìm cách đi chắc thắng như sau:
Bước 1. Tìm đống sỏi i thỏa điều kiện x Å
Si < Si.
Bước 2. Bốc tại đống i đó Si - (xÅSi) viên.
procedure CachDi(N: integer; var D,V: integer);
var x,i: integer;
begin
x := Ket(N);
if x = 0 then { Thua }
begin
D := 1;
for i := 2 to N do
if (S[i] >
S[D]) then D := i;
if (S[D] = 0) {Het
soi: Dau hang}
then D := 0
else S := 1;
exit;
end;
{ Chac thang }
for D:=1 to N do
if (s[D] > (x xor
S[D])) then
begin
V := S[D]-(x xor
S[D]); {boc V vien tai dong D }
exit;
end;
end;
Trong các hàm C# dưới đây mảng s
được khai báo n phần tử, các phần tử được mã số từ 0 đến n-1, trong khi các đống sỏi
được mã số từ 1 đến n do đó chúng ta phải lưu ý chuyển đổi chỉ số cho thích hợp.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét