Bài toán ba nhà ba giếng hỏi: có thể nối mỗi ngôi nhà trong ba ngôi nhà với cả ba cái giếng (hoặc ba nguồn điện, nước, ga) bằng những con đường không cắt nhau không? Câu trả lời là không, trên mặt phẳng hay mặt cầu đều không làm được. Lý do nằm ở công thức Euler cho đồ thị phẳng, và đây là bài toán mở đầu cho cả một lĩnh vực có ứng dụng thật: thiết kế mạch điện in.
Đề bài
Vẽ ba ngôi nhà ở hàng trên, ba cái giếng ở hàng dưới. Mỗi nhà cần một con đường riêng đến mỗi giếng — tổng cộng 9 con đường. Các con đường được vẽ cong tuỳ ý, nhưng không được cắt nhau, không được đi xuyên qua nhà hay giếng khác. Bản tiếng Anh quen thuộc hơn là "ba nhà, ba nguồn tiện ích": điện, nước, ga.
Câu đố này xuất hiện trên báo và sách đố vui ở Anh, Mỹ từ đầu thế kỷ 20, và nhà soạn câu đố Henry Dudeney từng đưa nó vào sách của mình. Hàng triệu người đã thử; ai cũng nối được 8 đường, đến đường thứ 9 thì kẹt.
Thử và kẹt ở đâu
Hãy thử: nối nhà 1 với ba giếng, nhà 2 với ba giếng — đến đây mọi thứ vẫn ổn, giấy bị chia thành vài vùng. Nhà 3 nối được với hai giếng. Nhưng giếng còn lại luôn nằm ở một vùng mà nhà 3 không thể đi tới nếu không cắt qua một đường đã có. Đổi cách vẽ đến đâu, kết quả vẫn thế.
Chứng minh bằng công thức Euler
Với một đồ thị vẽ trên mặt phẳng mà các cạnh không cắt nhau (gọi là đồ thị phẳng), Euler tìm ra một công thức đẹp:
Số đỉnh − Số cạnh + Số mặt = 2
"Mặt" là các vùng mà các cạnh chia mặt phẳng ra, kể cả vùng vô hạn bao bên ngoài. Kiểm thử với một hình vuông: 4 đỉnh, 4 cạnh, 2 mặt (trong và ngoài) → 4 − 4 + 2 = 2.
Áp dụng cho ba nhà ba giếng: 6 đỉnh, 9 cạnh. Nếu vẽ được không cắt nhau, số mặt phải là 2 − 6 + 9 = 5.
Giờ đếm theo cách khác. Đường chỉ đi từ nhà đến giếng, không bao giờ nhà nối nhà hay giếng nối giếng. Vì vậy mỗi mặt phải được bao bởi ít nhất 4 cạnh (nhà – giếng – nhà – giếng – quay về). 5 mặt × 4 cạnh = 20, nhưng mỗi cạnh chỉ giáp nhiều nhất 2 mặt, nên cần ít nhất 10 cạnh. Ta chỉ có 9. Mâu thuẫn → không thể vẽ.
Hai "kẻ phá đám": K₃,₃ và K₅
Trong ký hiệu toán học, đồ thị ba nhà ba giếng gọi là K₃,₃ (mỗi đỉnh của nhóm này nối với mọi đỉnh của nhóm kia). Một đồ thị nổi tiếng khác cũng không vẽ phẳng được là K₅: năm điểm, mỗi điểm nối với cả bốn điểm còn lại.
Năm 1930, nhà toán học Ba Lan Kazimierz Kuratowski chứng minh một điều đáng kinh ngạc: một đồ thị không vẽ phẳng được khi và chỉ khi bên trong nó "giấu" một bản của K₃,₃ hoặc K₅ (có thể bị kéo dài cạnh). Nói cách khác, mọi rắc rối của chuyện vẽ không cắt đều quy về hai hình này.
| Đồ thị | Số đỉnh | Số cạnh | Vẽ phẳng được? |
|---|---|---|---|
| K₄ (bốn điểm nối đôi một) | 4 | 6 | Được |
| K₅ | 5 | 10 | Không |
| K₂,₃ (hai nhà ba giếng) | 5 | 6 | Được |
| K₃,₃ (ba nhà ba giếng) | 6 | 9 | Không |
"Lời giải" gian lận và lời giải hợp lệ trên bề mặt khác
Nhiều người đưa "lời giải" bằng cách cho đường đi xuyên qua một ngôi nhà, hoặc vẽ đường ra ngoài tờ giấy rồi vòng lại. Đó là lách luật. Nhưng có một cách đổi luật thú vị và hoàn toàn hợp lệ: vẽ trên mặt bánh rán (mặt xuyến, như chiếc phao bơi). Trên mặt này, con đường thứ 9 có thể đi vòng qua "lỗ" của chiếc phao và tới đích mà không cắt đường nào. Bài toán chỉ không giải được trên mặt phẳng và mặt cầu.
Trên một chiếc cốc có quai cũng vậy: cái quai đóng vai trò cái lỗ. Đây là một ví dụ dễ hiểu cho câu nói đùa của dân toán: "Nhà tô-pô học không phân biệt được chiếc cốc với chiếc bánh rán".
Ứng dụng thật: mạch điện in
Trên một bảng mạch điện tử, các đường đồng nối linh kiện không được cắt nhau trên cùng một lớp, nếu không sẽ chập. Khi thiết kế mạch, kỹ sư phải giải đúng bài toán ba nhà ba giếng ở quy mô lớn: những kết nối nào vẽ được trên một mặt, những kết nối nào buộc phải đưa sang lớp thứ hai qua lỗ xuyên. Các mạch hiện đại có nhiều lớp chính vì đồ thị nối linh kiện thường không phẳng.
Ý tưởng tương tự xuất hiện khi quy hoạch đường ống, đường dây trong một toà nhà, hay khi thiết kế các nút giao thông: chỗ nào hai luồng bắt buộc phải gặp nhau thì cần cầu vượt hoặc hầm chui — "lớp thứ hai" của mặt đường.
Góc nhìn hôm nay: đố bạn, rồi giải thích
Bài ba nhà ba giếng là câu đố tuyệt vời để đưa bạn bè, con cái vào toán học. Đưa đề, để họ thử vài phút. Khi họ bắt đầu chắc chắn "không được", hỏi lại: "Làm sao em biết chắc là không ai làm được, chứ không phải em chưa tìm ra?" Đó chính là câu hỏi phân biệt giữa thử nghiệm và chứng minh. Rồi hãy đếm cùng họ: 6 đỉnh, 9 cạnh, 5 mặt, mỗi mặt ít nhất 4 cạnh. Ba dòng lập luận đó đóng lại một câu đố mà hàng triệu người đã thử.
Câu hỏi thường gặp
Bài toán ba nhà ba giếng có giải được không?
Không, trên mặt phẳng hoặc mặt cầu đều không giải được. Có thể chứng minh bằng công thức Euler: đồ thị có 6 đỉnh, 9 cạnh nhưng nếu vẽ phẳng sẽ cần ít nhất 10 cạnh.
Công thức Euler cho đồ thị phẳng là gì?
Với đồ thị liên thông vẽ trên mặt phẳng không có cạnh cắt nhau, số đỉnh trừ số cạnh cộng số mặt luôn bằng 2. Mặt bao gồm cả vùng vô hạn bên ngoài.
K₃,₃ là gì?
Là ký hiệu của đồ thị gồm hai nhóm ba đỉnh, mỗi đỉnh nhóm này nối với mọi đỉnh nhóm kia — chính là đồ thị ba nhà ba giếng. Nó cùng với K₅ là hai đồ thị cơ bản không vẽ phẳng được.
Có bề mặt nào giải được bài ba nhà ba giếng không?
Có. Trên mặt xuyến, như chiếc phao bơi hay chiếc cốc có quai, con đường thứ chín có thể đi vòng qua lỗ mà không cắt đường nào.
Bài toán này có ứng dụng gì?
Trong thiết kế mạch điện in, các đường dẫn trên cùng một lớp không được cắt nhau. Khi đồ thị nối linh kiện không phẳng, kỹ sư phải dùng thêm lớp mạch và lỗ xuyên.