Một chuyên gia ẩm thực cần đưa ra đánh giá về $n$ nhà hàng trong thành phố, trong đó $n$ là một số nguyên dương. Mỗi cặp nhà hàng được vị chuyên gia so sánh với nhau theo hai tiêu chí: độ ngon của món ăn và chất lượng phục vụ. Với một số cặp nhà hàng, vị chuyên gia không thể quyết định nhà hàng nào tốt hơn nhà hàng còn lại trong một tiêu chí nào đó, nhưng điều này không xảy ra đồng thời ở cả hai tiêu chí. Ngoài ra, nếu vị chuyên gia cho rằng nhà hàng $A$ tốt hơn nhà hàng $B$ ở một tiêu chí nào đó, và đồng thời cho rằng nhà hàng $B$ tốt hơn nhà hàng $C$ trong cùng tiêu chí đó, thì ông ta cũng đánh giá rằng nhà hàng $A$ tốt hơn nhà hàng $C$ trong tiêu chí ấy.

Chứng minh rằng tồn tại một nhà hàng $R$ sao cho mọi nhà hàng khác đều bị vị chuyên gia đánh giá kém hơn nhà hàng $R$ trong ít nhất một tiêu chí.

Ta nói nhà hàng $A$ là nổi trội trong tập các nhà hàng $S$ nếu $A$ tốt hơn ít nhất một tiêu chí so với mọi nhà hàng khác trong $S\setminus \{A\}$. Ta sẽ chứng minh bằng quy nạp theo số nhà hàng rằng trong mọi tập nhà hàng không rỗng luôn tồn tại ít nhất một nhà hàng nổi trội.
Nếu chỉ có một nhà hàng thì hiển nhiên nó là nổi trội. Giả sử mệnh đề đúng với mọi tập không rỗng có $<n$ nhà hàng. Ta sẽ chứng minh nó đúng với $n$ nhà hàng.
Ký hiệu tập $n\ge 2$ nhà hàng là $\mathcal{R}$. Chọn một nhà hàng $A\in \mathcal{R}$ tùy ý.
Theo giả thiết quy nạp, trong tập $\mathcal{R}\setminus \{A\}$ tồn tại một nhà hàng nổi trội, gọi là $B$.
Ký hiệu ${\mathcal{O}}_B$ là tập các nhà hàng trong $\mathcal{R}\setminus \{A\}$ có chất lượng phục vụ kém hơn $B$, và ${\mathcal{P}}_B$ là tập các nhà hàng trong $\mathcal{R}\setminus \{A\}$ có món ăn kém hơn $B$.
Hiển nhiên ${\mathcal{O}}_B\cup {\mathcal{P}}_B=\mathcal{R}\setminus \{A,B\}$.
Giữa $A$ và $B$ có các khả năng sau: (0.5 điểm)

Trường hợp 1: $B$ tốt hơn $A$ trong một tiêu chí nào đó. Khi này $B$ là nhà hàng nổi trội trong $\mathcal{R}$. (0.5 điểm)

Trường hợp 2: $A$ tốt hơn $B$ trong cả hai tiêu chí. Khi này $A$ cũng có chất lượng phục vụ tốt hơn mọi nhà hàng trong ${\mathcal{O}}_B$ và có chất lượng món ăn tốt hơn mọi nhà hàng trong ${\mathcal{P}}_B$. Do đó $A$ là nhà hàng nổi trội trong $\mathcal{R}$. (1 điểm)

Trường hợp 3: $A$ tốt hơn $B$ trong đúng một tiêu chí. Không mất tính tổng quát, giả sử $A$ có chất lượng phục vụ tốt hơn $B$. Khi đó $A$ cũng có chất lượng phục vụ tốt hơn mọi nhà hàng trong ${\mathcal{O}}_B$.
Theo giả thiết quy nạp, trong tập ${\mathcal{P}}_B\cup \{A\}$ tồn tại một nhà hàng nổi trội, gọi là $C$.
Nếu $C=A$ thì $A$ có chất lượng phục vụ tốt hơn mọi nhà hàng trong ${\mathcal{O}}_B\cup \{B\}$, và $A$ nổi trội trong ${\mathcal{P}}_B\cup \{A\}$. Do đó $A$ nổi trội trong ${\mathcal{O}}_B\cup \{B\}\cup {\mathcal{P}}_B\cup \{A\}=\mathcal{R}$. (1 điểm)

Giả sử $C\ne A$. Khi đó $C$ tốt hơn $A$ trong một tiêu chí nào đó. Nếu $C$ có chất lượng món ăn tốt hơn $A$ thì suy ra $B$ cũng có chất lượng món ăn tốt hơn $A$, mâu thuẫn với giả thiết. Vì vậy $C$ phải có chất lượng phục vụ tốt hơn $A$. Khi đó $C$ có chất lượng phục vụ tốt hơn mọi nhà hàng trong $\{A,B\}\cup {\mathcal{O}}_B$. Hơn nữa, theo giả thiết $C$ nổi trội trong ${\mathcal{P}}_B\cup \{A\}$, nên $C$ nổi trội trong $\{A,B\}\cup {\mathcal{O}}_B\cup {\mathcal{P}}_B=\mathcal{R}$. Điều này hoàn tất bước quy nạp, và do đó bài toán được giải quyết. (1 điểm)