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

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!
Nội dung trích xuất từ tài liệu:
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/2018MỘ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 đượckhi 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 đơnBà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ácnguyê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 ...