Một câu lạc bộ cờ vua không có hòa#
Sáu người trong một câu lạc bộ cờ vua mỗi người chơi với mọi thành viên khác một lần. Mỗi ván đều có người thắng. Bạn có luôn xếp được cả sáu người thành hàng sao cho mỗi người thắng người kế tiếp trong hàng không?
Câu trả lời đáng ngạc nhiên là có, luôn luôn, bất kể ai thắng ai. Trang này chứng minh điều đó.
Từ vựng, mỗi từ một mệnh đề. Một giải đấu chính xác là thiết lập này: mọi cặp chơi một lần và một trong hai người thắng. Trong ngôn ngữ đồ thị, người chơi là đỉnh và mỗi ván là một cạnh có mũi tên chỉ từ người thắng đến người thua. Một đường đi có hướng đi theo các mũi tên. Một đường đi Hamilton là một đường đi có hướng đi qua mọi đỉnh đúng một lần.
Định lý. Mọi giải đấu đều có một đường đi Hamilton.
Vì sao bạn không thể kiểm tra hết#
Với 6 người chơi, mỗi người chơi 5 trận, đếm ra 6 · 5 = 30, nhưng mỗi trận bị đếm hai lần, mỗi người chơi một lần. Vậy có 15 trận.
Mỗi trận có thể diễn ra theo 2 cách, nên có 215 = 32.768 giải đấu khác nhau trên 6 người chơi có gán nhãn. Với 10 người chơi có 45 trận và 245 giải đấu, nhiều hơn 35 nghìn tỷ. Kiểm tra từng cái một không phải là một chứng minh và không khả thi. Quy nạp xử lý mọi kích thước cùng lúc.
Chứng minh bằng quy nạp theo số người chơi#
Chúng ta quy nạp theo n, số đỉnh.
Bước cơ sở, n = 2. Có một ván. Bắt đầu từ người thắng và đi đến người thua. Đường đi đó đi qua cả hai người chơi. Xong.
Giả thiết quy nạp. Giả sử mọi giải đấu có n người chơi (với một n ≥ 2 nào đó) đều có một đường đi Hamilton.
Bước quy nạp. Lấy một giải đấu bất kỳ có n + 1 người chơi. Đặt một người chơi sang một bên; gọi họ là v. n người chơi còn lại, cùng các ván giữa họ, tạo thành một giải đấu trên n người chơi. Theo giả thiết quy nạp nó có một đường đi Hamilton. Đánh số các người chơi dọc theo đường đi đó:
1 → 2 → 3 → … → n (mỗi người thắng người kế tiếp).
Giờ đặt v trở lại. v đã chơi với từng người trong số họ, nên mọi cặp (v, i) có một mũi tên theo hướng này hoặc hướng kia.
- Nếu v thắng người chơi 1, đặt v lên đầu: v → 1 → 2 → … → n.
- Nếu không thì người chơi 1 thắng v. Đi dọc theo đường đi và dừng ở người chơi i đầu tiên mà v thắng. Người ngay trước đó, i − 1, không thua v, nên i − 1 thắng v. Chèn v vào giữa: … → i − 1 → v → i → …
- Nếu v không thắng ai, thì cụ thể n thắng v. Đặt v ở cuối: 1 → … → n → v.
Trong mọi trường hợp chúng ta có một đường đi qua tất cả n + 1 người chơi, mỗi người thắng người kế tiếp.
Kết luận. Theo nguyên lý quy nạp toán học, mọi giải đấu có n ≥ 2 người chơi đều có một đường đi Hamilton.
Bỏ một người chơi, xếp những người còn lại theo giả thiết quy nạp, và đặt người đã bỏ ngay trước người đầu tiên mà họ thắng, hoặc ở cuối nếu họ không thắng ai.
Chứng minh này cũng là một thuật toán#
Giáo sư của bạn nhấn mạnh rằng một chứng minh quy nạp tốt có thể được biến thành một chương trình. Chứng minh này làm được. Bắt đầu với một người chơi. Thêm những người khác từng người một, mỗi lần chèn người mới ngay trước người đầu tiên trong hàng hiện tại mà họ thắng (hoặc ở cuối). Khi mọi người đã vào, bạn có đường đi.
Quy trình đó đã được chạy trên 5.000 giải đấu ngẫu nhiên có từ 2 đến 10 người chơi trong lúc viết bài hướng dẫn này. Lần nào nó cũng tạo ra một đường đi Hamilton hợp lệ.
Sai ở chỗ nào#
- Luôn đặt người chơi mới ở cuối. Cách đó chỉ đúng khi người chơi n thắng v.
- Dừng ở một người chơi bất kỳ mà v thắng, không phải người đầu tiên. Lập luận cần người ngay trước đó đã thắng v, và điều đó chỉ được đảm bảo cho người đầu tiên như vậy.
- Bắt đầu từ n = 1. Với một người chơi không có ván nào, nên “giải đấu” không nói được điều gì hữu ích. Bước cơ sở của bài giảng là n = 2 (một đường đi một đỉnh cũng hiển nhiên ổn, nhưng hãy nói rõ bạn dùng cái nào).
- Quên dùng giả thiết. Toàn bộ bước chứng minh dựa vào đường đi qua n người chơi còn lại. Hãy nói to nó đến từ đâu.
Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí
Luyện tập Discrete Math theo chủ đề: dùng được khi không có mạng, không quảng cáo, không cần tài khoản.
Luyện tập chứng minh quy nạp →Câu hỏi thường gặp#
Giải đấu (tournament) trong lý thuyết đồ thị là gì?
Giải đấu là một đồ thị có hướng đầy đủ: mọi cặp đỉnh được nối bởi đúng một cạnh, và mỗi cạnh có một hướng. Bạn có thể đọc nó như một cuộc thi vòng tròn không có hòa, mũi tên chỉ từ người thắng đến người thua.
Đường đi Hamilton là gì?
Một đường đi đi qua mọi đỉnh đúng một lần. Trong đồ thị có hướng nó còn phải đi theo các mũi tên, nên trong một giải đấu nó là một hàng xếp tất cả người chơi trong đó mỗi người thắng người kế tiếp.
Mọi giải đấu có đường đi Hamilton không?
Có. Chứng minh bằng quy nạp theo số người chơi: bỏ đi một người chơi, tìm một đường đi Hamilton qua những người còn lại nhờ giả thiết quy nạp, và chèn người đã bỏ vào ngay trước người đầu tiên trên đường đi mà họ thắng, hoặc vào cuối nếu họ không thắng ai.
Một cuộc thi vòng tròn của n người chơi có bao nhiêu trận?
n(n − 1)/2, vì mỗi trong n người chơi n − 1 trận và mỗi trận được đếm hai lần. Với 6 người chơi đó là 15 trận, và có 2^15 = 32.768 kiểu kết quả có thể xảy ra.
Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.