Question

Let m be an integer in the set {0,1,2,3,4,5,6,7,8, 9}, and consider the following problem: determine m by asking 3-way questions, i.e. questions with at most 3 possible answers. For instance, one could ask which of 3 specific subsets m belongs to.
Give a decision tree argument showing that at least 3 such questions are necessary in worst case. In other words, prove that no correct algorithm can solve this problem by asking only 2 questions in worst case.

Answer 1

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