Câu hỏi 87
Alice và Bob chơi trò chơi với 2011 bảng $2011\times2011$: Bob nhận một bảng, Alice nhận 2010 bảng còn lại. Họ làm việc riêng và điền vào mỗi bảng các số $1,2,\ldots,2011^2$ sao cho các số tăng nghiêm ngặt theo hàng từ trái sang phải và theo cột từ trên xuống dưới. Không có hai bảng của Alice được điền giống hệt nhau. Sau khi điền xong, Bob được xem các bảng của Alice rồi đổi chỗ từng cặp số trong bảng mình, miễn là sau mỗi lần đổi, bảng vẫn hợp lệ (tăng theo hàng và cột). Khi Bob đổi xong, chọn ngẫu nhiên một bảng của Alice. Nếu có hai số nguyên cùng cột trong bảng được chọn nhưng cùng hàng trong bảng Bob thì Bob thắng; nếu không, Alice thắng. Nếu Bob chọn bảng ban đầu một cách tối ưu, số lần đổi chỗ tối đa mà Bob có thể cần để bảo đảm thắng là bao nhiêu?