Câu hỏi 170
Giữa $n \ge 8$ sân bay có một số chuyến bay thẳng một chiều. Giữa hai sân bay bất kỳ $a$ và $b$, có nhiều nhất một chuyến bay thẳng một chiều từ $a$ đến $b$ (có thể có đồng thời chuyến bay thẳng một chiều từ $a$ đến $b$ và từ $b$ đến $a$). Giả sử rằng với mọi tập $A$ gồm một số sân bay với $1 \le |A| \le n-1$, có tổng cộng ít nhất $4 \cdot \min\{|A|, n-|A|\}$ chuyến bay xuất phát từ các sân bay thuộc $A$ và đến các sân bay không thuộc $A$.
Chứng minh rằng với mọi sân bay $x$, có thể xuất phát từ $x$ và đi không quá $\sqrt{2n}$ chuyến bay để quay trở lại $x$.
Chứng minh rằng với mọi sân bay $x$, có thể xuất phát từ $x$ và đi không quá $\sqrt{2n}$ chuyến bay để quay trở lại $x$.