Can someone check i done part (a) right?
for 3 weighings::
M={take all eight marbles}.
devide marbles into 2 sets of 4 marbles each.
WEIGH 1:: weigh the both sets and select the heavier set.
now the new selected set will contain 4 marbles,devide them into 2 sets of 2 marbles each.
WEIGH 2:: weight the both sets and select the heavier set.
now the new selected set will contain 2 marbles,devide them into 2 sets of 1 marbles each.
WEIGH 3:: weight the both sets and select the heavier marble.
Now the heavier marble is found.
Question 6
You have eight marbles and a two-pan balance. All the marbles weight 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.
Hint: To solve part (b), it might be helpful to consider first the problem with nine marbles.
for 3 weighings::
M={take all eight marbles}.
devide marbles into 2 sets of 4 marbles each.
WEIGH 1:: weigh the both sets and select the heavier set.
now the new selected set will contain 4 marbles,devide them into 2 sets of 2 marbles each.
WEIGH 2:: weight the both sets and select the heavier set.
now the new selected set will contain 2 marbles,devide them into 2 sets of 1 marbles each.
WEIGH 3:: weight the both sets and select the heavier marble.
Now the heavier marble is found.
Question 6
You have eight marbles and a two-pan balance. All the marbles weight 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.
Hint: To solve part (b), it might be helpful to consider first the problem with nine marbles.
Attachments
Last edited by a moderator: