Xem mẫu
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN TRÒ CHƠI
BỐC VẬT
Đặng Huy Ruận
Trường Đại học Khoa học tự nhiên, ĐHQG Hà Nội
Tóm tắt nội dung
Trên bàn có một hay nhiều đống vật với số lượng hữu hạn. Hai đấu thủ thực hiện trò
chơi bốc các vật với người đi đầu được xác định ngẫu nhiên và bằng cách mỗi người đến
lượt phải bốc ít nhất một vật và không được bốc quá số lượng quy định. Trong trường
hợp có nhiều đống vật cũng chỉ được bốc ở một trong những đống còn vật.
Về thắng thua có hai cách qui định: Hoặc người bốc được vật cuối cùng thắng cuộc,
hoặc người không phải bốc vật cuối cùng thắng cuộc. Trong bài viết này chỉ xi n trình bầy
thuật toán bốc các vật đảm bảo cho người bốc được vật cuối cùng thắng cuộc.
Trường hợp có một đống vật trò chơi được gọi là Trò chơi đơn, còn trường hợp có nhiều
đống vật trò chơi được gọi là Trò chơi hợp.
Cả hai dạng trò chơi đều có hai cách giải quyết. Cách thứ nhất sử dụng tính chất đồng
dư được gọi là phương pháp đồng dư. Cách thứ hai sử dụng nhân của đồ thị được gọi là
phương pháp đồ thị.
1 Một số khái niệm và kết quả cần dùng
1.1 Đồ thị có hướng
Định nghĩa 1. Trên mặt phẳng hoặc trong không gian lấy n điểm tùy ý khác nhau và ký
hiệu bằng x1 , x2 , . . . , xn .
Giữa một số cặp điểm được nối bằng những đoạn thẳng hoặc đoạn cong được định
hướng.
Người ta gọi hình nhận được là một đồ thị có hướng đồng thời ký hiệu bằng G.
Các điểm đã chọn xi (1 ≤ i ≤ n) được gọi là các đỉnh, còn các đoạn thẳng hoặc đoạn
cong được định hướng đã nối được gọi là các cung của đồ thị G.
Nếu ký hiệu tập đỉnh bằng X, còn tập cung bằng E, thì đồ thị G còn được ký hiệu
bằng G(X, E).
Giả sử cung u đi từ đỉnh xi sang đỉnh x j . Khi đó xi được gọi là đỉnh đầu, còn x j được
gọi là đỉnh cuối của cung u.
Cặp đỉnh xi , x j được gọi là hai đỉnh kề nhau, nếu chúng là hai đầu của cùng một
cung.
Định nghĩa 2 (Nhân của đồ thị). Tập con A ⊆các đỉnh của đồ thị G = (X, E) được gọi là
nhân của đồ thị G, nếu
5
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
1) Hai đỉnh tùy ý x, y∈A đều không kề nhau.
2) Đỉnh tuỳ ý u không thuộc A đều tồn tại đỉnh v∈A, để từ u vào v có cung.
1.2 Đồ thị hợp
Giả sử có n đa đồ thị có hướng với các tập đỉnh không giao nhau từng đôi một G1 (X1 ,
E1 ), G2 (X2 , E2 ),. . . , Gn (xn , En ).
Xét tích đề các của các tập đỉnh X1 , X2 , . . . , Xn
X = X1 × X2 × · · · × Xn = {( x1 , x2 , . . . , xn )| xi ∈ Xi (1 ≤ i ≤ n)}
và tập
0 0 0 0
E = {( x1 , x2 , . . . , xn ), ( x1 , x2 , . . . , xn )|∃i!(1 ≤ i ≤ n) (( xi , xi ) ∈ Ei )}.
Định nghĩa 3. Đồ thị G = (X, E) được gọi là đồ thị hợp của các đồ thị G1 , G2 , . . . , Gn ,
đồng thời còn được ký hiệu bằng G1 , G2 , . . . Gn .
1.3 Tổng digit
Giả sử có n số nguyên không âm C1 , C2 , . . . , Cn với các dạng khai triển nhị phân
Ck = (Ck0 , Ck1 , Ck2 , . . . ) (1 ≤ k ≤ n)
Trong số học [m](2) hay ”m theo modul 2” là số dư (bằng 0 hoặc bằng 1) nhận được
khi chia m cho 2.
Định nghĩa 4. Véctơ:
!
n n n
C= ∑ Ck0 , ∑ Ck1 , ∑ Ck2 ,....
k =1 (2) k =1 (2) k =1 (2)
được gọi là tổng digit của các số nguyên C1 , C1 , . . . , Cn , đồng thời ký hiệu bằng:
C = C1 + ˙ ...+
˙ C2 + ˙ Cn−1 +
˙ Cn
˙ 7 = [(1, 1) + (1, 1, 1)](2) = [(1, 1, 0) + (1, 1, 1)](2) = (0, 0, 1)
Ví dụ 1. 3+
3+˙ 7+˙ 13 = [(1, 1) + (1, 1, 1) + (1, 0, 1, 1)](2)
= [(1, 1, 1, 0) + (1, 1, 1, 0) + (1, 0, 1, 1)](2) = (1, 0, 0, 1)
2 Trò chơi đơn
Bài toán 1. Giả sử m, n là hai số tự nhiên m < n và n không chia hết cho m + 1.
Trên bàn có một đống gồm n vật. Hai em A, B thực hiện trò chơi bốc các vật theo các
nguyên tắc sau:
1) Người đi đầu được xác định bằng gieo đồng tiền.
2) Mỗi người đến lượt phải bốc ít nhất một vật và không được bốc quá m vật.
3) Người bốc được vật cuối cùng sẽ thắng cuộc.
Nếu em A được đi đầu, thì em phải có cách bốc các vật như thế nào để đảm bảo thắng
cuộc, tức bốc được vật cuối cùng.
Có hai cách đưa ra thuật toán bốc các vật để em A chiến thắng. Đó là phương pháp
đồng dư và phương pháp đồ thị.
6
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
2.1 Phương pháp đồng dư
Thuật toán được hình thành dựa trên cơ sở tính đồng dư theo modul (m+1)
1) Vì n không chia hết cho m+1, nên khi chia n cho m+1 nhận được số dư r (0 < r ≤
m). Bởi vậy tại bước xuất phát em A có thể bốc r vật, để trên bàn còn lại số lượng vật
bằng nguyên lần của m+1.
2) Tại các bước tiếp theo, nếu đến lượt mình em B bốc s (1 ≤ s ≤ m) vật, thì ngay sau
đó em A bốc (m+1-s) vật, nên trên bàn số lượng vật còn lại vẫn là nguyên lần của m+1.
3) Trước khi em B bốc lần cuối cùng trên bàn còn đúng m+1 vật, nhưng em B phải
bốc ít nhất 1 vật và không được bốc quá m vật. Bởi vậy, sau khi em B bốc lần cuối cùng
trên bàn còn ít nhất 1 vật và không vượt quá m vật, nên em A có quyền bốc hết số vật
còn lại này và thắng cuộc.
Ví dụ 2. Trên bàn có một đống bi gồm 14 viên. Hai em Anh, Việt thực hiện trò chơi bốc
bi theo các nguyên tắc sau:
1) Người đi đầu được xác định bằng gieo đồng tiền.
2) Mỗi người đến lượt phải bốc ít nhất một viên bi và không được bốc quá 3 viên bi.
3) Người bốc được viên bi cuối cùng sẽ thắng cuộc.
Hỏi: Nếu em Anh đi đầu, thì em phải có cách bốc bi như thế nào để thắng cuộc, tức
bốc được viên bi cuối cùng?
Giải.
Trò chơi trong ví dụ tương ứng với trường hợp n = 14, còn m = 3.
Vì 14 chia cho 4 còn dư 2, nên với tư cách người đi đầu em Anh bốc 2 viên bi, để số bi
còn lại là 12 viên.
Tiếp theo giả sử em Việt bốc 3 viên, nên trên bàn còn 9 viên bi.
Đến lượt mình em Anh bốc 1 viên bi, để số bi còn lại là 8 viên.
Đến lượt mình giả sử em Việt bốc 2 viên bi, nên trên bàn còn 6 viên bi.
Đến lượt mình em Anh phải bốc 2 viên bi, để số bi còn lại là 4 viên.
Lần cuối cùng giả sử em Việt bốc 1 viên, nên số bi còn lại 3 viên.
Đến lượt mình đồng thời là người bốc cuối cùng em Anh bốc tất cả 3 viên bi còn lại
và thắng cuộc.
2.2 Phương pháp đồ thị
Để vận dụng phương pháp này đầu tiên phải xây dựng đồ thị mô tả diễn biến cuộc
chơi, sau đó dựa vào nhân của đồ thị mà đưa ra thuật toán.
2.3 Xây dựng đồ thị G mô tả diễn biến cuộc chơi
a. Đỉnh: Lấy n+1 điểm trên mặt phẳng hoặc trong không gian và ký hiệu một cách
tương ứng bằng các số
0, 1, 2, . . . , n − 1, n
Đỉnh n được thừa nhận là đỉnh xuất, nên được đặt trong khuyên tròn có mũi tên đi
vào.
Các đỉnh
7
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
0, m + 1, 2(m + 1), . . . ., s(m + 1)(s(m + 1) < n)
được đặt trong các ô chữ nhật. Các đỉnh còn lại được đặt trong khuyên tròn.
b. Cung:
α) Từ mỗi đỉnh s (s ≥ m) xuất phát m cung với các nhãn tương ứng là
1, 2, . . . , m - 1, m
β). Từ mỗi đỉnh t (1 ≤ t ≤ m) xuất phát t cung với các nhãn tương ứng là
1, 2, . . . , t - 1, t
Cung nhãn c xuất phát từ đỉnh a sẽ đi tới đỉnh a - c
2.4 Nhân N của đồ thị G
Tập con N = {0, m + 1, 2(m + 1), . . . , s(m + 1)}với s(m+1) < n là nhân của đồ thị G.
Bởi vì
α) Từng cặp đỉnh thuộc N không có cung nối
với nhau;
β) Với các số nguyên l, r tùy ý (0 ≤ k ≤ mn+1 , 1 ≤ r ≤ m) đỉnh k(m+1)+r không thuộc
N và từ đỉnh k(m+1)+r vào đỉnh k(m+1) ∈N có cung.
2.5 Thuật toán
Giả sử n = s(m+1) + r (1 ≤ r ≤ m). Để chiến thắng em A phải xuất phát từ đỉnh n, đi
theo cung nhãn r (tức bốc r vật) để đạt được đỉnh s(m + 1) ∈N.
Đến lượt mình em B phải xuất phát từ đỉnh s(m+1) và đi theo cung nhãn r (1 ≤ r ≤
m) (tức bốc r vật) và đi tới đỉnh s(m+1) - r không thuộc nhân N.
Đến lượt mình em A xuất phát từ đỉnh s(m+1) - r đi theo cung nhãn m+1- r (1 ≤ m +
1 - r ≤ m) (tức bốc m + 1- r vật) để đạt đỉnh (s - 1)(m + 1) thuộc nhân N.
Giả sử sau một số hữu hạn bước thay nhau bốc các vật em A đạt được đỉnh k(m+1)
∈N (tức trên bàn còn k(m+1) vật. Khi đó đến lượt mình em B phải xuất phát từ đỉnh
k(m+1) đi theo cung nhãn t (1 ≤ t ≤ m) (tức bốc t vật) để tới đỉnh k(m+1)-t không thuộc
nhân N. Tiếp theo đó đến lượt A, em sẽ bốc m+1-t (1 ≤ m+1-t ≤ m) vật và lại đạt được
đỉnh (k-1)(m+1) thuộc nhân N.
Sau khi bốc lần cận cuối em A đạt được đỉnh m+1 thuộc nhân N. Khi đó đến lượt
mình em B phải xuất phát từ đỉnh m+1 và đi theo cung với nhãn p(1 ≤ p ≤ m) để tới
đỉnh m+1-p (1 ≤ m+1-p ≤ m) không thuộc nhân N. Đến lượt mình em A xuất phát từ
đỉnh m+1-p đi theo cung m+1-p (tức bốc m+1-p vật) để đạt đỉnh O∈N và thắng cuộc.
8
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
Ví dụ 3. Trên bàn có một đống diêm gồm 9 que. Hai em Dũng, Hằng thực hiện trò chơi
bốc diêm theo nguyên tắc sau:
1) Người đi đầu được xác định bằng gắp thăm;
2) Mỗi người đến lượt mình phải bốc ít nhất 1 que diêm và không được bốc quá 3 que
diêm.
3) Người nào bốc được que diêm cuối cùng sẽ thắng cuộc.
Hỏi: Giả sử em Dũng được đi đầu, thì em phải có cách bốc diêm như thế nào để
thắng cuộc, tức bốc được que diêm cuối cùng?
Giải.
Để giải bài toán này ta dùng phương pháp đồ thị.
Trò chơi trong ví dụ này tương ứng với trường hợp n = 9, còn m = 3.
Đầu tiên ta xây dựng đồ thị G mô tả diễn biến cuộc chơi. Sau đó dựa vào nhân của
đồ thị G, mà đưa ra thuật toán đảm bảo người đi đầu (em Dũng) thắng cuộc.
1. Xây dựng đồ thị G
Để có đồ thị G cần xác định đỉnh và cung.
Đỉnh: Lấy 10 điểm trên mặt phẳng hoặc trong không gian và ký hiệu một cách tương
ứng bằng các số
0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Đỉnh ký hiệu bằng số 9 được thừa nhận là đỉnh xuất phát, nên được đặt trong ô tròn
có mũi tên đi vào.
Các đỉnh 1, 2, 3, 5, 6, 7, được đạt trong các ô tròn.
Các đỉnh 0, 4, 8 được đặt trong các ô chữ nhật.
Cung:
Với mỗi k∈3, 4, 5, 6, 7, 8, 9 từ đỉnh k xuất phát ba cung với nhãn 1,2,3 đi tới ba đỉnh
tương ứng là (k-1), (k-2) và (k-3).
Từ đỉnh 2 có cung nhãn 1 đi tới đỉnh 1 và cung nhãn 2 đi tới đỉnh 0.
Từ đỉnh 1 xuất phát cung duy nhất đi tới đỉnh 0.
9
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
Đồ thị G
2.Nhân của đồ thị G
Vì từng cặp đỉnh thuộc tập N = 0, 4, 8,không có cung nối với nhau.
Các đỉnh nằm ngoài N đều có cung đi tới một đỉnh thuộc N, nên tập N là nhân của
đồ thị G.
3. Thuật toán giúp người đi đầu (em Dũng) chiến thắng.
Với tư cách người đi đầu em Dũng phải xuất phát từ đỉnh 9, đi theo cung nhãn 1, tức
bốc 1 que diêm, để đạt được đỉnh 8 thuộc nhãn N.
Tiếp theo, đến lượt em Hằng, em phải xuất phát từ đỉnh 8 và chỉ có thể đi theo một
trong ba cung thuộc đỉnh này.
Chẳng hạn, em Hằng đi theo cung nhãn 2, tức bốc 2 que diêm, để tới đỉnh 6 không
thuộc nhân N.
Vì từ đỉnh 6 có cung nhãn 2 đi tới đỉnh 4 thuộc nhân N, nên đến lượt mình em Dũng
xuất phát từ đỉnh 6 và đi theo cung nhãn 2, tức bốc 2 que diêm, để đạt đỉnh 4 thuộc nhân
N.
Lần thứ ba đến lượt mình em Hằng phải xuất phát từ đỉnh 4 và cũng chỉ được phép
đi theo một trong ba cung xuất phát từ đỉnh này. Chẳng hạn em Hằng đi theo cung nhãn
3, tức bốc tối đa là 3 que diêm, và chỉ đạt cực đại tại đỉnh 1 không thuộc nhân N. Đến
lượt mình em Dũng xuất phát từ đỉnh 1 và đi theo cung duy nhất xuất phát từ đỉnh 1 và
cung này có nhãn là 1, tức bốc nốt que diêm cuối cùng, để đạt được đỉnh 0 thuộc nhân N
và thắng cuộc.
3 Trò chơi hợp
Giả sử mi , ni (1 ≤ i ≤ k) là các số nguyên dương và ni chia cho mi +1 có dư là ri và
tổng digit các số dư r1 + r2 + · · · + rk 6= 0.
Bài toán 2. Trên bàn có k đống vật M1 , M2 , . . . Mk với các số lượng tương ứng n1 , n2 , . . . ,
nk .
Hai em A, B thực hiện trò chơi bốc các vật theo nguyên tắc sau:
1) Người đi đầu được xác định bằng gieo đồng tiền;
2) Mỗi người đến lượt chỉ được bốc ở một trong những đống còn vật, phải bốc ít nhất
một vật và nếu bốc đống thứ i (1 ≤ i ≤ k), thì không được bốc quá mi vật;
3) Người bốc được vật cuối cùng sẽ thắng cuộc.
Hỏi: Nếu em A được đi đầu, thì em phải có cách bốc các vật như thế nào để đảm bảo
thắng cuộc, tức bốc được vật cuối cùng?
Có hai cách đưa ra thuật toán bốc các vật, để em A chiến thắng. Đó là phương pháp
đồng dư và phương pháp đồ thị.
3.1 Phương pháp đồng dư
Vì ri (1 ≤ i ≤ k) là số dư nhận được khi chia ni cho mi +1 và có tổng digit
To = r1 +˙ r2 +
˙ ...+
˙ rk 6= 0
nên với tư cách người được đi đầu em A phải chọn đống nào và phải bốc số lượng
vật bằng bao nhiêu trong phạm vi cho phép, để sau khi em bốc tổng digit của số dư tất
cả các đống bằng 0.
10
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
Giả sử em A bốc vật thuộc đống thứ t (1 ≤ t ≤ k) và số lượng vật còn lại tại đống này
0
sau khi em bốc chia cho mt+1 có dư là rt . Khi đó tổng digit
0
˙ r2 +
T1 = r1 + ˙ ...+
˙ r t −1 +
˙ rt +
˙ r t +1 +
˙ . . . .+˙ rk = 0
Giả sử hai em A, B cứ thay nhau bốc các vật theo quy tắc đã định và đến một thời
điểm nào đó sau khi em B bốc số lượng vật còn lại tại đống thứ i (1≤ i ≤ k) đem chia cho
mi +1 có dư là si và tổng digit
˙ s2 +
T2 = s1 + ˙ ...+
˙ s i −1 +
˙ si +
˙ s i +1 +
˙ . . . .+˙ sk 6= 0
Sau đó đến lượt mình em A phải chọn đống nào và bốc với số lượng vật bằng bao
nhiêu trong phạm vi cho phép, để sau khi em bốc tổng digit của số dư tất cả các đống
bằng 0.
Giả sử em A bốc vật thuộc thứ l (1 ≤ l ≤ k) và số lượng vật còn lại tại đống này sau
0
khi em bốc chia cho ml+1 có dư là sl . Khi đó tổng digit
0
˙ s2 +
T3 = s1 + ˙ ...+
˙ s l −1 +
˙ sl +
˙ s l +1 +
˙ . . . .+˙ sk = 0
Cứ tiếp tục quá trình thay nhau bốc các vật như trên thì em A sẽ là người bốc được
vật cuối cùng và thắng cuộc.
Ví dụ 4. Trên bàn có ba đống bi: Đống M1 gồm 14 viên, đống M2 gồm 9 viên và đống
M3 gồm 5 viên.
Hai em Tuấn, Bình thực hiện trò chơi bốc bi theo nguyên tắc sau:
1) Người đi đầu được xác định bằng gắp thăm;
2) Mỗi người đến lượt chỉ được bốc ở một trong những đống còn bi, phải bốc ít nhất
1 viên và
- Nếu bốc đống M1 , thì không được bốc quá 4 viên,
- Nếu bốc ở đống M2 , thì không được bốc quá 3 viên,
- Nếu bốc ở đống M3, thì không được bốc quá 2 viên.
3) Em bốc được viên bi cuối cùng sẽ thắng cuộc.
Hỏi: Nếu em Bình được đi đầu, thì em phải có cách bốc bi như thế nào để thắng
cuộc, tức bốc được viên bi cuối cùng?
Giải.
Do khi chia 14 cho 5 có dư là 4, chia 9 cho 4 có dư là 1, chia 5 cho 3 có dư là 2 và
T0 = 4+ ˙ 1+
˙ 2 = (0, 0, 1) + (1, 0, 0) + (0, 1, 0) = (1, 1, 1) 6= (0, 0, 0)
nên tại bước xuất phát em Bình phải bốc 1 viên thuộc đống M1 , để số lượng còn lại
tại các đống là: M1 có 13 viên và chia 13 cho 5 có dư là 3, M2 có 9 viên và chia 9 cho 4 có
dư là 1, M3 có 5 viên và chia 5 cho 3 có dư là 2. Bởi vậy có tổng digit các số dư
T1 = 3+ ˙ 1+
˙ 2 = (1, 1, 0) + (1, 0, 0) + (0, 1, 0) = (0, 0, 0)
Đến lượt mình, giả sử em Tuấn bốc 3 viên tại đống M2 , nên số lượng sau khi em
Tuấn bốc là: M1 có 13 viên và chia 13 cho 5 có dư 3, M2 còn 6 viên và chia 6 cho 4 có
dư 2, M3 có 5 viên và chia 5 cho 3 có dư 2. Bởi vậy tổng digit các số dư T2 = 3+ ˙ 2+˙2=
(1, 1, 0) + (0, 1, 0) + (0, 1, 0) = (1, 1, 0) 6= (0, 0, 0)
Đến lượt mình em Bình bốc 3 viên ở đống M1 . Khi đó số lượng tại các đống là: M1
còn 10 viên và 10 chia hết cho 5, M2 có 6 viên và 6 chia cho 4 còn dư 2, M3 có 5 viên và 5
chia cho 3 còn dư 2. Bởi vậy tổng digit của các số dư
T3 = 0+ ˙ 2+
˙ 2 = (0, 0, 0) + (0, 1, 0) + (0, 1, 0) = (0, 0, 0)
Đến lượt mình, chẳng hạn em Tuấn bốc 4 viên tại đống M1 , nên số lượng bi còn lại
tại các đống là: M1 còn 6 viên và 6 chia cho 5 còn dư 1, M2 có 6 viên và 6 chia cho 4 còn
dư 2, M3 có 5 viên và 5 chia cho 3 còn dư 2. Bởi vậy tổng digit của các số dư
T4 = 1+ ˙ 2+
˙ 2 = (1, 0, 0) + (0, 1, 0) + (0, 1, 0) = (1, 0, 0) 6= (0, 0, 0)
11
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
Đến lượt mình, em Bình chỉ còn cách duy nhất là bốc 1 viên thuộc M1 , để số lượng
còn lại tại các đống là: Đống M1 còn 5 viên và 5 chia hết cho 5, M2 có 6 viên và 6 chia cho
4 còn dư 2, M3 có 5 viên và 5 chia cho 3 còn dư 2. Bởi vậy tổng digit của các số dư
T5 = 0+ ˙ 2+˙ 2 = (0, 0, 0) + (0, 1, 0) + (0, 1, 0) = (0, 0, 0)
Đến lượt mình, chẳng hạn em Tuấn bốc 3 viên tại đống M2 , nên số lượng bi còn lại
tại các đống là: M1 có 5 viên và 5 chia hết cho 5, M2 còn 3 viên và 3 chia cho 4 còn dư 3,
M3 có 5 viên và 5 chia cho 3 còn dư 2. Bởi vậy tổng digit của các số dư
T6 = 0+ ˙ 3+˙ 2 = (0, 0, 0) + (1, 1, 0) + (0, 1, 0) = (1, 0, 0) 6= (0, 0, 0).
Đến lượt mình, em Bình bốc 4 viên tại đống M1 , nên số lượng bi còn lại tại các đống
là: M1 còn 1 viên và 1 chia cho 5 còn dư 1, M2 có 3 viên và 3 chia cho 4 còn dư 3, M3
có 5 viên và 5 chia cho 3 còn dư 2. Bởi vậy tổng digit của các số dư T7 = 1+ ˙ 3+
˙2 =
(1, 0, 0) + (1, 1, 0) + (0, 1, 0) = (0, 0, 0).
Đến lượt mình, chẳng hạn em Tuấn bốc nốt 3 viên ở đống M2 , nên số lượng bi còn lại
tại các đống là: M1 có 1 viên và 1 chia cho 5 còn dư 1, M2 không còn viên bi nào và 0 chia
hết cho 4, M3 có 5 viên và 5 chia cho 3 còn dư 2. Bởi vậy tổng digit của các số dư
T8 = 1+ ˙ 0+˙ 2 = (1, 0, 0) + (0, 0, 0) + (0, 1, 0) = (1, 1, 0) 6= (0, 0, 0).
Đến lượt mình em Bình phải bốc 1 viên ở đống M3, nên số lượng bi còn lại tại các
đống là: M1 có 1 viên vì 1 chia cho 5 còn dư 1, M2 không còn viên nào và 0 chia hết cho
4, M3 còn 4 viên và 4 chia cho 3 dư 1. Bởi vậy tổng digit của các số dư
T9 = 1+ ˙ 0+˙ 1 = (1, 0, 0) + (0, 0, 0) + (1, 0, 0) = (0, 0, 0)
Đến lượt mình, giả sử em Tuấn bốc nốt 1 viên bi còn lại của đống M1 . Khi đó chỉ đống
M3 còn 4 viên bi và 4 chia cho 3 còn dư 1, nên tổng digit của các số dư
T10 = 0+ ˙ 0+˙ 1 = (0, 0, 0) + (0, 0, 0) + (1, 0, 0) = (1, 0, 0) 6= (0, 0, 0).
Đến lượt mình em Bình phải bốc 1 viên ở đống M3, nên đống M3 còn lại 3 viên và 3
chia hết cho 3, nên tổng digit của các số dư T11 = 0+ ˙ 0+˙ 0 = 0.
Đến lượt mình em Tuấn không thể bốc hết 3 viên bi còn lại tại đống M3, và phải bốc
ít nhất 1 viên, nên:
- Nếu em Tuấn bốc 1 viên, thì em Bình có quyền bốc cả 2 viên bi còn lại và thắng cuộc.
- Nếu em Tuấn bốc 2 viên, thì vẫn còn lại 1 viên để em Bình bốc và thắng cuộc.
3.2 Phương pháp đồ thị
Đầu tiên đối với mỗi đống vật mi (1 ≤ i ≤ k) xây dựng đồ thị Gi mô tả diễn biến cuộc
chơi tại đống mi . Sau đó xây dựng đồ thị hợp G của các đồ thị G1, G2, . . . , Gk, để mô tả
diễn biến trò chơi hợp trên các đống M1 , M2 , . . . , Mk . Cuối cùng xác định nhân N của đồ
thị G và đưa ra thuật toán đảm bảo cho người đi đầu chiến thắng.
1. Đồ thị thành phần Gi (1 ≤ i ≤ k).
Để có đồ thị Gi mô tả cuộc chơi tại đống mi cần xác định đỉnh và cung.
a. Đỉnh
Lấy ni +1 điểm trên mặt phẳng hoặc trong không gian và ký hiệu một cách tương ứng
bằng các số
0, 1, 2, . . . ., ni - 1, ni làm đỉnh của đồ thị.
Đỉnh ni là đỉnh xuất phát, nên được đặt trong ô tròn có mũi tên đi vào. Các đỉnh còn
lại đều được đặt trong khuyên tròn.
b. Cung
α ) Từ mỗi đỉnh s(s ≥ mi ) xuất phát mi cung với các nhãn tương ứng
1, 2, . . . , mi - 1, mi
β) Từ đỉnh t (1 ≤ t ≤ mi ) xuất phát t cung với các nhãn tương ứng
12
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
1, 2, . . . , t - 1, t
Cung nhãn c xuất phát từ đỉnh e sẽ đi tới đỉnh e - c
3.3 Đồ thị hợp
Từ các đồ thị thành phần G1 , G2 , . . . , Gk ta xây dựng đồ thị hợp G.
3.4 Nhân của đồ thị G
Tập N gồm các đỉnh x = (x1 , x2 , . . . , xk ) của đồ thị G, mà xi ≡ ri (mod(mi+1)) và có
tổng digit các số dư
r1 + ˙ . . . .+
˙ r2 + ˙ rk = 0
Vì các đỉnh có tổng digit các số dư bằng 0 đều không có cung nối với nhau, nên hai
đỉnh tùy ý thuộc tập N đều không có cung nối với nhau, đồng thời mỗi đỉnh có tổng
digit các số dư khác 0 (không thuộc tập N) đều có cung đi tới đỉnh có tổng digit các số
dư bằng 0, tức đi tới một đỉnh thuộc N. Bởi vậy N là nhân của đồ thị G.
3.5 Thuật toán
Dựa vào nhân N của đồ thị G ta đưa ra thuật toán cho người đi đầu chiến thắng, tức
bốc được vật cuối cùng.
Vì đỉnh x = (n1 , n2 , . . . , nk ) có ni ≡ ri (mod mi + 1)
và
˙ r2 +
r1 + ˙ . . . .+
˙ rk 6= 0,
nên x ∈ / N và từ x có cung với nhãn at (1 ≤ at ≤ mt )(1 ≤ t ≤ k ) đi vào đỉnh y ∈ N.
Bởi vậy em A có quyền bốc at vật thuộc đống Mt .
Đến lượt mình, em B phải xuất phát từ đỉnh y, nhưng xuất phát từ đỉnh y chỉ có cung
đi tới các đỉnh nằm ngoài nhân N. Bởi vậy em B chỉ có thể bốc số lượng vật là nhãn của
cung đi từ nhân ra ngoài, nên em B chỉ có thể đạt đỉnh mà tổng digit của các số dư khác
0.
Sau đó, đến lượt mình em A lại có thể xuất phát từ đỉnh ngoài nhân N, mà em B vừa
đạt được để đi vào một đỉnh thuộc nhân N.
Cứ tiếp tục như vậy hai em A, B lần lượt thay nhau đi vào nhân N rồi lại ra khỏi nhân
N và bốc số lượng vật theo nhãn của các cung đi qua và đến cuối cùng em A đạt được
đỉnh 0, tức là bốc được vật cuối cùng và thắng cuộc.
13
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
Ví dụ 5. Trên bàn có hai đống bi với số lượng tương ứng: Đống M1 gồm 5 viên, đống M2
gồm 7 viên.
Hai em Hoè, Liên thay nhau bốc bi theo nguyên tắc:
1) Người đi đầu được xác định bằng gieo đồng tiền;
2) Mỗi người đến lượt chỉ được bốc tại một trong hai đống, phải bốc ít nhất 1 viên và
- Nếu bốc ở đống M1 , thì không được bốc quá 2 viên,
- Nếu bốc ở đống M2 , thì không được bốc quá 3 viên.
3) Người nào bốc được viên cuối cùng sẽ thắng cuộc.
Hỏi: Nếu em Hoè được đi đầu, thì em phải co cách bốc bi như thế nào để thắng cuộc,
tức bốc được viên bi cuối cùng?
Giải. Ta sẽ giải bài toán này bằng phương pháp đồ thị.
1) Xây dựng các đồ thị G1 , G2 để mô tả diễn biến cuộc chơi tại các đống M1 và M2
2. Xây dựng đồ thị hợp G.
14
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
15
- Hội thảo khoa học, Ninh Bình 15-16/09/2018
3. Thuật toán cho em Hoè là người đi đầu chiến thắng.
Đồ thị hợp G có nhân N gồm các đỉnh (5,6), (4,5), (3,4), (5,2), (2,6), (4,1), (1,5), (0,4), (2,
2), (1,1), (3,0) và (0,0) nên tại bước xuất phát với tư cách người được đi đầu em Hoè xuất
từ đỉnh (5,7) đi theo cung nhãn 1 để đạt đỉnh (5,6) thuộc N, tức em Hoè phải bốc tại đống
M2 1 viên, để đống M2 còn 6 viên, còn đống M1 vẫn giữ nguyên số lượng cũ là 5 viên.
Đến lượt mình, em Liên phải xuất phát từ đỉnh (5,6) và đi theo một trong những cung
thuộc đỉnh này. Chẳng hạn, em Liên đi theo cung nhãn 2 đi tới đỉnh (3,6), tức là bốc 2
viên ở đống thứ M1 , để đống M1 còn 3 viên và đống M2 vẫn giữ nguyên số lượng cũ là
6 viên.
Đến lượt mình, em Hoè xuất phát từ đỉnh (3,6) đi theo cung nhãn 1 sang đỉnh (2,6)
thuộc N, tức bốc 1 viên ở đống M1 , để đống M1 còn 2 viên và đống M2 vẫn giữ số lượng
cũ là 6 viên.
Đến lượt mình, em Liên phải xuất phát từ đỉnh (2,6) và đi theo một trong những cung
xuất phát từ đỉnh này. Chẳng hạn, em Liên đi theo cung nhãn 3 để về đỉnh (2,3) tức bốc
3 viên thuộc đống M2 , để đống M2 còn 3 viên và đống M1 vẫn giữ nguyên số lượng cũ
là 2 viên.
Đến lượt mình, em Hoè xuất phát từ đỉnh (2,3) đi theo cung nhãn 1 để về đỉnh (2,2)
thuộc N, tức bốc 1 viên ở đống M2 , để M2 còn 2 viên và M1 giữ nguyên số lượng cũ là 2
viên.
Đến lượt mình, em Liên phải xuất phát từ đỉnh (2,2) và đi theo một trong những cung
xuất phát tại đỉnh này. Chẳng hạn, em Liên đi theo cung nhãn 2 để về đỉnh (0,2), tức bốc
2 viên tại đống M1 . Khi đó đống M1 hết bi, còn đống M2 vẫn giữ nguyên số lượng cũ là
2 viên.
Đến lượt mình, em Hoè xuất phát từ đỉnh (0,2) đi theo cung nhãn 2 để về đỉnh (0,0)
thuộc N, tức bốc nốt 2 viên bi cuối cùng và thắng cuộc.
Tài liệu
[1] Đặng Huy Ruận, Lý thuyết đồ thị và ứng dụng
Nhà xuất bản Khoa học kỹ thuật, 2002.
[2] Claude Berge. Theorie des graphes et ses applications. Dunod. Paris 1967
[3] Đặng Huy Ruận. Trò chơi và đồ thị Nhà xuất bản Khoa học kỹ thuật, 2004
[4] Đặng Huy Ruận. Phương pháp giải bài toán chia hết Nhà xuất bản Khoa học kỹ thuật,
2005
16
nguon tai.lieu . vn
