tailieunhanh - 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! | 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 Đồ 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 .