Answer:
Take any algorithm if that algorithm solves this problem it can be represented as a ternary decision tree. Therefore each question has at most three answers.
There are ten possible verdicts, the height of such kind of tree should satisfy
ℎ >= ⌈log3(10)⌉ = 3
Hence no such algorithm can ask less than three questions in the worst case.
---
b)
Each and every internal node represents a question asking whether m belongs to one of three possible subset of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} or not
For example 0123|456|789 represented the questionDoes “m: belongs to {0, 1, 2, 3}, to {4, 5, 6}, or to {7, 8, 9}?"
Verdicts are placed in brackets "[ ]"
Explanation:
decision tree is attached below
