Ai sẽ đến Rio?

2

Ai sẽ đến Ryuo

G. M. Adelson-Velsky,
I. N. Bershtein,
M. L. Gerver

Bài toán, được thảo luận trong bài viết này, hoàn toàn không có đặc điểm cờ vua - hay thực sự là thể thao -. Ví dụ, nó có thể được hình thành như sau: từ $n$ cặp đá có trọng lượng không bằng nhau, hiển thị theo thứ tự giảm dần $k$ những viên nặng nhất, chỉ sử dụng cân hai mảnh không có quả cân, sử dụng số lượng cân tối thiểu. Nhưng đây là một công thức có ý nghĩa toán học hoàn hảo: tạo một chương trình cho máy tính, với số lượng so sánh tối thiểu, sẽ chọn số lớn nhất từ ​​$n$ các số không bằng nhau theo cặp $k$ và sắp xếp chúng theo thứ tự giảm dần *).

Mệnh đề về bất đẳng thức cặp số (hoặc đá) tự động đảm bảo đáp ứng điều kiện: nếu $a > b$ và $b > c$ thì $a > c$. Bạn không cần phải là một kỳ thủ Bolshisky giàu kinh nghiệm mới hiểu rằng thực tế không có điều gì giống như vậy trong thể thao và chẳng hạn, việc Fischer thua Petrosyan tại giải đấu giả vờ ở Curacao và chiến thắng của Spassky trong trận đấu quyết định của trận tranh chức vô địch thế giới với Petrosyan hoàn toàn không xác định trước kết quả của trận đấu Spassky-Fischer.

Tuy nhiên, chúng ta hãy lưu ý rằng hệ thống Olympic (người thua cuộc bị loại) dựa chính xác vào các giả định được hình thành ở đầu bài viết. Nhân tiện, sơ đồ Olympic “thông thường”, theo đó người thua trong trận chung kết ngay lập tức được tuyên bố là người đoạt giải nhì (và người chiến thắng trong cuộc gặp những người thua ở bán kết được tuyên bố thứ ba), chỉ là một phiên bản tồi tệ hơn của “Quy tắc VOMI”!

Bài toán, mà các tác giả nói đến, như đã đề cập, hoàn toàn mang bản chất của người Serbia. (Nhân tiện, chúng tôi đã cố gắng đạt được lời giải của nó, với tất cả “tính cơ bản” rõ ràng của nó, chỉ khá gần đây, tất nhiên, điều này được tạp chí của chúng tôi đặc biệt quan tâm). Tác giả thấy thú vị và vui vẻ hơn khi trình bày nó bằng ngôn ngữ “cờ vua”…

Chương 1. Quy tắc VOMI

Đã xong rồi! Các thành phố cờ vua Vasyuki cuối cùng đã được phép tham gia Olympic Thế giới ở Rue de Janey.

*) Bài viết chỉ đề cập đến trường hợp $k=3$ (trường hợp tổng quát được bàn ở bài toán số 3).

ro. Hóa ra, như thường lệ, vào giây phút cuối cùng, và bây giờ một vòng loại phải được tổ chức trong vài ngày nữa và ba người mạnh nhất phải được chọn từ 128 kỳ thủ nghiệp dư. Hai người trong số họ (nhà vô địch và người đoạt giải nhì) sẽ chơi cho đội của Vasya

4

người chiến thắng ở vị trí thứ ba, chỉ cần chi tiêu
$$127 + 6 + 6 = 139$$
các bữa tiệc.

Chương II. Nó có thể ngắn hơn được không?

Quy tắc VOMI có tốt không? Có thể xác định được người thắng thứ 1, thứ 2 và thứ 3 trong ít ván chơi hơn không?

§ 1. Ý kiến, cơ hội và số phận của ban lãnh đạo

Ngay cả trước khi hoàn thiện, hãy để ban quản lý Câu lạc bộ Tứ Mã đưa ra quan điểm rằng người chơi cờ mạnh nhất là A, người giỏi thứ hai là B, và người thứ ba là C. Và mục tiêu của sự hoàn hảo là để xác minh rằng điều này thực sự đúng.

Việc kiểm tra như vậy không thể được thực hiện trong ít hơn 127 ván đấu, vì tất cả người chơi cờ, ngoại trừ nhà vô địch, đều phải thua ít nhất một ván. Và trong 127 ván, có thể: 125 “người ngoài” (tất cả trừ A, B và C) chơi 124 ván “loại trực tiếp” (sau mỗi ván thua bị loại), sau đó người thắng đấu với C và thua *), C thua *) B và C sẽ thua *) A. Thực tế, thậm chí không cần thiết phải biết trực tiếp người thắng cuộc: họ có thể đoán ngẫu nhiên nên đôi khi (“nếu may mắn”) ba người chiến thắng được xác định bởi 127 trò chơi.

Tuy nhiên, chúng tôi sẽ cho rằng không có thông tin gì thêm về sức mạnh của các kỳ thủ và chúng tôi “không biết”. Hơn nữa, chúng ta hãy tưởng tượng rằng Evil Fate (hoặc đặc vụ của đối thủ - bất cứ điều gì bạn muốn) ảnh hưởng đến kết quả của mỗi trò chơi để trận đấu hoàn hảo tồn tại lâu nhất có thể. Chúng tôi sẽ chứng minh rằng trong trường hợp này không thể chọn ra người thắng thứ 1, thứ 2 và thứ 3 trong số 128 người chơi cờ trong ít hơn 139 ván đấu, bất kể **) việc thực hiện severnonia phù phiếm như thế nào.

*) Nếu anh ta thắng, điều đó có nghĩa là ban quản lý đã nhầm lẫn và không rõ phải làm gì tiếp theo.
**) Tất nhiên, theo đề xuất 1-5 của Chương I.

§ 2. Phát biểu định lý

Chúng ta hãy xem xét ngay trường hợp thực tế khi có 128 và bất kỳ số người chơi cờ nào ở các phần hoàn hảo. Hãy biểu thị nó bằng n. Chúng ta cũng xin giới thiệu ký hiệu sau đây. Cho N là một số tùy ý; đối với một số số nguyên l, bất đẳng thức $2^l \geq N$ đúng. Chúng ta hãy biểu thị bằng l [N] số nguyên nhỏ nhất trong số các số nguyên này.

Ví dụ.

1. Vì $2^3 < 10 < 2^4$ nên l [10] = 4.
2. Nếu $2^{k-1} < N \leq 2^k$ thì l [N] = k.
3. Chẳng bao lâu nữa chúng ta sẽ cần biết l[N] bằng bao nhiêu nếu N = 128·127. Vì $128 = 2^7$ và $2^6 < 127 < 2^7$, nên $2^{13} < 128·127 < 2^{14}$, do đó l [128 127] = 14.

Định lý. Để xác định người thắng 1-20, 2-20 và 3-20 trong số n người chơi cờ, bạn cần phải phô mai không ít hơn

$$P(n) = l[n(n-1)] + n-3$$
các bữa tiệc.

Theo anh ấy. Một cách khác để xây dựng định lý này như sau.

Cho phép kiểm tra tối đa các trò chơi R, trong đó

$$R < l[n(n-1)] + n-3.$$

Sau đó (bất kể quy tắc nào được thực hiện theo quy tắc severnonia), kết quả của trò chơi có thể đến mức sau R ván vẫn không thể xác định được người chiến thắng thứ 1, thứ 2 và thứ 3.

Nếu n = 128 thì l[n(n-1)] = l[128·127] = 14 (xem ví dụ 3). Điều này có nghĩa là P(128) = 14 + 128 - 3 = 139. Do đó, theo định lý đã xây dựng, để xác định người thắng thứ 1, thứ 2 và thứ 3 trong số 128 kỳ thủ thì cần không ít hơn 139 ván đấu. Trong 139 trò chơi, chúng có thể được xác định bằng quy tắc VOMI - vì vậy quy tắc VOMI là tốt!

§ 3. Tại phòng kế toán của Evil Rock

Trong § 1 của chương này, chúng tôi đã cảnh báo rằng Evil Rock đang cố gắng trì hoãn vòng loại Svernonia. Hiện nay

5

chúng tôi chỉ ra một chiến lược, theo đó, anh ta sẽ đảm bảo rằng các giải nhất, nhì và ba được xác định trong số ít nhất $n$ người chơi cờ vua

$$P(n) = l \left[ n(n-1) \right] + n-3$$

các bữa tiệc.

Về giới hạn 1. Chúng tôi sẽ gọi bất kỳ cặp người chơi cờ nào là $(A, B)^*$ biệt kích. Chúng tôi nhấn mạnh rằng các lệnh $(A, B)$ và $(B, A)$ là khác nhau; $A$ chơi theo đội $(A, B)$ ở bảng đầu tiên và theo đội $(B, A)$ ở bảng thứ hai.

Trước khi bắt đầu cuộc thi, tất cả các đội thi đấu tại địa điểm ở Olympida. Có bao nhiêu?

Trước giải đấu, mỗi kỳ thủ $n$ có cơ hội chơi ở bàn đầu tiên. Đồng thời, anh ta có thể dẫn dắt đội $n-1$ (bất kỳ người chơi cờ nào ngoại trừ anh ta đều có thể đứng thứ hai sau anh ta). Như vậy, số lượng tất cả người chỉ huy là $n$ ($n-1$).

Khi cuộc thi diễn ra, số đội tranh giành một suất ở Rio giảm dần (cho đến khi còn lại đúng một đội như vậy).

Giả sử một số trò chơi đã được chơi ở Turin. Dựa trên kết quả của họ, chúng tôi sẽ chia tất cả những người tham gia thành 3 nhóm. Nhóm đầu tiên bao gồm tất cả những người chưa thua một trận nào. Về thứ hai - những người thua đúng một ván và nhất thiết phải thua người chơi cờ của nhóm đầu tiên. Đến người thứ ba - tất cả những người còn lại (những người thua nhiều hơn một ván hoặc một ván - mỗi người chơi không thuộc nhóm đầu tiên).

Ở bên phải. Kiểm tra xem trong tình huống này, các đội sau đây đang tranh giành một suất ở Rio:

1. tất cả các đội $(A, B)$, trong đó $A$ thuộc nhóm đầu tiên và $B$ từ nhóm thứ hai, và trận duy nhất $B$ thua là thua $A$;

2. tất cả các đội $(C, D)$, cũng như $C$ và $D$, đều thuộc nhóm đầu tiên.

Kiểm tra để đảm bảo không có đội nào khác đang thi đấu tại địa điểm Olympida.

*) “Đội” gồm hai người, không phải ba người: cầu thủ dự bị không được đưa vào đội (điều này thuận tiện hơn cho việc trình bày).

(Chỉ định. Để $B$ thua $A$ thì $B$ sẽ không trở thành nhà vô địch và chỉ có thể trở thành người đoạt giải nhì với điều kiện $A$ trở thành nhà vô địch. Như vậy, $B$ sẽ không còn được dẫn dắt bất kỳ đội nào và chỉ trong một đội - trong $(A, B)$ - anh ta mới có thể tham gia với tư cách là người tham gia thứ hai.)

Định nghĩa 2. Nếu tại một thời điểm nào đó trong cuộc thi, kỳ thủ $A$ đã thắng $a$ ván và kỳ thủ cờ vua $B$ đã thắng $b$ ván thì chúng tôi sẽ nói rằng đội $(A, B)$ có $a+b$ điểm. Số $2^{a+b}$ được gọi là đặc điểm của đội $(A, B)$.

Sau mỗi trận đấu mới, tài sản của bất kỳ đội nào sẽ tăng thêm 1 (nếu người chiến thắng trong trò chơi là thành viên của đội này) hoặc không thay đổi. Đặc tính tương ứng của bất kỳ lệnh nào sẽ bị xóa hoặc không thay đổi.

Định nghĩa 3. Chơi một số lượng trò chơi nhất định. Thật thuận tiện để mô tả tình hình hiện tại bằng số $M$, bằng tổng các đặc điểm của tất cả các đội vẫn đang cạnh tranh địa điểm ở Olympida.

$M$ bằng bao nhiêu trong tình huống ban đầu (trước cuộc thi)? Chưa có ai thắng trận nào, mỗi đội 0 điểm, đặc điểm của đội nào cũng là $2^0=1$. Do đó, $M$ ban đầu chỉ đơn giản là tổng số lệnh, tức là $M_{\text{начальное}}=n$ ($n-1$).

Bổ đề. Giả sử trong một số tình huống, được đặc trưng bởi số $M$, một ván cờ được chơi giữa cờ $A$ và $B$. Chúng ta hãy biểu thị bằng $M_A$ con số đặc trưng cho tình huống sẽ phát sinh nếu $A$ thắng và bằng $M_B$ con số đặc trưng cho tình huống trong trường hợp $B$ thắng. Sau đó

$$M_A + M_B = 2M,$$

sao cho mặc dù một trong các số $M_A$ và $M_B$ không nhỏ hơn $M$.

Bằng chứng. Trước trận đấu giữa $A$ và $B$, tất cả các đội tranh giành địa điểm ở Olympida đương nhiên được chia thành 3 nhóm.

6

Nhóm I. Các lệnh trong đó $A$ được bao gồm nhưng $B$ không được bao gồm hoặc được bao gồm sau $A^*$).

Nhóm II. Các lệnh trong đó $B$ được bao gồm nhưng $A$ không được bao gồm hoặc được bao gồm sau $B$.

Nhóm III. Các đội không bao gồm $A$ hoặc $B$.

Hãy ký hiệu bằng $M_I$, $M_{II}$, $M_{III}$ tổng đặc điểm của lệnh nhóm I, II và III (vì vậy $M=M_I+M_{II}+M_{III}$).

Hãy để chúng tôi chứng minh rằng $M_A=2M_I+M_{III}$. Quả thực, sau chiến thắng $A$, chỉ có các đội thuộc Nhóm I và III mới đủ điều kiện giành chiến thắng ở Rio; Đồng thời, ở nhóm III, đặc điểm của các đội không thay đổi nhưng ở nhóm I thì đặc điểm của các đội lại tăng gấp đôi.

Tương tự, người ta chứng minh rằng

$$M_B = 2M_{II} + M_{III}.$$

Vì thế,

$$M_A + M_B = 2(M_I + M_{II} + M_{III}) = 2M.$$

Chiến lược của Evil Doom. Giải đấu vòng loại diễn ra như thế nào? Như chúng ta biết, tất cả các trò chơi đều được chơi tuần tự (lần lượt). Những người tham gia mỗi trò chơi mới được đặt tên tùy thuộc vào kết quả của tất cả các trò chơi trước đó.

Giả sử một số ván nhất định đã được chơi và ván tiếp theo được gọi là giữa cờ vua $A$ và $B$. Evil Doom đếm các đặc điểm $M$, $M_A$ và $M_B$ (xem bổ đề); sau đó nếu $M_A>M_B$, anh ta loại bỏ để $A$ thắng, và nếu $M_B>M_A$, thì $B$ thắng; nếu $M_A=M_B$, thì anh ta sẽ không hoảng hốt. Vì số lớn hơn $M_A$ và $M_B$ được hoàn thành ít nhất $M$ (theo bổ đề), nên với chiến lược này, đặc tính $M$ không giảm sau mỗi trò chơi.

Nhấn mạnh Rock toàn năng là đủ rồi, không cần phải thế đâu.

*) B được đưa vào sau $A$ chỉ trong một đội ($A, B$); đội này được xếp vào Nhóm I và chỉ được đặt với điều kiện là vẫn tuyên bố sẽ giành chiến thắng ở Rio.

Toàn tri: không đi sâu vào kế hoạch tổ chức giải đấu, anh ấy áp dụng chiến lược tương tự cho bất kỳ lịch thi đấu nào.

Tiếp theo, chúng tôi sẽ chỉ ra rằng với chiến lược này, việc xác định người chiến thắng thứ 1, thứ 2 và thứ 3 sẽ cần ít nhất

$$P(n) = l[n(n-1)] + n-3$$

các bữa tiệc.

§ 4. Chứng minh định lý

Thực hiện corvevohany $M_{начальное} = n(n-1)$. Giá trị của $M$ là bao nhiêu khi quá trình kiểm tra hoàn thành và xác định được vị trí á quân 1, 2 và 3 $X$, $Y$ và $Z$? Một đội ($XY$) đã được chọn để lên tàu tới Thế vận hội. Hãy để chúng tôi biểu thị bằng $v$ số điểm trong nội dung của đội này. Sau đó $M_{конецное} = 2^v$.

Nếu Evil Doom làm theo chiến lược được mô tả ở trên thì sau mỗi trận đấu, chỉ số $M$ không giảm nên $M_{конецное}$ không nhỏ hơn $M_{начальное}$. Do đó $2^v \geq n(n-1)$, tức là $v \geq l[n(n-1)]$. Như vậy, hai người chiến thắng đầu tiên $X$ và $Y$ đã tham gia không dưới $l[n(n-1)]$ trò chơi.

Ngoài ra, ít nhất $(n-3)$ trò chơi đã được chơi mà không có sự tham gia của họ. Thật vậy, mỗi kỳ thủ trong số $(n-3)$ cờ vua không có tên trong top ba được công nhận đã phải thua một người khác không phải $X$ và $Y$ - nếu không thì anh ta sẽ giành được vị trí thứ ba.

Như vậy tổng cộng không ít hơn

$$P(n) = l[n(n-1)] + n-3$$

các bữa tiệc. Định lý đã được chứng minh.

Chương III. Làm thế nào để xác định ba người chiến thắng trong $n$ cờ vua?

Chương I đã trình bày quy tắc xác định ba người chiến thắng trong 128 ván cờ. Hãy để chúng tôi trình bày các quy tắc tương tự cho trường hợp cờ vua $n$. Đặt $l[n]=k$, tức là

$$2^{k-1} < n \leq 2^k.$$

7

§ 1. Định nghĩa nhà vô địch

Trò chơi được chơi theo hệ thống Optimian. Ở giai đoạn đầu tiên, tất cả những người tham gia được chia thành hai nhóm: theo một cặp $2^k$; ở cặp khác, người chiến thắng được xác định và được nhận vào chặng 2; các thành viên của nhóm đầu tiên bắt đầu cuộc chiến ngay từ màn thứ 2. Tổng số được nhận vào giai đoạn 2

$$\left(n - 2^{k-1}\right) + \left(2^k - n\right) = 2^{k-1}$$

người tham gia. Tất cả các chặng, bắt đầu từ chặng thứ 2, “tiêu chuẩn”*): những người tham gia chặng được chia thành từng cặp, trong mỗi cặp sẽ xác định được người chiến thắng, ai được nhận vào chặng tiếp theo. Nhà vô địch được xác định trong trò chơi tài chính ở giai đoạn thứ $k$. Vì mỗi người trong số $n$ người tham gia, ngoại trừ nhà vô địch, thua một trò chơi theo cách có hệ thống như vậy, nên tổng cộng $(n-1)$ trò chơi sẽ được chơi ở giai đoạn $k$.

§ 2. Xác định người đoạt giải Nhì

Những người chơi cờ chỉ thua nhà vô địch đang tranh giành vị trí này. Không có nhiều hơn $k$; Hãy gán cho họ những con số 1, …, $k$ ($N_2$ tôi là người đã thua nhà vô địch ở chặng $i$-th**).

Chúng tôi chơi các trò chơi như thế này: $N_2$ 1 chơi với $N_2$ 2***), sau đó người chiến thắng chơi với $N_2$ 3, v.v. (tổng cộng không quá $k-1$ trò chơi). Người chiến thắng ở ván cuối cùng là người về nhì.

*) Giai đoạn 1, trái ngược với trường hợp được thảo luận trong quy tắc VOMI, là “không chuẩn” (nghĩa là nó yêu cầu phân chia bổ sung những người tham gia thành các nhóm được nêu trong đoạn này), nếu $n$ không phải là lũy thừa chính xác của hai.

**) Lưu ý rằng có thể không đạt được $N_2$ 1 (nếu nhà vô địch bắt đầu trò chơi từ màn 2).

***) Không có giai đoạn nào khác (xem phương pháp trước) và mọi thứ bắt đầu bằng trò chơi giữa $N_2$ 2 và $N_2$ 3.

§ 3. Xác định người đoạt giải ba

Có thể dễ dàng kiểm tra (xem § 3 của Chương I) rằng người đoạt giải nhì đã thắng không quá $k$ trò chơi và do đó không quá $k$ mọi người đang tranh giành vị trí thứ ba. Người mạnh nhất trong số họ cuối cùng đã được xác định cho trò chơi $k-1$. Đây là người đoạt giải ba.

§ 4. Kết luận

Để tìm ra người đoạt giải 1, 2 và 3 trong số $n$ người chơi cờ vua, chỉ cần kiểm tra

$$\left(n-1\right) + \left(k-1\right) + \left(k-1\right) = 2k + n-3 = 2l \left[n\right] + n-3$$

các bữa tiệc. Chúng ta sẽ biểu thị con số này bằng $Q(n)$.

Chương IV. Thảo luận về kết quả

Đặt $n$ là một số nguyên, $n \geqslant 3$. Ta biểu thị bằng $I(n)$ một số thỏa mãn hai điều kiện sau:

1. đối với $I(n)$ trò chơi, chắc chắn có thể xác định được người thắng thứ 1, thứ 2 và thứ 3 trong số $n$ người chơi cờ vua.

2. nếu $R < I(n)$, thì kết quả của ván đấu có thể đến mức trong ván $R$ không thể xác định được người thắng thứ 1, thứ 2 và thứ 3 trong số $n$ người chơi cờ vua.

Khi đó kết quả thu được ở chương II và chương III có thể viết dưới dạng công thức

$$P(n) \leqslant I(n) \leqslant Q(n).$$

Chúng ta hãy nhớ lại điều đó

$$P(n) = l \left[n(n-1)\right] + n-3,$$

$$Q(n) = 2l \left[n\right] + n-3,$$

ở đâu $l \left[n\right] = k$ tại $2^k \geqslant n > 2^{k-1}$.

Có thể chứng minh rằng $Q(n)$ bằng $P(n)$ hoặc $P(n)+1$. Trong trường hợp đầu tiên $I(n)=P(n)=Q(n)$. Trong trường hợp thứ hai, có hai khả năng cho $I(n)$: $I(n)=P(n)$ hoặc $I(n)=Q(n)$. Cả hai khả năng