Đến nội dung

Hình ảnh

Từ một trò chơi IQ

thuật toán trò chơi IQ logic suy luận

  • Please log in to reply
Chưa có bài trả lời

#1
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Cách đây lâu rồi, tôi không nhớ nữa! Ngày đấy hình như mới khai sinh ra cái "kim từ điển" - một loại máy tra từ điển bỏ túi. Một cậu bạn của tôi được bố nó mua cho một cái nó mang khoe với tôi.
Phải nói là tôi bị cuốn hút luôn vào cái máy bé tẹo đó.
(Thời đó điện thoại di động còn chưa có, hoặc nếu có thì chỉ là những máy ít chức năng hoặc là cái gì đó quá xa lạ với tôi. Ông chú tôi có một cái máy nhắn tin được cơ quan cấp để tiện liên lạc khi cần mà tôi còn thấy quá thích thú với cái màn hình hiện thị được 2 dòng chữ, mỗi tin nhắn nhận được không quá 32 ký tự. Máy vi tính, tôi được học trong nhà trường thì chỉ biết đến MS-DOS, PASCAL, loanh quanh chỉ với các bài tập dạng đó, đến Windows 95 tôi còn chưa hiểu là gì ...)
Tìm đến mục "Trò chơi" của máy, tôi thấy có trò "Đoán Số" (thực ra tên gọi là gì tôi cũng không nhớ!)

Luật chơi như sau:
- Máy chọn trước một dãy gồm 4 chữ số đôi một khác nhau $(\overline{abcd};\;a,b,c,d\in\{0,1,...,9\})$
- Người chơi phải tìm ra dãy số này với $10$ lần đoán
- Sau mỗi lần đoán, giả sử ta đoán là $0123$ thì máy "trả lời" cho ta biết các thông tin dạng $xA,yB$
với
$xA$ là $x$ chữ số đúng được đặt đúng vị trí của đáp án
$yB$ là $y$ chữ số có trong đáp án nhưng sai vị trí.

Ví dụ nếu đáp án là $3178$ thì máy sẽ trả lời là $1A,1B$ (số 1 và số 3)

Đầu tiên, tôi chưa hiểu lắm nên đoán bừa, hết 10 lần rồi mà vẫn không tìm được đáp án.
Dần dần hiểu ra cách suy luận thì mất khoảng 6-7 lần đoán là ra
Tiếp tục chơi đi chơi lại nhiều lần, tôi nhận thấy nhiều nhất là chỉ sau 5 lần đưa ra dự đoán, đến lần thứ 6 là tôi đưa ra được đáp án chính xác! Chưa lần nào tôi phải dùng đến lần thứ 7. Phải chăng chỉ cần tối đa là 6 lần đoán?

Tôi bắt đầu đi tìm lời giải thích cho câu hỏi đó ...
Phải mất tới 2 tập vở viết chỉ để tôi thống kê và phân tích các trường hợp, nháp, v.v... nhưng cuối cùng cũng chẳng đi đến đâu!
Và thế là bài toán dần đi vào quên lãng ...

Gần $10$ năm sau (2005), tôi được học về máy tính nhiều hơn, đa dạng hơn, một lần nữa tôi trở lại với thắc mắc của bài toán này. Tôi đã dùng PASCAL và thuật toán vét cạn, viết một chương trình kiểm tra kết quả (tiếc là cho đến bây giờ tôi không còn giữ code). Kết quả sau 3h đồng hồ chương trình chạy (chút nữa thì tôi tưởng máy tính hỏng!) trả về cho tôi con số 7

Nản! Không biết tôi sai hay cái máy tính sai! (chương trình viết sai)
Cuối cùng thì tôi cũng thấy rằng tồn tại những lần chơi phải dùng đến lần đoán thứ 7 (xem ví dụ)
Bài viết đầu tiên mà tôi gia nhập diễn đàn VMF, tôi đã đưa thắc mắc của tôi lên, nhưng thời điểm đó bài viết của tôi nhanh chóng đi vào quên lãng...

Tự dưng bây giờ tôi lại nhớ đến nó!
Hy vọng có ai đó chứng minh bằng Toán học rằng số lần đoán tối ưu để có kết quả đúng là 7?

Lấy một ví dụ trò chơi này như sau:
Đáp án $3178$ (tôi chưa biết)
- lần 1 tôi đoán $0123$ máy trả kết quả là 1A1B
- lần 2 tôi đoán $4567$ máy trả kết quả là 0A1B
Suy luận: Tôi đã dùng hết 8 chữ số mới chắc chắn được có 3 chữ số có mặt như vậy trong {8,9} chắc chắn có 1 số có mặt trong đáp án. Giả sử tôi cho đó là 9, tôi lại cho rằng số 2 trong lần 1 là vị trí A còn số 3 là vị trí B
- lần 3 tôi đoán $7329$ máy trả kết quả là 0A2B
Suy luận: Như vậy thì 2 không phải là A, còn lại 0,1,4,5,6,8 có 2 số nữa của đáp án. Trong dự đoán 1 tôi lại tin rằng 3 là A, tôi chọn thêm 5 và 6 và tin vào số 9
- lần 4 tôi đoán $5693$ máy trả kết quả là 0A1B
Suy luận: So sánh lần 3 với lần 2 ta có {2,7} có 1 số của đáp án, loại được hai số 5 và 6; thêm nữa điều tôi tin tưởng 3 là A là sai. Như vậy theo lần 1 thì chỉ có 0 hoặc 1 là A, tôi lại tin rằng 0 là A
- lần 5 tôi đoán $0718$ máy trả kết quả là 1A2B
Suy luận: Nếu tin 0 là A, 1 là B thì do lần 1, 1 chỉ có thể đứng cuối, mà như vậy thì 2 và 3 hoàn toàn không có, theo lần 3 thì cả 7 và 9 đều có (Bốn chữ số ta chọn sẽ là 0,1,7,9) và như vậy 9 không nằm ở hàng đơn vị (do lần 3) không nằm ở hàng chục (do lần 4) suy ra 9 nằm hàng trăm, 7 nằm hàng chục vậy là sẽ không có mâu thuẫn gì.
- lần 6 tôi đoán $0971$ máy trả kết quả 1A1B (Vậy là vỡ mộng!)
Suy luận: So với lần 5 ta mất đi một số đúng đó là số 8, loại được số 9, theo lần 4 thì nhận được số 3, theo lần 1 thì {0,1,2} chỉ có 1, theo lần 3, lần 6 và lần 1 thì loại nốt được số 2, nhận được số 7, mà 0 không phải là A do đó theo lần 1 thì 1 hàng trăm là A, 3 là B, theo lần 6 thì 7 ở hàng chục là A, lại theo lần 5 thì 8 ở hàng đơn vị là A do đó số 3 còn mỗi vị trí là hàng nghìn
- lần 7 tất nhiên là $3178$

Có ai giải được bài toán này ?





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: thuật toán, trò chơi, IQ, logic, suy luận

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh