Khi đoán một số từ 1 đến 100 và được báo "cao hơn" hay "thấp hơn" sau mỗi lần, cách đoán chia đôi khoảng còn lại luôn tìm ra số trong tối đa 7 lần, và không có cách nào chắc chắn tìm ra trong 6 lần. Lý do: mỗi lần đoán chia khoảng còn lại làm đôi, và phải chia đôi 7 lần thì 100 khả năng mới thu về một.
Đó là phần của người đoán. Phần đối kháng nằm ở người giấu: nếu người đoán luôn bắt đầu bằng 50 rồi 25 hay 75, có 37 số buộc họ phải đoán đủ 7 lần, và người giấu tinh ý sẽ chọn trong nhóm đó. Phần dưới đi qua lời giải từng bước, phép đếm chứng minh 7 là cần và đủ, cách người giấu chọn số, cách người đoán đáp lại, và các biến thể như 1 đến 1000.
Luật và cái sai hay gặp của người mới
Người giấu nghĩ một số nguyên từ 1 đến 100, viết lên mảnh giấy úp xuống để không đổi ý. Người đoán nói một số; người giấu trả lời "đúng", "số của mình cao hơn" hoặc "số của mình thấp hơn". Mục tiêu của người đoán là tìm ra số trong ít lần nhất; mục tiêu của người giấu là khiến người đoán tốn nhiều lần nhất.
Người mới thường đoán theo cảm giác: 30, rồi 70, rồi 45. Mỗi lần đoán như vậy loại được một phần khoảng còn lại, nhưng phần loại được có khi lớn có khi nhỏ. Nếu đoán 30 mà số thật lớn hơn, chỉ loại được 30 số và còn 70 số. Trường hợp xấu nhất mới là thứ đáng lo, vì người giấu chọn số chứ không phải số tự rơi vào.
Cái sai thứ hai là quên khoảng hiện tại. Sau bốn năm lần đoán, nhiều người lẫn lộn giữa "thấp hơn 62" và "cao hơn 58", đoán lại một số đã bị loại. Hãy luôn nói thành lời hoặc ghi ra: số nằm từ đâu đến đâu.
Giữ hai điều này trong đầu: tính cho trường hợp xấu nhất và luôn biết khoảng còn lại, mọi phần sau sẽ dễ theo.
Lời giải chia đôi, đi từng bước với số 2
Quy ước: mỗi lần đoán số ở giữa khoảng còn lại; nếu khoảng có số phần tử chẵn, lấy số giữa bên trái (làm tròn xuống). Thử với số người giấu là 2 — một trong những số tốn lượt nhất.
- Khoảng 1–100. Giữa là (1 + 100) / 2 = 50,5, làm tròn xuống 50. Đoán 50, được báo thấp hơn. Còn 1–49.
- Khoảng 1–49. Giữa là 25. Đoán 25, thấp hơn. Còn 1–24.
- Khoảng 1–24. Giữa là 12,5, lấy 12. Đoán 12, thấp hơn. Còn 1–11.
- Khoảng 1–11. Giữa là 6. Đoán 6, thấp hơn. Còn 1–5.
- Khoảng 1–5. Giữa là 3. Đoán 3, thấp hơn. Còn 1–2.
- Khoảng 1–2. Giữa là 1,5, lấy 1. Đoán 1, cao hơn. Còn đúng số 2.
- Đoán 2 — trúng ở lần thứ 7.
Kiểm phía trên với số 100: đoán 50 (cao hơn, còn 51–100), 75 (còn 76–100), 88 (còn 89–100), 94 (còn 95–100), 97 (còn 98–100), 99 (còn 100), rồi 100 — cũng 7 lần. Mỗi lần đoán, khoảng còn lại không quá nửa khoảng cũ: 100, 50, 25, 12, 6, 3, 1. Sau 6 lần đoán sai thì chỉ còn một số, lần thứ 7 chắc chắn trúng.
Vì sao 6 lần không đủ: đếm số tìm được theo từng lần
Nghĩ ngược lại: với cách đoán bất kỳ, lần đoán thứ nhất chỉ trúng được 1 số. Sau lần một, câu trả lời "cao" hay "thấp" chia ra hai nhánh, nên lần hai trúng được tối đa 2 số khác nhau. Lần ba tối đa 4, cứ thế gấp đôi.
| Lần đoán | Số trúng được tối đa ở lần này | Cộng dồn tối đa | Thực tế với cách chia đôi 1–100 |
|---|---|---|---|
| 1 | 1 | 1 | 1 số (50) |
| 2 | 2 | 3 | 2 số (25, 75) |
| 3 | 4 | 7 | 4 số |
| 4 | 8 | 15 | 8 số |
| 5 | 16 | 31 | 16 số |
| 6 | 32 | 63 | 32 số |
| 7 | 64 | 127 | 37 số còn lại |
Sau 6 lần, dù khéo cách nào, nhiều nhất chỉ phân biệt được 63 số — ít hơn 100. Vậy với 100 số, luôn có số buộc phải tới lần thứ 7. Và cách chia đôi đạt đúng giới hạn đó: 1 + 2 + 4 + 8 + 16 + 32 = 63 số trúng trong 6 lần đầu, 100 − 63 = 37 số còn lại trúng ở lần thứ 7.
Cũng từ bảng này tính được số lần đoán trung bình nếu số giấu được chọn hoàn toàn ngẫu nhiên: (1×1 + 2×2 + 3×4 + 4×8 + 5×16 + 6×32 + 7×37) / 100 = (1 + 4 + 12 + 32 + 80 + 192 + 259) / 100 = 580 / 100 = 5,8 lần.
Người giấu nên chọn số nào
Tránh các số người đoán hay đi qua. Nếu người đoán dùng cách chia đôi quen thuộc, 50 trúng ngay lần đầu, 25 và 75 trúng lần hai. Những số "tròn" như 10, 20, 50, 100 cũng hay được đoán thử. Chọn chúng là tự rút ngắn ván.
Chọn trong nhóm 37 số tốn 7 lần. Với quy ước làm tròn xuống như trên, các số như 2, 5, 100 và nhiều số nằm ngay sát một điểm chia đều thuộc nhóm phải đoán đủ 7 lần. Không cần nhớ hết, chỉ cần tự chạy thử cách chia đôi trong đầu với số mình định chọn.
Nhưng đừng quá bám một kiểu. Nếu bạn giấu số 2 mấy ván liền, người đoán sẽ nhận ra và đoán 2 ngay. Người giấu cũng cần khó đoán như người ra búa kéo bao: chọn ngẫu nhiên trong nhóm số tốn lượt, mỗi ván một chỗ khác.
Không được đổi số giữa chừng. Viết số ra giấy và úp xuống trước khi bắt đầu. Đổi số giữa ván cho khớp với câu trả lời là gian lận. Thật ra, kể cả người giấu gian lận như vậy cũng không kéo được quá 7 lần với người đoán theo cách chia đôi, vì cách đó đúng với mọi số.
Người đoán đáp lại người giấu tinh ý
Đổi cách làm tròn. Nếu người giấu biết bạn luôn làm tròn xuống và chọn số nằm ở góc tốn lượt nhất, bạn đổi sang làm tròn lên hoặc lấy ngẫu nhiên một trong hai số giữa. Số lần đoán tối đa vẫn là 7, nhưng tập 37 số tốn lượt đổi chỗ, người giấu không nhắm được nữa.
Đừng bỏ cách chia đôi để đoán theo cảm giác. Có người cho rằng người giấu hay chọn số có số 7 hoặc số lẻ, rồi đoán thẳng vào đó. Thỉnh thoảng trúng sớm, nhưng khi sai thì khoảng còn lại lớn, có khi tốn 9 hay 10 lần. Chia đôi giữ trường hợp xấu nhất ở 7 lần.
Kết hợp có kiểm soát. Nếu thật sự thấy người giấu thiên về một vùng, bạn có thể đặt điểm chia lệch về vùng đó một chút, miễn mỗi nhánh còn lại vẫn không quá 63 số ở lần đầu. Như vậy vẫn bảo đảm 7 lần trong trường hợp xấu nhất mà có cơ hội trúng sớm hơn.
Câu tự hỏi trước mỗi lần đoán. Khoảng còn lại có bao nhiêu số, và sau lần đoán này, nhánh lớn hơn còn bao nhiêu? Nếu nhánh lớn còn quá nửa, bạn đang đoán phí.
Các biến thể và số lần cần
Cách tính chung: tìm số lần nhỏ nhất sao cho 2 nhân với chính nó bấy nhiêu lần, trừ 1, không nhỏ hơn số khả năng. Bảng dưới tính sẵn cho các khoảng hay dùng.
| Khoảng số | Số khả năng | Lần cần trong trường hợp xấu nhất | Vì sao |
|---|---|---|---|
| 1 đến 10 | 10 | 4 | 3 lần chỉ phân biệt 7 số, 4 lần được 15 |
| 1 đến 50 | 50 | 6 | 5 lần được 31, 6 lần được 63 |
| 1 đến 100 | 100 | 7 | 6 lần được 63, 7 lần được 127 |
| 1 đến 500 | 500 | 9 | 8 lần được 255, 9 lần được 511 |
| 1 đến 1000 | 1000 | 10 | 9 lần được 511, 10 lần được 1023 |
Biến thể "câu hỏi có hay không" cũng theo đúng bảng này: thay vì đoán một số, người hỏi đặt câu như "số đó có lớn hơn 50 không?". Khác ở chỗ câu hỏi có hay không không bao giờ trúng ngay, nên cần 7 câu để thu 100 số về một số rồi mới nói ra đáp án. Với trẻ nhỏ, nên bắt đầu từ khoảng 1 đến 10 hoặc 1 đến 20 để các em tự thấy cách chia đôi.
Những nhầm lẫn hay gặp khi đấu đoán số
Nhầm 1: lấy số trung bình cảm tính thay vì số giữa khoảng. Khoảng còn lại là 51–100 mà đoán 70 thì nhánh dưới còn 19 số, nhánh trên còn 30 số. Số giữa đúng là 75: hai nhánh còn 24 và 25 số. Mỗi lần lệch như vậy cộng dồn lại có thể làm bạn tốn thêm một lần.
Nhầm 2: quên rằng số đã đoán cũng bị loại. Đoán 50 và được báo thấp hơn thì khoảng mới là 1–49, không phải 1–50. Bỏ sót chi tiết này khiến khoảng to hơn thực tế một số, và ở những bước cuối, một số dư có thể là thêm một lượt.
Nhầm 3: tin rằng người giấu hay chọn số đặc biệt. Có người tin người giấu thích số 7, số 37 hay số có hai chữ số giống nhau. Có thể đúng với vài người quen, nhưng đem thành quy tắc với người lạ thì đổi lấy rủi ro tốn quá 7 lần.
Nhầm 4: nghĩ người giấu không làm được gì. Người giấu không kéo được quá 7 lần, nhưng chọn số khôn thì luôn kéo được đủ 7 lần thay vì để người đoán trúng ở lần 3 hay 4. Trong một cuộc đấu nhiều ván đổi vai, đó là khác biệt quyết định.
Mang cách chia đôi ra ngoài đời
Cách nghĩ của câu đố này dùng được mỗi khi bạn phải tìm một chỗ hỏng trong một dãy dài mà chỉ hỏi được "trước hay sau". Một dây đèn trang trí ba mươi bóng bị tắt cả chuỗi vì một bóng hỏng: thay vì thử từng bóng, kiểm ở giữa dây trước, rồi kiểm giữa nửa hỏng. Năm lần kiểm là thu về một bóng, vì 2 nhân lên năm lần là 32, đủ phủ 30 bóng.
Một sổ thu chi ba mươi ngày bị lệch tiền cuối tháng cũng vậy: đối chiếu số dư ngày 15, biết lệch xảy ra trước hay sau, rồi đối chiếu ngày giữa nửa đó. Thay vì soát ba mươi ngày, bạn chỉ soát năm sáu chỗ.
Điều kiện để chia đôi có ích là mỗi lần kiểm cho câu trả lời rõ ràng về phía. Khi câu trả lời mơ hồ, như "có vẻ ở đâu đó phía trên", hãy tìm cách đặt câu hỏi sắc hơn trước khi chia tiếp.
Câu hỏi thường gặp
Đoán số từ 1 đến 100 thì chắc chắn trúng trong mấy lần?
Tối đa 7 lần nếu mỗi lần đoán số ở giữa khoảng còn lại. Không có cách nào bảo đảm trúng trong 6 lần, vì 6 lần chỉ phân biệt được nhiều nhất 63 số, ít hơn 100.
Đoán số từ 1 đến 1000 thì cần bao nhiêu lần?
Cần tối đa 10 lần. Chín lần chỉ phân biệt được 511 số, còn mười lần được 1023 số, đủ phủ 1000. Mỗi lần vẫn đoán số ở giữa khoảng còn lại như với khoảng 1 đến 100.
Người giấu chọn số nào thì người đoán tốn nhiều lần nhất?
Phụ thuộc cách người đoán chia khoảng. Với cách bắt đầu từ 50 và làm tròn xuống, có 37 số tốn đủ 7 lần, chẳng hạn 2, 5 và 100. Nhưng nếu người đoán đổi cách làm tròn thì nhóm số này đổi theo.
Đoán theo cảm giác có khi nào tốt hơn chia đôi không?
Có thể trúng sớm hơn trong vài ván, nhưng khi sai thì khoảng còn lại lớn và có thể tốn nhiều hơn 7 lần. Chia đôi là cách duy nhất giữ trường hợp xấu nhất ở 7 lần, nên là cách an toàn khi đấu với người giấu tinh ý.
Câu đố đoán số giúp trẻ học được gì?
Trẻ học cách loại trừ có hệ thống, giữ khoảng còn lại trong đầu và hiểu rằng câu hỏi tốt là câu hỏi chia đều khả năng. Nên cho trẻ đổi vai giấu và đoán, không chấm điểm, chỉ hỏi các em đã đoán bằng cách nào.
Đoán số cao thấp liên quan gì đến tìm kiếm nhị phân?
Cách đoán chia đôi chính là tìm kiếm nhị phân: mỗi bước so sánh với phần tử giữa rồi bỏ đi một nửa. Đây cũng là cách người ta tra một từ trong cuốn từ điển giấy, mở giữa cuốn rồi lật về nửa có chữ cái cần tìm.