Trong 2 bạn đấu với nhau có kết quả thắng thua phân định thì ta có thể xếp bạn thắng đứng sau bạn thua, do đó ta luôn xếp được 1 hàng mà bạn đứng sau thắng bạn đứng trước (ít nhất là 2), trong các cách xếp hàng đó thì tồn tại một cách xếp có nhiều bạn nhất, gọi số bạn thuộc hàng này là k.

Giả sử bài toán không đúng tức $$k<n$$. Khi đó sẽ tồn tại một bạn a tham gia và không thuộc hàng đó, xét kết quả của bạn đó với k bạn thuộc hàng thì ta có 3 trường hợp:

Trường hợp 1: a thắng tất cả thì suy ra a thắng người cuối cùng của hàng và a có thể được xếp ở cuối hàng

Trường hợp 2: a thua tất cả thì dẫn đến a thua bạn đầu tiên của hàng nên a có thể được xếp ở đầu hàng.

Trường hợp 3: Nếu có cả kết quả thắng và thua thì sẽ tồn tại 2 bạn b và c liên tiếp để a thắng b và a thua c . Khi đó ta có thể xếp a giữa b và c .

Như vậy a cũng có thể được xếp vào hàng trên nên điều giả sử ban đầu k là số bạn nhiều nhất là vô lí. Vậy $$k=n$$. Bài toán được chứng minh.