Đề bài: Cho phản chứng: giả sử 1 người có thể liên lạc với 100 người bất kỳ. Theo vòng lặp, chúng ta có thể kết bạn với tất cả mọi người trên thế giới không? Hãy chứng minh.

Trước hết, chúng ta cần hiểu rõ yêu cầu của bài toán. Bài toán yêu cầu chúng ta sử dụng phương pháp “chứng minh bằng phản chứng”. Điều này có nghĩa là chúng ta sẽ giả sử điều ngược lại với điều cần chứng minh là đúng, sau đó đi đến một mâu thuẫn, từ đó suy ra điều ban đầu phải đúng.

Bước 1: Phát biểu điều cần chứng minh và điều giả sử phản chứng.

Điều cần chứng minh: Không thể kết bạn với tất cả mọi người trên thế giới bằng cách liên lạc với 100 người mỗi lần.

Giả sử phản chứng: Giả sử chúng ta có thể kết bạn với tất cả mọi người trên thế giới bằng cách liên lạc với 100 người mỗi lần.

Bước 2: Xây dựng mô hình và lập luận.

Chúng ta hãy tưởng tượng một mạng lưới “kết bạn”. Mỗi người là một điểm trong mạng lưới, và nếu hai người là bạn, chúng ta có thể vẽ một đường nối giữa họ.

Theo giả sử phản chứng, mỗi lần chúng ta “liên lạc”, chúng ta có thể kết bạn với 100 người mới. Hãy xem xét điều này một cách cẩn thận.

Giả sử số dân trên thế giới là \(N\). Hiện tại, chúng ta là 1 người. Theo giả sử, chúng ta liên lạc với 100 người bất kỳ. Bây giờ chúng ta có thêm 100 người bạn. Tổng số người mà chúng ta có thể tiếp cận là \(1 + 100 = 101\).

Tiếp theo, từ 101 người này, chúng ta lại chọn 100 người bất kỳ để liên lạc. Tuy nhiên, ở đây có một vấn đề quan trọng: những người chúng ta liên lạc lần thứ hai có thể đã nằm trong số 100 người bạn đầu tiên của chúng ta.

Hãy xét một trường hợp đơn giản hơn. Giả sử số dân trên thế giới là 200 người. Bạn là người thứ 1.

Lượt 1: Bạn liên lạc với 100 người. Bây giờ bạn có 100 người bạn. Tổng cộng, bạn và bạn bè của bạn là \(1 + 100 = 101\) người.

Lượt 2: Theo giả sử, bạn có thể liên lạc với 100 người bất kỳ.

Trường hợp 1: Bạn chọn 100 người hoàn toàn mới, chưa từng liên lạc trước đó. Điều này là không thể vì tổng số người trên thế giới chỉ là 200, và bạn đã biết 100 người rồi.

Trường hợp 2: Trong 100 người bạn bè bạn chọn, có thể có những người bạn đã có trong 100 người bạn ban đầu. Giả sử bạn liên lạc với 100 người bạn bè của mình. Tối đa, bạn chỉ có thể mở rộng mạng lưới của mình thêm một số lượng người nhất định.

Điều mấu chốt ở đây là “vòng lặp”. Nếu bạn chỉ có thể liên lạc với 100 người bất kỳ, thì bạn không có gì đảm bảo rằng bạn sẽ luôn tiếp cận được những người chưa từng được liên lạc.

Hãy hình dung: Bạn có 1 người. Bạn kết bạn với 100 người. Bây giờ có 101 người.
Bạn chọn 100 người bất kỳ trong số 101 người này để “tiếp tục vòng lặp”. Nếu bạn chọn lại chính 100 người bạn ban đầu, bạn không có thêm người bạn mới nào. Nếu bạn chọn 99 người bạn cũ và 1 người mới, bạn chỉ có thêm 1 người bạn mới.

Để kết bạn với tất cả mọi người trên thế giới, bạn cần một phương pháp đảm bảo rằng mỗi lần liên lạc, bạn sẽ tiếp cận được ít nhất một người mà bạn chưa từng biết. Tuy nhiên, với quy tắc “liên lạc với 100 người bất kỳ”, bạn có thể rơi vào tình huống liên tục “lặp lại” với những người đã biết.

Bước 3: Tìm ra mâu thuẫn.

Giả sử chúng ta có thể kết bạn với tất cả mọi người trên thế giới bằng cách liên lạc với 100 người bất kỳ. Điều này có nghĩa là, dù chúng ta có bao nhiêu người bạn đi chăng nữa, chúng ta luôn có thể tìm được 100 người để liên lạc và mở rộng mạng lưới của mình cho đến khi chạm đến tất cả mọi người.

Tuy nhiên, khi chúng ta có một số lượng lớn người quen, ví dụ có \(k\) người bạn, và chúng ta liên lạc với 100 người bất kỳ trong tập hợp \(k+1\) người (chúng ta cộng với chính mình), thì có khả năng rất cao là chúng ta sẽ liên lạc lại với những người đã là bạn của mình.

Ví dụ, nếu số dân là \(N\), và bạn đã kết bạn được với \(N-1\) người. Bây giờ bạn có \(N\) người trong mạng lưới của mình. Để kết bạn với người còn lại, bạn cần liên lạc với 100 người bất kỳ. Nhưng nếu tất cả \(N\) người bạn này đều là người quen của bạn, bạn không thể chọn 100 người để “mở rộng” mạng lưới sang người thứ \(N+1\). Nhưng trên thực tế, bạn chỉ có \(N\) người trên toàn thế giới.

Mâu thuẫn nằm ở chỗ: phương pháp “liên lạc với 100 người bất kỳ” không đảm bảo sự tiến triển liên tục đến những người mới. Có thể bạn sẽ mãi mãi “quanh quẩn” trong một nhóm nhỏ hơn số dân thế giới.

Hãy tưởng tượng một cách khác: chúng ta có một tập hợp các đỉnh là người dân, và các cạnh là mối quan hệ “quen biết”. Bạn bắt đầu từ một đỉnh. Mỗi lần, bạn có thể thêm 100 đỉnh mới vào tập hợp các đỉnh đã “tiếp cận”. Tuy nhiên, nếu bạn chọn 100 đỉnh đã có trong tập hợp, bạn không mở rộng được tập hợp.

Nếu giả sử phản chứng là đúng, tức là ta có thể kết bạn với tất cả mọi người. Điều này ngụ ý rằng, dù số người bạn đã có là bao nhiêu, ta luôn có thể tìm được 100 người khác để liên lạc và “kết nạp” họ vào mạng lưới của mình cho đến khi hết. Nhưng điều này không thể xảy ra, bởi vì một khi bạn đã biết gần hết mọi người, việc chọn “100 người bất kỳ” có thể chỉ là chọn lại những người đã quen.

Bước 4: Kết luận.

Vì giả sử phản chứng dẫn đến mâu thuẫn (không thể đảm bảo luôn tiếp cận được người mới thông qua việc chọn 100 người bất kỳ, đặc biệt khi mạng lưới đã mở rộng đáng kể), nên giả sử phản chứng là sai.

Do đó, điều ngược lại phải đúng.

Kết luận: Không, chúng ta không thể kết bạn với tất cả mọi người trên thế giới chỉ bằng cách liên lạc với 100 người bất kỳ theo vòng lặp.

Các em thấy đấy, phương pháp phản chứng giúp chúng ta nhìn vấn đề từ một góc độ khác và tìm ra những điểm yếu trong giả định ban đầu. Bài tập này rèn luyện cho chúng ta khả năng tư duy logic và suy luận chặt chẽ.