Problem:
You have eight marbles and a two-pan balance. All the marbles weigh the same, except for one, which is heavier than all the others. The marbles are otherwise indistinguishable. You may make no assumptions about how much heavier the heavy marble is.
(a) Describe an algorithm that finds the heavy marble in three weighings.
(b) Describe an algorithm that finds the heavy marble in two weighings.
Hints: Apply the binary search-based strategy.
To solve part (b), it might be helpful to consider first the problem with nine marbles.
Additional Information:
The question belongs to Computer Science and it discusses about two algorithms on marbles.
Total Word Limit: 251 Words