Các kết nối Facebook dưới dạng toán đồ thị
Phương pháp dùng hình vẽ, hình mô phỏng để giải toán ở chương trình tiểu học giúp HS hiểu và giải được một số bài toán dạng logic, dạng kết hợp, tổ hợp…Tài liệu này giới thiệu một cách giải bài toán lí thú về kêt nối Facebook để các ban tham khảo và ứng dụng.
-----------------------------------------------------------------------
1/- Mạng kết nối facebook
Trường hợp một người tham gia “Mạng kết nối facebook” chọn bất kỳ 6 người nào đó trên facebook, thì có thể chọn ra được 3 người:
Hoặc là, cả 3 người này đều là friend của nhau,
Hoặc là, trong 3 người này không có ai là friend của ai cả.
Giả thử có các mối kết nối qua hình minh họa:
Hình 1a :
có 6 bạn: An, Bảo, Cường, Chi, Dũng và Đạt. Nếu như hai bạn là friend của nhau trên facebook thì chúng ta kết nối họ lại bằng một đường màu tím, còn nếu họ không là friend thì chúng ta nối lại bằng đường màu xanh.
Ta thấy trong 6 bạn này, có thể chọn ra 3 bạn là An, Dũng và Chi, cả 3 bạn này đều là friend của nhau bởi vì họ được nối bởi các đường màu tím. Trường hợp 3 bạn Đạt, Bảo và Cường cũng vậy.
Hình 1b :
có 6 bạn: Kim, Lan, Mai, Nam, Nga và Nhi. Ta có thể chọn ra được 3 bạn là Nga, Mai và Nam, trong 3 bạn này không có ai là friend của ai cả bởi vì các bạn này được nối bởi các đường màu xanh. Ba bạn Nhi, Nam và Mai cũng vậy.
* Qua mô tả minh họa trường hợp kết nối trên, chúng ta làm quen với một loại toán gọi là “toán đồ thị”. Một đồ thị bao gồm các đỉnh và cáccạnh. Cạnh là đoạn thẳng dùng để nối hai đỉnh lại với nhau. Đồ thị trong bài toán của chúng ta có 6 đỉnh tượng trưng cho 6 người, giữa hai đỉnh bất kỳ được nối bằng đúng một cạnh, và các cạnh này được tô bằng hai màu là xanh và tím.
2/ Liên hệ “Toán đồ thị” đơn giản
Trong một đồ thị bất kỳ, có khi giữa hai đỉnh không có cạnh nào, hoặc có khi chúng được nối lại bằng nhiều hơn một cạnh. Các cạnh cũng có khi là vô hướng như trong bài toán của chúng ta, hoặc cũng có khi là có hướng, và có thể được tô màu, hoặc là không tô màu.
Hình 2 (a,b,c,d) dưới đây là một vài ví dụ về bài toán đồ thị.
Bây giờ quay trở lại với trường hợp 6 người kết nối facebook nêu trên. Nếu phát biểu theo ngôn ngữ đồ thị thì bài toán của chúng ta sẽ như sau.
Bài toán:
Cho một đồ thị gồm 6 đỉnh mà hai đỉnh bất kỳ được nối bằng một cạnh có màu xanh hoặc màu tím.
Chứng minh rằng tồn tại một tam giác có các cạnh đều là màu tím hoặc đều là màu xanh.
Chúng ta sẽ dùng nguyên lý Dirichlet để chứng minh bài toán . Nguyên lý Dirichlet phát biểu một cách đơn giản là nếu chúng ta nhốt 5 con chim bồ câu vào hai cái chuồng thì sẽ có một chuồng có ít nhất là 3 con bồ câu. (Minh họa tại hình 3 )
Chứng minh bài toáni đồ thị facebook,
Ta chọn một đỉnh bất kỳ, chẳng hạn như đỉnh "An". Từ đỉnh "An" chúng ta có 5 cạnh. Chúng ta xem 5 cạnh này như 5 con chim bồ câu, nếu cạnh màu tím thì nhốt vào chuồng màu tím, còn cạnh màu xanh thì nhốt vào chuồng màu xanh. Hình 4
Theo nguyên lý Dirichlet thì sẽ có một chuồng có ít nhất là 3 con chim bồ câu. Chúng ta giả sử đó là chuồng màu tím. Có nghĩa là chúng ta có ít nhất 3 cạnh màu tím.
(Giả sử như cạnh An-Dũng, cạnh An-Chi và cạnh An-Cường là màu tím như hình 4 )
* Bây giờ chúng ta xem xét tam giác Dũng-Chi-Cường. Nếu một cạnh của tam giác này là màu tím, chẳng hạn như cạnh Dũng-Chi màu tím như hình 5a, thì chúng ta sẽ có một tam giác màu tím là An-Dũng-Chi.
Trường hợp ngược lại, nếu tam giác Dũng-Chi-Cường không có cạnh nào màu tím như hình 5b, thì chúng ta sẽ có một tam giác màu xanh Dũng-Chi-Cường.
Tóm lại, trong mọi trường hợp, Ta luôn tìm được một tam giác có ba cạnh màu tím hoặc cả ba cạnh màu xanh, và như vậy bài toán đã được chứng minh xong.
nguon VI OLET
