Chủ đề này có 2 trả lời

[hxthanh]

E. Galois và supermember cùng nhau chơi trò chơi Đoán số như sau:

supermember sẽ nghĩ ra trong đầu một dãy 4 chữ số $abcd,\quad a,b,c,d$ đôi một khác nhau (trong tập $E=\{0,1,...,9\}$) đem đố E. Galois.
Mỗi lượt đoán của mình E. Galois sẽ đưa ra một đáp án chẳng hạn $a_1b_1c_1d_1$.
So sánh mỗi dự đoán của E. Galois với đáp án của mình, supermember sẽ cung cấp cho E. Galois một thông tin bằng một số điểm như sau:
$\bullet\;{}$ Cộng $10$ điểm cho mỗi chữ số đúng nằm đúng vị trí, chẳng hạn khi $b_1=b$
$\bullet\;{}$ Cộng $1$ điểm cho mỗi chữ số có mặt trong đáp án nhưng sai vị trí, chẳng hạn khi $d_1=a$

Hỏi: E. Galois phải dùng ít nhất bao nhiêu lượt đoán để chắc chắn tìm được dãy 4 chữ số của supermember ?

Gợi ý

Không mất tổng quát, giả sử dãy số của supermember là $0123$
- Xét trường hợp tưởng chừng "nhanh nhất" mà "chuối" nhất E. Galois đoán lần $1$ là $012x_1$ với $x_1\neq 3$
- Như vậy điểm của lần $1$ E. Galois nhận được là $30$.
- Các lần tiếp theo E. Galois tiếp tục đoán là $012x_i$ với $x_i\neq 3$ (đều nhận được số điểm là $30$)
- Các số $x_i\neq 3$ chỉ còn lại là $4,5,6,7,8,9$
- Như vậy "chuối" lắm thì sau $6$ lần thất bại, lần đoán thứ $7$ E. Galois sẽ phải đoán đúng.

Bạn sẽ phải chứng minh rằng $7$ là số lần cần và đủ để chắc chắc tìm được đáp án. Thực tế khi chơi trò chơi này với máy tính, thường thì nhiều lắm cũng chỉ 6 lần là máy tìm được đáp án.

______________________________________
Cùng chơi với máy  DoanSo.rar   7K   668 Số lần tải

[hxthanh]

Sự may mắn có cơ sở

[ilovelife]

Sự may mắn có cơ sở

aoqua.png

Em nghĩ có  thể giải bài này bằng decision tree + pruning search. (Xin lỗi em hiện tại hơi bận nên chưa nên không có ngay "sản phẩm")

 

Chứng minh cần tối đa 7 lần: thử tất cả các trường hợp ? (em nghĩ nó chưa phải cách hay, tốn thời gian)