IMO Shortlist 2024: Combinatorics

Trong bài này tôi sẽ giới thiệu các bài toán tổ hợp trong cuốn IMO Shortlist 2024, các bài toán từ IMO SL năm trước các bạn có thể tìm ở https://nttuan.org/category/contests/imo-shortlist/ .

Các phần khác của bộ 2024 tôi đã đăng ở đây

A. https://nttuan.org/2025/09/03/isl2024a/

G. https://nttuan.org/2025/08/07/isl2024g/

N. https://nttuan.org/2025/11/14/isl2024n/

C1. https://artofproblemsolving.com/community/c6h3610442p35340913

Cho $n$ là một số nguyên dương. Một lớp gồm $n$ học sinh chạy $n$ cuộc đua, trong mỗi cuộc đua họ được xếp hạng mà không có hòa. Một học sinh đủ điều kiện để nhận điểm đánh giá $(a, b)$ với $a$ và $b$ là các số nguyên dương, nếu họ về đích trong $b$ vị trí dẫn đầu ở ít nhất $a$ cuộc đua. Điểm số cuối cùng của họ là giá trị lớn nhất có thể của $a-b$ trên tất cả các điểm đánh giá mà họ đủ điều kiện. Tìm tổng lớn nhất có thể của tất cả các điểm số của $n$ học sinh.

C2. https://artofproblemsolving.com/community/c6h3610436p35340903

Cho $n$ là một số nguyên dương. Các số nguyên $1, 2, 3, \ldots, n^2$ được điền vào các ô của bảng $n \times n$ sao cho mỗi số nguyên được điền vào đúng một ô và mỗi ô chứa đúng một số nguyên. Với mỗi số nguyên $d$ sao cho $d\mid n$ , phép $d$ -chia của bảng là phép chia bảng thành $(n/d)^2$ bảng con không chồng nhau, mỗi bảng con có kích thước $d \times d$ , sao cho mỗi ô được chứa trong đúng một bảng con $d \times d$ . Ta nói rằng $n$ là một số đẹp nếu các số nguyên có thể được điền vào bảng $n \times n$ sao cho, với mỗi số nguyên $d$ với $d\mid n$ và $1 < d < n$ , trong phép $d$ -chia của bảng, tổng các số nguyên được điền trong mỗi bảng con $d \times d$ không chia hết cho $d$ . Hãy xác định tất cả các số đẹp chẵn.

C3. https://artofproblemsolving.com/community/c6h3610441p35340911

Cho $n$ là một số nguyên dương. Có $2n$ hiệp sĩ ngồi quanh một bàn tròn. Họ gồm $n$ cặp đối tác, mỗi cặp muốn bắt tay nhau. Một cặp chỉ có thể bắt tay khi họ ngồi cạnh nhau. Mỗi phút, một cặp hiệp sĩ ngồi cạnh nhau đổi chỗ. Tìm số lần đổi chỗ nhỏ nhất giữa các hiệp sĩ ngồi cạnh nhau sao cho, bất kể cách sắp xếp ban đầu thế nào, mỗi hiệp sĩ đều có thể gặp đối tác của mình và bắt tay tại một thời điểm nào đó.

C4. https://artofproblemsolving.com/community/c6h3359777p31218774

Trên một bảng có $2024$ hàng và $2023$ cột, Ốc sên Turbo cố gắng di chuyển từ hàng đầu tiên đến hàng cuối cùng. Trong mỗi lần thử, nó chọn bắt đầu ở bất kỳ ô nào trong hàng đầu tiên, sau đó di chuyển từng bước đến một ô liền kề chung cạnh. Nó thắng nếu đạt đến bất kỳ ô nào trong hàng cuối cùng. Tuy nhiên, có $2022$ quái vật đã được xác định trước và giấu kín trong $2022$ ô, mỗi hàng có một con trừ hàng đầu tiên và hàng cuối cùng, sao cho không có hai quái vật nào nằm cùng một cột. Nếu không may Turbo đến ô có quái vật, lần thử của nó kết thúc và nó được đưa trở lại hàng đầu tiên để bắt đầu một lần thử mới. Các quái vật không di chuyển. Giả sử Turbo được phép thực hiện $n$ lần thử. Xác định giá trị nhỏ nhất của $n$ sao cho nó có một chiến lược đảm bảo đến được hàng cuối cùng, bất kể vị trí của các quái vật thế nào. (IMO2024/5)

C5. https://artofproblemsolving.com/community/c6h3610469p35340978

Cho $N$ là một số nguyên dương. Geoff và Ceri chơi một trò chơi mà họ bắt đầu bằng cách viết các số $1, 2, \ldots, N$ lên bảng. Sau đó họ luân phiên thực hiện một nước đi, bắt đầu từ Geoff. Mỗi nước đi bao gồm việc chọn một cặp số nguyên $(k, n)$ , trong đó $k \ge 0$ và $n$ là một trong các số nguyên trên bảng, sau đó xóa mọi số nguyên $s$ trên bảng sao cho $2^k \mid n-s$ . Trò chơi tiếp tục cho đến khi bảng trống. Người chơi xóa số nguyên cuối cùng trên bảng sẽ thua. Xác định tất cả các giá trị của $N$ mà Geoff có thể đảm bảo thắng, bất kể Ceri chơi như thế nào.

C6. https://artofproblemsolving.com/community/c6h3610456p35340931

Cho $n$ và $T$ là các số nguyên dương. James có $4n$ viên bi với khối lượng $1, 2, \ldots, 4n$ . Anh ấy đặt chúng lên một chiếc cân thăng bằng sao cho hai bên có khối lượng bằng nhau. Andrew có thể di chuyển một viên bi từ bên này sang bên kia của chiếc cân, sao cho độ chênh lệch về khối lượng của hai bên luôn không quá $T$ . Tìm, theo $n$ , số nguyên dương $T$ nhỏ nhất sao cho Andrew có thể thực hiện một chuỗi các nước đi để mỗi viên bi cuối cùng nằm ở phía đối diện của chiếc cân, bất kể cách James đặt bi ban đầu như thế nào.

C7. https://artofproblemsolving.com/community/c6h3358930p31206050

Cho dãy vô hạn các số nguyên dương $(a_n){n\geq 1}$ và số nguyên dương $N$ . Giả sử với mọi số nguyên $n>N$ , $a_n$ bằng số lần xuất hiện của $a{n-1}$ trong dãy số $a_1$ , $a_2$ , $\ldots$ , $a_{n-1}$ . Chứng minh rằng một trong hai dãy số $(a_{2n-1}){n\geq 1}$ và $(a{2n})_{n\geq 1}$ là tuần hoàn kể từ lúc nào đó. (IMO2024/3)

C8. https://artofproblemsolving.com/community/c6h3610448p35340921

Cho $n$ là một số nguyên dương. Cho một bảng $n \times n$ , ô đơn vị ở góc trên bên trái ban đầu được tô màu đen, và các ô khác được tô màu trắng. Sau đó, ta áp dụng một chuỗi các thao tác tô màu lên bảng. Trong mỗi thao tác, ta chọn một hình vuông $2 \times 2$ có đúng một ô màu đen và ta tô ba ô còn lại của hình vuông $2 \times 2$ đó thành màu đen. Xác định tất cả các giá trị của $n$ sao cho ta có thể tô toàn bộ bảng thành màu đen.

Formal power series

Định nghĩa 1. Một chuỗi lũy thừa hình thức là một biểu diễn có dạng

$a_0+a_1x+a_2x^2+a_3x^3+\ldots,$

hay gọn hơn $\displaystyle\sum_{k=0}^{\infty}a_kx^k.$ Trong đó $(a_n)_{n\geq 0}$ là một dãy các số phức. Các $a_i$ được gọi là các hệ số của chuỗi lũy thừa hình thức, $a_0$ được gọi là hệ số tự do của chuỗi lũy thừa hình thức.

Từ “hình thức” trong định nghĩa trên có nghĩa là ta không bận tâm đến việc cho $x$ các giá trị đặc biệt, ta cũng không quan tâm đến tính hội tụ hay phân kỳ của chuỗi. Tập tất cả các chuỗi lũy thừa hình thức với hệ số thuộc một tập hợp $A$ được ký hiệu bởi $A[[x]]$ . Với một chuỗi lũy thừa hình thức $a(x)$ , ta ký hiệu hệ số của $x^n$ trong chuỗi này bởi $[x^n]a(x)$ .

Nếu $a_i=0$ với mọi $i>m$ thì để cho gọn, chuỗi $\sum_{n=0}^{\infty}a_nx^n$ sẽ được viết là

$a_0+a_1x+\ldots+a_mx^m.$

Chuỗi lũy thừa hình thức với tất cả các hệ số bằng $0$ được gọi là chuỗi không, ký hiệu là $0$ . Tổng và tích của hai chuỗi lũy thừa hình thức $\displaystyle\sum_{n=0}^{\infty}a_nx^n$ và $\displaystyle\sum_{n=0}^{\infty}b_nx^n$ được định nghĩa bởi

$\displaystyle\sum_{n=0}^{\infty}a_nx^n+\sum_{n=0}^{\infty}b_nx^n=\sum_{n=0}^{\infty}(a_n+b_n)x^n$

và

$\displaystyle\left(\sum_{n=0}^{\infty}a_nx^n\right)\left(\sum_{n=0}^{\infty}b_nx^n\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n.$

Với hai phép toán này thì $\mathbb{C}[[x]]$ là một vành giao hoán có đơn vị là chuỗi đơn vị $1+0x^1+0x^2+0x^3+\ldots,$ ký hiệu là $1$ .

Tương tự như với các số phức, ta có kết quả sau:

Định lý 1. Nếu $a$ và $b$ là các phần tử khác không của $\mathbb{C}[[x]]$ , thì chuỗi tích $ab$ cũng khác chuỗi không.

Chứng minh. Gọi $m$ là số tự nhiên nhỏ nhất sao cho $[x^m]a\not=0$ , và $n$ là số tự nhiên nhỏ nhất sao cho $[x^n]b\not=0$ . Khi đó

$[x^{m+n}](ab)=([x^m]a)([x^n]b)\not=0,$

suy ra $ab$ khác chuỗi không. $\Box$

Khác với phép nhân trong tập các số phức, không phải mọi chuỗi khác không đều có nghịch đảo. Chẳng hạn, khi $a(x)=0+x+0x^2+0x^3+\ldots,$ (chuỗi này thường được viết là $a(x)=x$ ) thì $a(x)\not=0$ nhưng không có chuỗi $b(x)$ để $a(x)b(x)=1$ .

Định lý 2. Chuỗi $a(x)$ có nghịch đảo khi và chỉ khi $[x^0]a(x)\not=0$ .

Chứng minh. Giả sử chuỗi $a(x)$ có nghịch đảo, và $b(x)$ là nghịch đảo của nó. Khi đó

$1=[x^0](ab)=([x^0]a)([x^0]b),$

suy ra $[x^0]a(x)\not=0$ .

Bây giờ giả sử $\displaystyle a(x)=\sum_{n=0}^{\infty}a_nx^n$ là một chuỗi lũy thừa hình thức có $a_0=[x^0]a(x)\not=0$ . Chuỗi lũy thừa hình thức $\displaystyle b(x)=\sum_{n=0}^{\infty}b_nx^n$ là nghịch đảo của $a(x)$ khi và chỉ khi $a_0b_0=1$ và

$\displaystyle\sum _{k=0}^na_kb_{n-k}=0,\quad\forall n\geq 1.$

Từ hệ này ta có thể xác định $b(x)$ bởi $b_0=1/a_0$ và

$\displaystyle b_n=-\frac{1}{a_0}\sum _{k=1}^na_kb_{n-k},\quad\forall n\geq 1.$ $\Box$

Khi $a$ là một chuỗi có nghịch đảo thì ta ký hiệu chuỗi nghịch đảo của nó bởi $a^{-1}$ . Tích của chuỗi $b$ và chuỗi $a^{-1}$ thường được viết là $\frac{b}{a}$ .

Ví dụ. Chuỗi lũy thừa hình thức $1-x$ có nghịch đảo là chuỗi

$\displaystyle \frac{1}{1-x}=1+x+x^2+x^3+\ldots$

Định nghĩa 2. Dãy các chuỗi lũy thừa hình thức với hệ số phức $\{S_n(x)\}_{n\geq 1}$ được gọi là hội tụ đến chuỗi lũy thừa hình thức với hệ số phức $S(x)$ , ký hiệu $\displaystyle\lim_{n\to\infty} S_n(x)=S(x)$ , nếu với mỗi $n\geq 0$ có số nguyên dương $N$ sao cho $[x^n]S_i(x)=[x^n]S(x)$ mỗi khi $i\geq N$ . Trong trường hợp này ta nói $\{S_n(x)\}_{n\geq 1}$ là một dãy hội tụ.

Khi $\displaystyle A(x)=\sum_{n\geq 0}a_nx^n$ là một phần tử khác không của $\mathbb{C}[[x]]$ , ta gọi bậc của $A(x)$ , ký hiệu $\deg A(x)$ , là số $n$ nhỏ nhất sao cho $a_n\not=0$ . Dễ thấy nếu $B(x)$ và $C(x)$ là các phần tử khác không của $\mathbb{C}[[x]]$ thì $B(x)C(x)$ cũng là một phần tử khác không của $\mathbb{C}[[x]]$ , và

$\deg B(x)C(x)=\deg B(x)+\deg C(x).$

Ta quy ước $\deg 0=\infty$ . Sử dụng bậc của một chuỗi lũy thừa hình thức ta có một định nghĩa khác của tính hội tụ của dãy các chuỗi lũy thừa hình thức.

Continue reading →

IMO Shortlist 2023: Combinatorics

Hình học : https://nttuan.org/2024/11/02/isl2023-geometry/

Đại số: https://nttuan.org/2025/01/23/isl2023-algebra/

Số học: https://nttuan.org/2025/02/13/isl2023-number-theory/

C1. https://artofproblemsolving.com/community/c6h3359749p31218491

Cho $m$ và $n$ là các số nguyên lớn hơn $1$ . Trong mỗi ô vuông đơn vị của lưới $m\times n$ có một đồng xu với mặt trái hướng lên trên. Một phép toán bao gồm các bước sau.

chọn một hình vuông $2\times 2$ trong lưới;
lật các đồng xu ở ô đơn vị trên cùng bên trái và dưới cùng bên phải;
lật đồng xu ở ô vuông đơn vị trên cùng bên phải hoặc dưới cùng bên trái.

Xác định tất cả các cặp $(m,n)$ sao cho mọi đồng xu đều hiện mặt phải sau một số hữu hạn lần thực hiện phép toán.

C2. https://artofproblemsolving.com/community/c6h3359755p31218537

Xác định số nguyên dương $L$ lớn nhất sao cho tồn tại một dãy các số nguyên dương $a_1,\dots,a_L$ có tính chất: mỗi số hạng của dãy không lớn hơn $2^{2023}$ , và không có các số hạng liên tiếp $a_i,a_{i+1},\dots,a_j$ (ở đây $1\le i\le j\le L$ ) với một cách chọn dấu $s_i,s_{i+1},\dots,s_j\in\{1,-1\}$ để

$s_ia_i+s_{i+1}a_{i+1}+\dots+s_ja_j=0.$

C3. https://artofproblemsolving.com/community/c6h3107350p28104367

Cho $n$ là một số nguyên dương. Một tam giác Nhật Bản gồm $1+2+\cdots+n$ hình tròn được xếp thành một hình tam giác đều sao cho với mỗi $i = 1, 2, ..., n$ , hàng thứ $i$ có đúng $i$ hình tròn và trên hàng đó có đúng một hình tròn được tô màu đỏ. Một đường đi ninja trong một tam giác Nhật Bản là một dãy gồm $n$ hình tròn nhận được bằng cách xuất phát từ hàng trên cùng, đi lần lượt từ một hình tròn xuống một trong hai hình tròn ngay dưới nó, và kết thúc tại hàng dưới cùng. Trong hình vẽ là một tam giác Nhật Bản với $n = 6$ và một đường đi ninja có chứa hai hình tròn màu đỏ.

Như một hàm số của $n$ , tìm giá trị lớn nhất của $k$ sao cho trong mỗi tam giác Nhật Bản luôn có một đường đi ninja chứa ít nhất $k$ hình tròn màu đỏ. (IMO2023/5)

C4. https://artofproblemsolving.com/community/c6h3359724p31218375

Cho $n\geqslant 2$ là một số nguyên dương. Paul có một dải hình chữ nhật cỡ $1\times n^2$ gồm $n^2$ hình vuông đơn vị, trong đó hình vuông thứ $i$ được gắn nhãn $i$ với mọi $1\leqslant i\leqslant n^2$ . Anh ta muốn cắt dải giấy thành nhiều mảnh, trong đó mỗi mảnh bao gồm một số ô vuông đơn vị liên tiếp, sau đó dịch chuyển (không xoay hoặc lật) các mảnh để thu được hình vuông $n\times n$ thỏa mãn tính chất sau: nếu hình vuông đơn vị trong hàng $i$ và cột $j$ được gắn nhãn $a_{ij}$ , thì $a_{ij}-(i+j -1)$ chia hết cho $n$ .

Xác định số mảnh nhỏ nhất mà Paul cần tạo để hoàn thành việc này.

C5. https://artofproblemsolving.com/community/c6h3359765p31218619

Elisa có $latex $2023$ rương kho báu, tất cả đều được mở khóa và trống rỗng lúc đầu. Mỗi ngày, Elisa thêm một viên đá quý mới vào một trong những chiếc rương đã mở khóa mà cô ấy chọn, và sau đó, một cô tiên sẽ hành động theo các quy tắc sau:

nếu có nhiều hơn một rương được mở khóa, cô sẽ khóa một trong số chúng, hoặc
nếu chỉ có một rương được mở khóa, cô sẽ mở khóa tất cả các rương.

Cho rằng quá trình này diễn ra mãi mãi, hãy chứng minh rằng tồn tại một hằng số $C$ với tính chất sau: Elisa có thể đảm bảo rằng chênh lệch giữa số viên ngọc trong hai rương bất kỳ không bao giờ vượt quá $latex $C$, bất kể cô tiên hành động như thế nào.

C6. https://artofproblemsolving.com/community/c6h3359747p31218478

Cho $N$ là một số nguyên dương và xét một lưới $N \times N$ các ô vuông. Đường dẫn xuống bên phải là một dãy các ô lưới sao cho mỗi ô là một ô ở bên phải hoặc một ô bên dưới ô trước đó trong chuỗi. Đường dẫn lên bên phải là một chuỗi các ô lưới sao cho mỗi ô là một ô ở bên phải hoặc một ô phía trên ô trước đó trong chuỗi.

Chứng minh rằng không thể phân chia các ô của lưới $N \times N$ thành ít hơn $N$ vùng sao cho mỗi vùng là một đường dẫn xuống bên phải xuống hoặc một đường dẫn lên bên phải.

Chẳng hạn, lưới $5 \times 5$ có thể phân chia thành $5$ vùng như hình vẽ.

C7. https://artofproblemsolving.com/community/c6h3359751p31218524

Quần đảo Imomi bao gồm $n\geq 2$ hòn đảo. Giữa mỗi cặp đảo khác nhau có một tuyến phà duy nhất chạy theo cả hai hướng và mỗi tuyến phà được điều hành bởi một trong $k$ công ty. Được biết, nếu bất kỳ công ty nào đóng cửa tất cả các tuyến phà của mình thì một du khách, bất kể bắt đầu từ đâu, sẽ không thể ghé thăm tất cả các hòn đảo đúng một lần (đặc biệt là không quay lại hòn đảo mà du khách bắt đầu). Xác định giá trị lớn nhất có thể có của $k$ theo $n$ .

Ramsey numbers

Các bạn đọc lại các bài sau để theo dõi cho dễ:

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

[3] https://nttuan.org/2023/09/01/graph02/

—

Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.

Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau.

Lời giải. Gọi $A$ là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, $A$ sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là $B$ , $C$ , $D$ , mà $A$ cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng $A$ quen cả ba người $B$ , $C$ , và $D$ . Nếu trong $B$ , $C$ , và $D$ có hai người quen nhau, chẳng hạn là $B$ và $C$ thì ba người $A$ , $B$ , và $C$ đôi một quen nhau. Nếu không, $B$ , $C$ , và $D$ đôi một không quen nhau. $\Box$

Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.

Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ $K_6$ trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của $K_6$ bởi hai màu, luôn có $K_3$ mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay $K_6$ bởi $K_n$ với $n<6$ . Kết quả sẽ thay đổi thế nào nếu thay $K_3$ bởi $K_{\alpha}$ ? Ta xét bài toán tổng quát sau:

Bài toán. Cho một số nguyên dương $\alpha$ . Tồn tại hay không số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu, luôn có $K_{\alpha}$ mà các cạnh mang cùng một màu. Số nguyên dương $n$ nhỏ nhất có tính chất này bằng bao nhiêu?

Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được $n$ như một hàm của $\alpha$ trong tình huống tổng quát mà chỉ có thể ước lượng nó.

Định lý 1 (Ramsey). Cho $s$ và $t$ là hai số nguyên lớn hơn $1$ . Khi đó tồn tại số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, $K_n$ có đồ thị con $K_s$ với các cạnh xanh hoặc có đồ thị con $K_t$ với các cạnh đỏ. Nếu ký hiệu $R(s,t)$ là số nguyên dương $n$ nhỏ nhất có tính chất này thì

$R(s,t)\leq R(s,t-1)+R(s-1,t)$

mỗi khi $s$ và $t$ lớn hơn $2$ .

Các số $R(s,t)$ được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết $R(3,3)=6$ . Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số $R(k,k)$ , chúng được gọi là các số Ramsey đối xứng.

Chứng minh. Ta chứng minh bằng quy nạp theo $s$ và $t$ . Lập luận đơn giản ta thu được $R(k,2)$ , $R(2,k)$ đều tồn tại và bằng $k$ với mọi $k>1$ .

Bây giờ giả sử $R(s,t-1)$ và $R(s-1,t)$ đều tồn tại, ở đây $s$ và $t$ là các số nguyên lớn hơn $2$ . Đặt $\alpha=R(s,t-1)+R(s-1,t)$ . Xét một cách tô màu các cạnh của $K_{\alpha}$ bởi một trong hai màu xanh và đỏ. Gọi $v$ là một đỉnh của $K_{\alpha}$ . Mỗi một trong $\alpha-1$ đỉnh còn lại của $K_{\alpha}$ được nối với $v$ bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có $R(s-1,t)$ đỉnh được nối với $v$ bởi cạnh xanh, hoặc có $R(s,t-1)$ đỉnh được nối với $v$ bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem $R(s-1,t)$ đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có $K_{s-1}$ với các cạnh xanh hoặc $K_t$ với các cạnh đỏ. Nếu có $K_t$ với các cạnh đỏ thì ta có điều phải chứng minh, nếu có $K_{s-1}$ với các cạnh xanh thì thêm $v$ vào ta có đồ thị con $K_s$ của $K_{\alpha}$ với các cạnh xanh, và ta cũng có điều cần chứng minh. $\Box$

Định lý 2. Với mỗi số nguyên $k>3$ , ta có $R(k,k)>2^{k/2}$ .

Chứng minh (của Paul Erdos). Xét một số nguyên $n$ thỏa mãn $k\leq n\leq 2^{k/2}$ . Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, sao cho trong $K_n$ không có $K_k$ với các cạnh cùng màu.

Tô màu mỗi cạnh của $K_n$ bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu $\Omega$ là tập tất cả các cách tô màu, và với mỗi biến cố $A$ , xác suất xảy ra $A$ bằng $\mid A\mid /\mid\Omega\mid$ .

Gọi $X$ là biến cố: trong $K_n$ không có $K_k$ với các cạnh cùng màu. Ta cần chứng $\mathbb{P}(X)>0$ . Với mỗi đồ thị con đầy đủ trên $k$ đỉnh của $K_n$ , gọi $Y_{\alpha}$ là biến cố: $\alpha$ có các cạnh cùng màu. Khi đó

$\displaystyle\mathbb{P}(Y_{\alpha})=\frac{\mid Y_{\alpha}\mid }{\mid \Omega\mid}=\frac{2\cdot 2^{C_n^2-C_k^2}}{2^{C_n^2}}=2^{1-C_k^2},$

do đó

$\mathbb{P}(X)=1-\mathbb{P}(\overline{X}) =1-\mathbb{P}\left(\bigcup_{\alpha}Y_{\alpha}\right)\geq 1-\sum_{\alpha}\mathbb{P}(Y_{\alpha})=1-C_n^k2^{1-C_k^2}.$

Mà ta lại có

$\displaystyle C_n^k2^{1-C_k^2}<\frac{n^k}{k!}\cdot 2^{1-C_k^2}\leq \frac{2^{k^2/2}}{k!}\cdot 2^{1-C_k^2}=\frac{2^{1+\frac{k}{2}}}{k!}< 1,$

suy ra $\mathbb{P}(X)>0$ . $\Box$