Lý thuyết trò chơi và sắp xếp

Lý thuyết trò chơi và sắp xếp

Lí thuyết trò chơi và sắp xếp là 1 loại toán rất hay, yêu cầu tính tư duy, suy luận và sáng tạo cao. Trên box Toán của chúng ta, từ trước đến nay, mọi người cũng đã đưa ra nhiều bài toán trò chơi rất hay.Vì vậy, hôm nay tôi lập topic này, để chúng ta cùng nhau thảo luận về các bài toán trò chơi,Mong rằng mọi người có thể tìm thấy nhiều điều bổ ích,và ứng dụng trong cuọc sống.
Xin mọi người hãy thử với chùm bài toán này:


BÀI TOÁN 1: Một tấm bảng có tính chất sau:Nếu ta viết dãy số nguyên a1, a2, a3......a(n), thì khi viét số hạng a(n) thì số hạng đứng trước nó 3 bước tức số hạng a(n) - 3 sẽ tự động tăng thêm 1 đơn vị.Có thể viết dãy số 1, 2, 3,....13 trên bảng đó hay không?


BÀI TOÁN 2:Trong hộp có 2000 viên sỏi, Có 2 người tham gia 1 trò chơi,mỗi người lần lượt phải bốc ít nhất là 11 viên, nhiều nhất lag 20 viên.Người nào bốc viên sỏi cuối cùng là người thua cuộc.hãy tìm thuật chơi để đảm bảo người bốc đầu tiên là người thắng cuộc

Được home_nguoikechuyen sửa chữa / chuyển vào 06/01/2003 ngày 11:11

Ờ đúng vậy, bác home này lười nhỉ? Mà kô biết box ta có tham gia Cybergame kô nhỉ? Box toán chắc nhiều game thủ lắm.
Cây cải đắng quên lòng mình đang đắng
Trổ hoa vàng để dọc suối ong bay

Cái gì vậy?hơ hơ, mình vẫn chưa hiểu lắm 2 bài trả lời của các bạn đối với bài của home??
+++
Đây là mảng toán hay thôi chứ thực sự là nó không khó lắm, nên hi vọng những bài toán về dạng này sẽ lôi cuốn được mọi người như nó là trò chơi vậy?
"Các bạn gái xinh xinh và duyên dáng,
Trước khi yêu xin nhớ lấy câu này:
Các chàng trai như sao trời sáng chói,
Long lanh nhiều nhưng chẳng sáng bao nhiêu"....

Hì , bài 1 nè thằng bạn :
Đáp số là có. Thật vậyta viết 13 số 0,1,2,3,4,5,6,7,8,9,11,12,13 thì theo bài ra sẽ được dãy 1,2,3,4,5,6,7,8,9,10,11,12,13.
Hoàng Kiên Trung

Hơ, đố gì mà dễ vậy.
Bài 1: chưa đọc đề mà hình như có chú nào giải rồi thì phải. Không care.
Bài 2: thằng 1 bốc 16 viên, sau đó cứ thằng 2 bốc x viên thì thằng 1 bốc 31-x viên => thế là thắng.
Đối với các bài toán trò chơi thì vấn đề đặt ra thường là tìm cách chơi để xác suất thắng là lớn nhất chứ còn luôn thắng như trên thì không hay với lại thường là rất dễ.

Giới thiệu về lý thuyết trò chơi.
Mặc dầu lý thuyết trò chơi được áp dụng vào nhiều lĩnh vực khác nhau nhưng về căn bản đó là lý thuyết về quy hoạch và liên quan đến sự phân tích các hướng tối ưu của hành động. Nó giả thiết bức tranh tổng quát của trò chơi được biết rõ, nghĩa là các đối thủ biết rõ các bước mình và đối phương có thể đi và kết quả của chúng. Xuất phát từ giả thiết đó lý thuyết trò chơi phân tích một cách khách quan tình thế xung đột quyền lợi của các bên tham gia trò chơi. Lý thuyết trò chơi đưa ra các phương thức hành động tối ưu đối với các đối thủ tham gia vào trò chơi.
Lý thuyết trò chơi có thể được áp dụng vào rất nhiều lĩnh vực như kinh tế, chính trị,.... Về kinh tế thì ví dụ đơn giản rồi vì các doanh nghiệp có thể coi là các đối thủ trong một trò chơi mà họ cần phải có hành động tối ưu để thu được lợi nhuận cực đại (tất nhiên là không phải bằng cách buôn lậu hay trốn thuế). Còn trên lĩnh vực chính trị thì ta có thể lấy ví dụ như cuộc chạy đua hạt nhân giữa hai cường quốc là Liên xô (cũ) và Mỹ, theo lý thuyết trò chơi thì cả hai bên đều phải phát triển vũ khí hạt nhân thì mới là hành động tối ưu (đạt được cân bằng Nash).
Lý thuyết trò chơi liên quan chặt chẽ tới lý thuyết xác suất và thống kê đặc biệt là quy hoạch tuyến tính. Các trò chơi ban đầu thường là các trò chơi hai người, đánh cờ vua hay cờ tướng có thể coi là thuộc dạng này. Bắt đầu từ những năm 1930, Jonh Von. Neumann đã bắt đầu nghiên cứu các lý thuyết các trò chơi tổng quát hơn, đặc biệt là về mặt toán học. Năm 1944, Von Neumann và Oskar Morgenstern đã công bố bài báo với tên ?obài toán trò chơi với n người?, ví dụ bạn có thể hình dung như trò túlơkhơ hay tá-lả mà ta vẫn đánh có bốn người. Sau đó thì đã có rất nhiều các nghiên cứu đã nghiên cứu về lý thuyết trò chơi.
Girl of the Moon

Chị Girl này, nếu được chị giải thích rõ hơn về lí thuyết trò chơi này đi, cho một ví dụ cụ thế chẳng hạn...Em nhớ có lần nghe nói về lí thuyết này, áp dụng vào việc ...cá độ đá banh! Tính đọc thêm về vấn đề này, nhưng ngại kiếm trên mạng quá, chờ chị post thêm. Hihi, hứa sẽ vote cho chị 5 *

Ờ, cái vụ cá độ bóng đá bằng lý thuyết trò chơi thì đây là lần đầu tiên mình nghe thấy đấy.

Bài toán đơn giản
Cảnh sát bắt hai tên bị tình nghi là trộm rồi giam riêng hai tên ở hai phòng cách biệt và giải thích cho mỗi tên là nếu một tên không khai báo mà tên kia khai báo thì tên khai báo được thả ngay còn tên kia (không khai báo) sẽ bị tù 9 tháng, nếu cả hai cùng khai báo thì cả hai sẽ bị tù 6 tháng, còn nếu không ai khai báo thì cả hai sẽ được thả ngay.
Đây là bài toán trò chơi đơn giản nhất với người chơi chính là hai tên bị tình nghi còn cách chơi là chọn một trong hai khả năng (tức là chọn một trong hai nước đi): khai báo hoặc không khai báo, kết quả thì ta đã biết ứng với mỗi nước đi thì sẽ có kết quả ra sao.

Rõ ràng ta thấy nếu cả hai không khai báo là lợi nhất cho cả hai nhưng vì không có thông tin chắc chắn là đối phương sẽ chọn nước gì nên nếu chọn nước đi không khai báo mà đối phương lại chọn nước khai báo thì mình sẽ bị tù 9 tháng còn nếu chọn nước khai báo thì nhiều nhất là cũng bị giam 6 tháng còn may mắn (tức là khi đối phương chọn không khai báo) thì được thả ngay. Như vậy ta nói nước khai báo là trội ngặt hơn so với nước không khai báo.
Vậy kết quả sẽ là cả hai tên đều cùng chọn nước khai báo.
Điểm chọn đó gọi là cân bằng Nash.
Lập luận này cũng chính là lập luận khi ta đánh cờ vua hoặc cờ tướng. Thuật toán alpha-beta dùng để lập trình chương trình đánh cờ trên máy tính cũng dựa trên lập luận tương tự.
Ta cũng có thể ứng dụng bài toán này vào cuộc chạy đua hạt nhân giữa Liên xô(cũ) và Mỹ, rõ ràng theo lý luận tương tự trên, nếu mình không phát triển vũ khí hạt nhân mà đối phương phát triển thì mình thua, còn nếu mình phát triển thì cùng lắm là hoà (tức là khi cả hai bên cùng phát triển như nhau) => cả hai cùng phát triển vũ khí hạt nhân.
Girl of the Moon

hic, ai bảo dễ đấy nhỉ????Do đó là bài toán mở đầu topic nên ra đề dễ để mọi người tham gia đấy thôi. Đề khó kiếm khó gì!!!!!
Ngoài ra rất cảm ơn girl vì ví dụ rất thú vị
------------------------------------
Có khi mưa ngoài trời là giọt nước mắt em.

Bài toán 3Trong cung điện nhà vua Actua tập trung 2n hiệp sĩ , biết rằng mỗi hiệp sĩ có không quá n-1 kẻ thù, trong 2n hiệp sĩ đó.CMR:quân sư của nhà vua có thể sắp xếp đắt các hiệp sĩ quanh 1 bàn tròn sao cho không có ai ngồi cạnh kẻ thù của họ.
bài toán 4 3 người A, B, C chơi 1 cỗ bài gồm 3 quân.Trên mỗi quân bàì có in 1 số nguyên.3 số nguyên p, q, r ấy thoả mãn điè kiện : 0< p<q< r.Mỗi người phát 1 quân bài và nhận được số que bằng số in trên mỗi quan bài ấy.Sau đó các quân bài được thu lại , xáo trộn và được phát lại., còn các người chơi vần giữ lại số que nhận được . Sau 1 số N > 2 lượt phát
A nhận được cả thảy 2o que, B nhận được 10 que,C nhận được 9 que.Biết rằng B nhận được r que trong lượt phát cuối cùng. Hỏi ai nhận được q que trong lượt phát đầu tiên
------------------------------------
Có khi mưa ngoài trời là giọt nước mắt em.