» Khoa Học Tự Nhiên

Một số phương pháp giải bài toán trò chơi bốc vật

Chia sẻ: AtaruMoroboshi _AtaruMoroboshi | Ngày: | Loại File: PDF | Số trang:12

Báo xấu

19
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết "Một số phương pháp giải bài toán trò chơi bốc vật" 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. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Một số phương pháp giải bài toán trò chơi bốc vật

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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.