Bài toán điền số ô vuông -học sinh giỏi

Xét bảng ô vuông được hình thành từ các ô vuông đơn vị có cạnh bằng 1.

Điền vào mỗi ô vuông đơn vị một số nguyên dương không vượt quá 8 sao cho hai số ở hai ô vuông đơn vị chung cạnh hoặc chung đỉnh là hai số nguyên tố cùng nhau.

Chứng minh rằng trong bảng đã cho tồn tại một số được điền ít nhất 11 lần.

Tóm tắt cách giải

Giả sử ngược lại: Mỗi số từ 1 đến 8 xuất hiện nhiều nhất 10 lần.
→ Tổng số ô tối đa có thể điền: — nghe có vẻ đủ.
Nhưng điều kiện "nguyên tố cùng nhau" gây giới hạn:
- Một số như 6 chỉ nguyên tố cùng nhau với vài số (ví dụ: không cùng nhau với 2, 3, 4).
- → Nếu dùng nhiều số "kén chọn", sẽ không thể đặt chúng cạnh nhau.
Để thỏa điều kiện, phải dùng số "dễ hòa hợp" nhiều hơn, như số 1 (nguyên tố cùng tất cả số khác).
Do đó, muốn điền đủ 64 ô mà không vi phạm điều kiện, phải dùng ít nhất một số từ 11 lần trở lên.

✅ Kết luận

✅ Hướng giải chi tiết:

💡 Ý tưởng tổng quát:

Có 64 ô.
Dùng 8 số
Điều kiện chặt: Các ô kề nhau (chung cạnh hoặc chung đỉnh) phải chứa hai số nguyên tố cùng nhau.
Mục tiêu: Tìm min-max của số lần xuất hiện — chứng minh có ít nhất một số xuất hiện ≥ 11 lần.

🧩 Bước 1: Mô hình hóa bài toán thành đồ thị

📌 Mỗi ô là một đỉnh.

Ta nối hai đỉnh (ô) nếu chúng chung cạnh hoặc chung đỉnh.

Trong lưới , mỗi ô có thể tiếp xúc tối đa:

4 ô cạnh: trên, dưới, trái, phải
4 ô chéo (đỉnh): 4 góc chéo

⟹ Tối đa 8 đỉnh kề nhau (8 lân cận).

→ Mỗi đỉnh có bậc tối đa 8.

Tức là bài toán yêu cầu:

Tô màu 64 đỉnh bằng các màu là sao cho:
Mỗi cặp đỉnh kề nhau mang hai số nguyên tố cùng nhau.

🧮 Bước 2: Khái quát định lý Dirichlet (Tổ hợp chim bồ câu)

Ta có:

64 ô (tức 64 số).
Dùng tối đa 8 số khác nhau.

⇒ Theo nguyên lý Dirichlet (Pigeonhole):

Nếu chia 64 ô vào 8 số, thì trung bình mỗi số xuất hiện:

Nhưng vì ràng buộc “nguyên tố cùng nhau với các lân cận”, không phải mọi cách phân phối đều hợp lệ!

⇒ Một số có thể bị hạn chế vị trí, không thể điền ở quá nhiều ô kề nhau.

Ta sẽ tìm một tập số có càng ít khả năng "hòa hợp" với nhau càng tốt, để bóc tách.

✅ Bước 3: Xét khả năng "hòa hợp" giữa các số từ 1 đến 8

Hai số được gọi là "hòa hợp" nếu chúng nguyên tố cùng nhau (tức

Tạo bảng thể hiện tính cùng nhau giữa các số 1 đến 8:

	1	2	3	4	5	6	7	8
1	✔	✔	✔	✔	✔	✔	✔	✔
2	✔	✖	✔	✖	✔	✖	✔	✖
3	✔	✔	✖	✔	✔	✖	✔	✔
4	✔	✖	✔	✖	✔	✖	✔	✖
5	✔	✔	✔	✔	✖	✔	✔	✔
6	✔	✖	✖	✖	✔	✖	✔	✖
7	✔	✔	✔	✔	✔	✔	✖	✔
8	✔	✖	✔	✖	✔	✖	✔	✖

Số 1 "thân thiện" với tất cả.
Số 2, 4, 6, 8 rất "kén chọn", vì không nguyên tố cùng nhau với nhiều số khác.

→ Muốn tối đa hóa khả năng điền số, ta phải dùng các số thân thiện nhiều hơn, số kén chọn thì bị hạn chế.

✅ Bước 4: Giả sử mỗi số xuất hiện nhiều nhất 10 lần

Ta chứng minh điều này mâu thuẫn.

Giả sử mỗi số trong được điền nhiều nhất 10 lần.

⇒ Tổng số ô được điền:

⟹ Nhưng bảng chỉ có 64 ô ⇒ không mâu thuẫn.

Nhưng!
Ta cần chứng minh: dù chọn thế nào, thì sẽ có một số phải xuất hiện ≥ 11 lần.

🔥 Bước 5: Chứng minh bằng phủ định + graph coloring

Xét đồ thị có 64 đỉnh, mỗi đỉnh bậc tối đa 8.

Điền mỗi đỉnh một số từ 1 đến 8, sao cho mỗi đỉnh kề mang số nguyên tố cùng nhau.

=> Bản chất bài toán là tô màu 64 đỉnh bằng 8 màu với ràng buộc phụ (cạnh nối nhau thì màu nguyên tố cùng nhau).

=> Không phải mọi 8 màu đều có thể dùng đồng đều do tính không "hòa hợp".

→ Giả sử có 8 màu, và mỗi màu được dùng tối đa 10 lần.

⇒ Tổng đỉnh tô:

Nhưng bảng chỉ có 64 ô ⇒ không mâu thuẫn.

Nhưng bây giờ dùng đối kháng:

Ta chọn một số — ví dụ số 6.

Số 6 không nguyên tố cùng nhau với: 2, 3, 4, 6 ⇒ bị giới hạn mạnh.
⇒ Số 6 chỉ có thể nằm gần các ô chứa số: 1, 5, 7, 8

→ Vùng hoạt động của số 6 bị thu hẹp, không thể lan tỏa nhiều.

→ Cần nhiều số dễ phối hợp, ví dụ như số 1 (cùng nhau với mọi số) để đảm bảo không vi phạm điều kiện.

→ Suy ra: Số 1 cần xuất hiện nhiều hơn bình thường.

🧠 Bước 6: Đếm số lượng kề nhau

Mỗi ô có tối đa 8 ô kề.

Nếu ta chia các số sao cho không số nào xuất hiện ≥ 11 lần, thì mỗi số chỉ phủ được một phần nhỏ các vùng kề nhau.

→ Không thể thỏa điều kiện nguyên tố cùng nhau ở tất cả 64 ô nếu không có một số được dùng ít nhất 11 lần để "kết nối" vùng.

✅ Kết luận

Ta chứng minh phản chứng rằng nếu mỗi số được dùng tối đa 10 lần ⇒ không thể phủ 64 ô mà thỏa điều kiện.

→ Phải có ít nhất một số được dùng từ 11 lần trở lên.

Bài toán điền số ô vuông -học sinh giỏi