Câu hỏi 29
Cho số nguyên $n \ge 2$. Hai người chơi Alice và Bob chơi trò chơi sau: Ban đầu tất cả $\binom{n}{2}$ cạnh của đồ thị đầy đủ $K_n$ đều chưa được tô màu. Họ lần lượt tô đỏ các cạnh, Alice đi trước. Trong mỗi lượt, người chơi chọn một hoặc hai cạnh chưa tô để tô đỏ, với ràng buộc là sau mỗi lượt, không có ba đỉnh nào mà cả ba cạnh nối giữa chúng đều được tô đỏ. Trò chơi kết thúc khi không thể tô thêm cạnh nào.
Chứng minh rằng tồn tại số thực $\varepsilon \gt 0$ sao cho với mọi số nguyên $n \ge 2$, bất kể Bob chơi thế nào, Alice luôn có thể đảm bảo rằng khi trò chơi kết thúc, số cạnh đỏ không vượt quá $\left(\frac{1}{4} - \varepsilon\right)n^2 + n$.
Chứng minh rằng tồn tại số thực $\varepsilon \gt 0$ sao cho với mọi số nguyên $n \ge 2$, bất kể Bob chơi thế nào, Alice luôn có thể đảm bảo rằng khi trò chơi kết thúc, số cạnh đỏ không vượt quá $\left(\frac{1}{4} - \varepsilon\right)n^2 + n$.