Lời giải bài 6 IMO 2025 từ Ban Tổ Chức | Problem 6 Solution 6

Bài toán 6 của IMO 2025 yêu cầu xác định số lượng gạch hình chữ nhật tối thiểu cần đặt trên một lưới 2025×2025 ô vuông đơn vị, sao cho mỗi cạnh của viên gạch nằm trên đường lưới, mỗi ô vuông đơn vị được phủ bởi nhiều nhất một viên gạch, và mỗi hàng, mỗi cột của lưới có đúng một ô vuông không được phủ (gọi là “lỗ”).

TÓM LƯỢC: Cho bảng 2025×2025 ô vuông, cần phủ kín bằng các hình chữ nhật liền mạch, sao cho mỗi hàng và mỗi cột còn đúng 1 ô trống. Không viên nào chồng nhau. Tìm số viên gạch ít nhất.

LỜI GIẢI BÀI 6 – CÂU KHÓ NHẤT!

1. Hiểu Rõ Quy Mô Lưới và Biến Số N:

Lưới là một hình vuông có kích thước 2025×2025. Số 2025 là một số đặc biệt vì nó là một số chính phương (2025 = 45²). Trong các nguồn, khi nói về “lưới n² x n²”, biến ‘n’ này đại diện cho căn bậc hai của chiều dài cạnh lưới. Đối với bài toán này, kích thước lưới là 2025×2025, vậy n = √2025 = 45.

2. Xây Dựng Phương Án Phủ Lưới (Construction):

Mặc dù bài toán này rất phức tạp, nhưng có một phương án xây dựng được đề xuất dựa trên tính chất chính phương của kích thước lưới:

• Ví dụ nhỏ: Với lưới 4×4 (nếu coi n² = 4, thì n=2, nhưng ở đây n là số chính phương mà kích thước lưới là 4×4, tức n=4), việc đặt các lỗ theo đường chéo sẽ cần 6 viên gạch. Tuy nhiên, việc đẩy các lỗ ra mép lưới cho phép chỉ sử dụng 5 viên gạch để phủ phần còn lại.
• Mở rộng cho 9×9: Thay vì đặt một “cối xay gió” lớn, có thể đặt nhiều “cối xay gió” nhỏ hơn (ví dụ, kích thước 3×3, với 3 là căn bậc hai của 9) ở giữa lưới. Điều này cho thấy việc sử dụng tính chất n là một số chính phương là quan trọng.
• Tổng quát cho lưới n² x n²:
  • Các lỗ được mô tả bằng chiều cao của chúng từ trái sang phải, tạo thành một hoán vị.
  • Các lỗ có thể được sắp xếp theo một “mẫu đẹp” bắt đầu từ n, 2n, 3n, … cho đến n² trong một cột, sau đó là các nhóm lỗ ngắn hơn dần.
  • Phần còn lại của lưới được lấp đầy bằng các viên gạch hình chữ nhật dài, đặc biệt là ở các khu vực không phải “cối xay gió”.
• Số lượng gạch theo phương án này: Đối với lưới n² x n² (với n là căn bậc hai của chiều dài cạnh lưới), số lượng gạch cần thiết là n² + 2n – 3.
  • Với lưới 2025×2025, ta có n = 45.
  • Vậy, số gạch theo phương án này là 45² + 2 * 45 – 3 = 2025 + 90 – 3 = 2112.

3. Chứng Minh Giới Hạn Dưới (Lower Bound Proof):

Mục tiêu của phần chứng minh là chỉ ra rằng số lượng gạch tối thiểu không thể ít hơn n² + 2n – 3. Chứng minh này không dựa vào các định lý nâng cao như định lý Dilworth, mà sử dụng các định lý cơ bản hơn.

• Biểu diễn vị trí lỗ: Các vị trí lỗ được coi là một hoán vị của các số từ 1 đến n² (chiều cao của lỗ trong mỗi cột).
• Liên hệ với Dãy con Tăng Dài nhất (LIS) và Dãy con Giảm Dài nhất (LDS):
  • Khẳng định 1: Cho một hoán vị của các số từ 1 đến K. Nếu A là độ dài của LIS và B là độ dài của LDS, thì AB ≥ K. Điều này được chứng minh bằng cách gán cho mỗi phần tử i một cặp nhãn (aᵢ, bᵢ) tương ứng với độ dài LIS và LDS kết thúc tại i. Không có hai phần tử nào có cùng nhãn (aᵢ, bᵢ).
  • Khẳng định 2: Nếu AB = K, thì luôn có thể chọn một LIS có độ dài A và một LDS có độ dài B mà chúng có một phần tử chung.
• Ứng dụng vào bài toán:
  • Kích thước hoán vị K = n². Gọi A là độ dài LIS và B là độ dài LDS của các lỗ.
  • Chúng ta phân chia các lỗ thành các vùng dựa trên LIS và LDS (gọi là lỗ xanh và lỗ đỏ) và gán “mũi tên xanh” và “mũi tên đỏ” để xác định vùng.
  • Mỗi lỗ sẽ có ít nhất một cạnh được “tô bóng” (shaded edge) dựa trên việc nó có cả mũi tên xanh và đỏ ở cùng một hướng.
  • Một lỗ chung giữa LIS và LDS sẽ có cả bốn cạnh được tô bóng.
• Đếm số cạnh được tô bóng:
  • Trường hợp 1: LIS và LDS không có lỗ chung. Khi đó, AB ≥ n² + 1 (vì AB > K = n²). Số cạnh được tô bóng tối thiểu là n² + A + B. Sử dụng bất đẳng thức AM-GM (A+B ≥ 2√AB), ta có số cạnh tô bóng tối thiểu là n² + 2n + 1 (vì A+B ≥ 2√(n²+1) ≥ 2n+1).
  • Trường hợp 2: LIS và LDS có lỗ chung. Khi đó, AB = n² (theo Khẳng định 2, chúng ta chọn chúng giao nhau). Số cạnh được tô bóng tối thiểu là n² + A + B + 1 (cộng thêm 1 cho lỗ chung). Sử dụng AM-GM (A+B ≥ 2√AB = 2n), ta có số cạnh tô bóng tối thiểu là n² + 2n + 1.
  • Trong cả hai trường hợp, số cạnh được tô bóng tối thiểu là n² + 2n + 1.
• Liên hệ cạnh được tô bóng với số gạch:
  • Quan sát 1: Mỗi viên gạch hình chữ nhật chỉ có thể chạm vào nhiều nhất một cạnh được tô bóng. (Đây là một điểm phức tạp liên quan đến cách định nghĩa các vùng và mũi tên).
  • Quan sát 2: Nếu một cạnh được tô bóng không nằm trên mép lưới, thì phải có một viên gạch chạm vào nó.
  • Từ đó, số lượng gạch hình chữ nhật ≥ (Tổng số cạnh được tô bóng) – (Số cạnh được tô bóng nằm trên mép lưới).
  • Có 4 cạnh của lưới, nên ta trừ đi 4 (tức là 1 cho mỗi cạnh lưới).
  • Số gạch tối thiểu ≥ (n² + 2n + 1) – 4 = n² + 2n – 3.

4. Kết Luận Cuối Cùng:

Dựa trên phương án xây dựng đã đưa ra và chứng minh giới hạn dưới, số lượng gạch tối thiểu cần để phủ lưới 2025×2025 ô vuông là n² + 2n – 3, với n = 45 (căn bậc hai của 2025). Vậy, số gạch tối thiểu cần là: 45² + 2 * 45 – 3 = 2025 + 90 – 3 = 2112.

Sự tương đồng

Sự tương đồng: Việc giải quyết bài toán này, đặc biệt là phần chứng minh, giống như một người thám tử đang điều tra một vụ án phức tạp. Các “lỗ” không được che phủ là những manh mối quan trọng. Việc phân tích LIS và LDS của các vị trí lỗ giống như việc tìm kiếm các mô hình hoặc xu hướng trong các manh mối đó. Các “cạnh được tô bóng” (shaded edges) giống như những điểm yếu hoặc ranh giới nhạy cảm mà những viên gạch (tức là các yếu tố che phủ) phải tránh hoặc chỉ có thể tiếp xúc một cách hạn chế. Cuối cùng, bằng cách định lượng số lượng các điểm yếu này và biết mỗi viên gạch chỉ có thể xử lý bao nhiêu điểm yếu, bạn có thể suy luận ra số lượng tối thiểu các viên gạch cần thiết, giống như một thám tử suy ra số lượng thủ phạm tối thiểu dựa trên bằng chứng thu thập được.