Đặt cược tốt nhất cho người đơn giản

4

CƯỢC TỐT NHẤT
CHO ĐƠN GIẢN

Ứng viên Khoa học Vật lý và Toán học
P. A. PEVZNER

• Tại sao bạn không bao giờ chơi? - Kid hỏi Smoke trong lần họ làm chuyện đó ở Deer Rose. Bạn không thực sự muốn đến bàn ăn bánh tart sao?
  “Tuyết,” Smoke trả lời. “Nhưng tôi biết số liệu thống kê về sản lượng và tôi cần một con số gần đúng.”

Jack London, Khói Bellew

Có thể bạn đã biết trò chơi ngửa: người chơi A chọn một mặt nào đó của đồng xu (ví dụ: O - mặt ngửa), thông báo cho B về điều đó; B chiếm bên kia; sau đó, đồng xu lật… Không ai còn nghi ngờ gì nữa rằng người chơi ngửa là một cách công bằng để giải quyết lời giải các vấn đề gây tranh cãi.

Năm 1974, Martin Gardner, trong bài báo “Nghịch lý nảy sinh từ các mối quan hệ không phân biệt đối xử”, đã giới thiệu cho độc giả Scientific American một trò chơi “thuần khiết không kém” mà ông gọi là cặp miếng đệm hay nhất. Trò chơi này tương tự như trò chơi ngửa, chỉ có điều người chơi hình thành các từ không phải từ một chữ cái, như trong trò chơi ngửa, mà từ nhiều chữ cái. Martin, người chơi A nghĩ ra từ ORO và thông báo cho B về nó; Ngược lại, nó nghĩ ra một số từ có cùng độ dài, chẳng hạn như OOP. Tất nhiên, các từ được chọn không được giống nhau nên A báo cáo lựa chọn của mình cho B. Sau đó, người chơi bắt đầu tung đồng xu, ghi lại kết quả của mỗi lần tung. Martin, sau 6 lần tung các kết quả: sấp, ngửa, sấp, sấp, ngửa, sấp, trình tự POPPOP sẽ được ghi lại. Trò chơi dừng lại khi từ được A hoặc B chọn xuất hiện ở cuối chuỗi chữ cái đã ghi; trong trường hợp đầu tiên, chiến thắng thuộc về A, trong trường hợp thứ hai - thuộc về B. Như vậy, ai có từ xuất hiện đầu tiên sẽ thắng. Martin, nếu O xuất hiện trên đồng xu tiếp theo thì A sẽ thắng, vì POPPOP sẽ được viết (các từ được A chọn trong chuỗi được in nghiêng); Nếu P được tung ra ở lượt tiếp theo, trò chơi phải tiếp tục (vì POPPOP không chứa OPO và OOP); Hơn nữa, trong trường hợp O, O, P xuất hiện ở các ô thứ 8, 9 và 10 thì B sẽ thắng - sau cùng sẽ viết POPPOPOOR.

Nếu bạn đang chơi trò chơi mặt ngửa thì việc lựa chọn mặt ngửa hay mặt sấp là vấn đề sở thích, vì chữ O và P đều bằng nhau. Thoạt nhìn, có vẻ như trong “cuộc đặt cược tốt nhất cho những người đơn giản” tất cả các từ đều bình đẳng. Năm 1969, người tạo ra trò chơi này, Walter Penney, đã phát hiện ra sự bất bình đẳng của các từ. Hầu hết các nhà toán học sau khi đã học được luật chơi lúc đầu đều từ chối tin vào điều đó. Tuy nhiên, điều này là như vậy - đối với nhiều cặp từ, việc lựa chọn một trong số chúng (“mạnh nhất”) mang lại lợi thế cho trò chơi đưa ra lựa chọn này: người chơi này thắng nhiều hơn đối thủ của mình, trò chơi trở nên không công bằng. Hơn nữa, có một công thức cho phép bạn định lượng lợi thế này.

Gần như có một câu chuyện trinh thám gắn liền với công thức này. Gardner đã trích dẫn nó trong bài báo của mình, trích dẫn nhà toán học nổi tiếng người Anh John Conway, người đã báo cáo nó trong một bức thư (không có bằng chứng). Gardner thừa nhận rằng ông không biết làm thế nào để chứng minh điều đó và “cho rằng” nó đạt được nhờ sự trợ giúp của matini, giống như nhiều kết quả khác của Conway.

Các báo cáo của Conway về bài toán này vẫn chưa được công bố, nhưng vào cuối những năm 70 và đầu những năm 80, công thức của ông đã được một số nhà toán học chứng minh một cách độc lập theo nhiều cách khác nhau. Tuy nhiên, tất cả những tác phẩm này đều sử dụng một bộ máy toán học khá phía máy chủ và công thức xuất hiện trong đó giống như một trò lừa: sau khi chia một số biểu thức có ba chữ số cho những biểu thức khác. Hoá ra sinh vật đó

5

Có một bằng chứng cơ bản về công thức Convel, bản phác thảo của nó được đưa ra ở phần kết của bài viết này. Hơn nữa, hiện nay đã có một thuật toán đơn giản để tìm ra đáp số tốt nhất cho người chơi thứ hai, mặc dù thuật toán thay thế ban đầu (đối với các từ có ba chữ cái), được đề xuất trong bài báo của Gardner và thuộc sở hữu của đồng nghiệp V. Volk, không hề thua kém về độ mơ hồ và phức tạp của nó so với các sàng giả kim để lấy được hòn đá triết gia.

Nhưng chúng ta lạc đề. Vẫn chưa rõ tại sao các từ trong trò chơi của chúng tôi có thể không đồng đều.

Từ nào mạnh hơn?

Hãy xem xét một ví dụ cụ thể. Hãy tưởng tượng rằng trong một trò chơi có các từ có hai chữ cái, người chơi A đặt cược vào tổ hợp “sấp-đuôi” và B - đặt cược vào tổ hợp “sấp-đầu”. Khi đó A sẽ chỉ thắng nếu PP xuất hiện ở hai lần ném đầu tiên: nếu OP xuất hiện thì B thắng ngay, nếu PO hoặc OO xuất hiện thì B cũng thắng, mặc dù không phải ngay lập tức; cụ thể là, trong hai trường hợp cuối cùng, B sẽ thắng ngay khi P xuất hiện trong lần tung tiếp theo (và điều này sẽ xảy ra vào một ngày nào đó - với một lần tung sạch, đồng xu không phải lúc nào cũng rơi trúng mặt). Như vậy, trong 4 phiên điều trần có khả năng xảy ra như nhau (PP, OP, PO, OO), người chơi A sẽ thắng một (PP), tức là cơ hội y A thắng kém gấp 3 lần y B.

Về trò chơi có từ hai chữ, điều đáng chú ý là người chơi thông minh A sẽ không thắng được chữ PP (cũng như chữ OO). Anh ta sẽ chọn từ OP (hoặc PO), khi đó cơ hội thắng và thua của anh ta là như nhau, tất nhiên trừ khi B chọn một trong những từ “yếu” OO hoặc PP (kiểm tra!).

Hình 1.

Nhưng nếu chúng ta chuyển sang các từ có ba chữ cái, hình ảnh tiếp nhận sẽ thay đổi. Cụ thể: dù nhà thờ A chọn từ có ba chữ cái nào thì đối thủ B cũng có thể chọn một từ khác giúp mình có cơ hội chiến thắng cao hơn.

“Thế nào,” người đọc sẽ hỏi, “tại sao người chơi A không chọn từ “mạnh nhất” vì anh ta chọn trước? Nhưng vấn đề là không có từ nào mạnh nhất. Tình huống xuất hiện rõ ràng hình 1. Tất cả các từ gồm ba chữ cái được tạo thành từ các chữ cái O, P đều được viết trên đó và các mũi tên màu đỏ giữa hai từ cho biết từ nào trong hai từ này mạnh hơn (tức là mang lại cơ hội chiến thắng cao hơn).

Nhìn vào hình 1: có ít nhất một mũi tên xuất hiện ở mỗi từ; Điều này có nghĩa là đối với bất kỳ từ nào cũng có từ mạnh hơn, tức là không có từ nào mạnh nhất. Lưu ý chu kỳ của PPO, OPP, OOP và PPO. Chúng ta thấy: từ việc chữ X mạnh hơn Y, chữ Y mạnh hơn Z, hoàn toàn không suy ra rằng X sẽ mạnh hơn Z (một tình huống thường nảy sinh trong thể thao hiện đại). Các nhà toán học nói rằng thái độ trở nên mạnh mẽ hơn là không tích cực (do đó có tiêu đề bài báo của Gardner). Có sẵn hình 1, người chơi B, được hướng dẫn bởi các mũi tên, luôn có thể giành cho mình một từ mạnh hơn trong đáp số mà A lựa chọn. Và khi đó anh ta sẽ thắng thường xuyên hơn đối thủ của mình.

Nhưng thường xuyên hơn bao nhiêu? Và làm thế nào để hình 1 phản ánh đúng tình hình thực tế? Chúng ta phải trả lời những câu hỏi này.

Hãy đánh giá cơ hội chiến thắng

Hãy quay trở lại trò chơi hai chữ cái. Như trước đây, chúng ta sẽ giả sử rằng người chơi ngây thơ A đã chọn từ A=11, và đối thủ xảo quyệt B của anh ta đặt cược vào từ B=01 (thay vì các chữ cái O, P bây giờ chúng ta viết các số 0,1, còn người chơi và từ anh ta chọn được biểu thị bằng một chữ cái). Chuỗi tung đồng xu mà A thắng sẽ được gọi là chuỗi A (loạt B được định nghĩa tương tự). Ví dụ: 11 là dòng A và 01, 001, 0001, 101, 1001, 10001 là dòng B.

6

Bảng 1.

Rõ ràng, 11 là dãy A duy nhất (tức là A thắng khi và chỉ khi hai lần tung đồng xu đầu tiên cho kết quả là 1). Hơn nữa, điều không kém phần quan trọng là dãy B có dạng 0…1 hoặc 10…1 (thay cho một số nhiều điểm, bất kỳ số 0 nào cũng có thể trở thành).

Vì vậy, 11 là dòng A duy nhất. Hãy thử xác định xác suất*) thắng A, tức là phải hợp nhất, trong đó sau hai lần ném, chuỗi 11 xuất hiện.

Kết quả của một lần tung là có thể xảy ra hai kết quả (0 và 1) - xác suất của mỗi kết quả là 1/2. Kết quả của hai lần ném là có bốn kết quả có thể xảy ra, xác suất của mỗi kết quả là 1/4, do đó xác suất A thắng là 1/4 (tức là A sẽ thắng trong 1/4 tổng số lần hợp nhất):

$$P(A, B) = P(11) = 1/4$$

($P(A, B)$ biểu thị xác suất A thắng B và $P(11)$ biểu thị xác suất của loạt 11).

$n$ lần ném có thể dẫn đến kết quả $2^n$ (có thể xảy ra như nhau); do đó, xác suất của mỗi lần chạy độ dài $n$ là $1/2^n$. Để tính xác suất $P(B, A; n)$ thắng B trong $n$ bước trở xuống, cần phải tìm xác suất của mỗi chuỗi $B$ có độ dài $\leq n$ và tính tổng các xác suất này. chúng tôi nhận được

$$P(B, A; n) = P(01) + P(001) + \dots$$

$$\dots + P(0...01) + P(101) + P(1001) + \dots$$

• Chúng tôi sẽ không định nghĩa khái niệm xác suất ở đây - ở nước ta các từ “xác suất” và “tỷ lệ sáp nhập” là những từ đồng nghĩa. Chúng tôi giới thiệu đến độc giả muốn làm quen với khái niệm này cuốn sách: A. N. Kolmogorov, I. G. Zhurbenko, A. V. Prokorov, Giới thiệu về Lý thuyết Xác suất, M.: Nauka, 1978.

Bảng 2.

$$\dots + P(10...01) = \left( \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^n} \right) +$$

$$+ \left( \frac{1}{8} + \frac{1}{16} + \dots + \frac{1}{2^n} \right) = \frac{3}{4} - \frac{1}{2^{n-1}}.$$

Do đó, B thắng A ở $n$ bước trở xuống với xác suất ước tính đối với $n$ lớn là gần bằng 3/4; xác suất không ai thắng sau khi tung $n$ là $1/2^{n-1}$ (tức là, không có gì là nhỏ đối với $n$ lớn). Đi đến giới từ trong đẳng thức $P(B, A; n) = 3/4 - 1/2^{n-1}$ với $n \to \infty$, chúng ta có thể giả định rằng chúng ta sẽ có xác suất $P(B, A)$ thắng B từ A với “sự tiếp tục không giới hạn” của trò chơi:

$$P(B, A) = 3/4.$$

Xác suất thắng của các từ gồm hai chữ cái $A$ và $B$ tùy ý được thể hiện ở Bảng 1 (số tại giao điểm của hàng $B$ và cột $A$ cho biết xác suất B thắng A). Bảng này không khó để tạo.

Hãy đánh giá ưu điểm

Dựa vào Bảng 1, Bảng 2 được xây dựng, giúp B có lợi thế hơn $A$

$$d(B, A) = \frac{P(B, A)}{P(A, B)}.$$

Bảng 3 cho thấy lợi ích của tất cả các từ có ba chữ cái. Bằng cách sử dụng bảng này, chúng tôi đã xây dựng biểu đồ “không biên giới” được hiển thị trong hình 1.

Nhưng làm thế nào để tìm được những con số ở bảng 3? Thật không may, công thức (1) ít được sử dụng để tính toán với độ dài từ $l \geq 3$. Đã có ba chữ cái $A, B$ thì rất dễ tìm thấy $P(A, B)$ - rất khó bài toán, còn đối với những từ lớn $l$ thì điều đó là vô vọng. Nhưng ở đây “ma thuật” đã giúp chúng ta

7

Công thức Convel

Công thức của Convel cho phép chúng ta tìm $d(B, A)$ cho $B$ và $A$ tùy ý mà không cần tính toán bất kỳ xác suất nào. Để giải thích công thức này, chúng ta cần định nghĩa các từ đa thức Convel $K_{XY}(t)$ $X, Y$.

Trên hình 2, các từ $Y$ được viết dưới từ $X$ sáu lần, với mỗi từ mới $Y$ dịch sang phải một vị trí so với từ trước đó (đối với các từ có chữ cái $n$, các từ $Y$ sẽ được viết dưới $X, n$ lần).

Mỗi lần dịch của từ $Y$ sẽ được gán số 1 hoặc 0, tùy thuộc vào việc tất cả các chữ cái nằm dưới nhau ở vị trí chung $X$ và $Y$ có ​​trùng nhau hay không. Từ kết quả (có độ dài $n$) từ số 0 và số 1 được gọi là mối tương quan của $X$ và $Y$ và được ký hiệu là $\langle XY \rangle$. Vì vậy, ví dụ, đối với ca thứ 2 $Y$ vị trí chung là như nhau, do đó ở dòng thứ hai tại hình 2 một đơn vị được viết - chữ cái thứ hai của từ $\langle XY \rangle$.

Trong ví dụ của chúng tôi
$$\langle XY \rangle = 010011.$$

Nói chung, hãy để $\langle XY \rangle = e_1 \dots e_n$ (trong đó $e_i$ là số không hoặc số một). Khi đó đa thức Convel của từ $X, Y$ được định nghĩa như sau:
$$K_{XY}(t) = e_1 + e_2 t + \dots + e_n t^{n-1}.$$

Trong trường hợp của chúng tôi $K_{XY}(t) = t + t^4 + t^5$. Một định nghĩa rất lạ! Trong mọi trường hợp, hoàn toàn không rõ làm thế nào người ta có thể tiếp cận được anh ta. Nhưng nó hoạt động - Công thức của Convel dựa trên nó:

$$d(B, A) = \frac{K_{AA}(1/2) - K_{AB}(1/2)}{K_{BB}(1/2) - K_{BA}(1/2)}.$$

Người ta có thể hiểu Gardner khi ông cho rằng việc lựa chọn công thức bất thường này là do những cú đánh “thế giới khác”: à, ma thuật, và không có gì hơn thế!

Không chú trọng đến nguồn gốc của công thức (*), chúng tôi sẽ chỉ ra cách sử dụng nó. Đầu tiên chúng ta cần tìm các mối tương quan $\langle AA \rangle, \langle AB \rangle, \langle BB \rangle, \langle BA \rangle$. Sau đó viết bốn đa thức Convel từ chúng, thay thế $t = 1/2$ vào mỗi chúng và cuối cùng, thực hiện các hành động được chỉ ra ở bên phải