subject

Advanced fake-coin problem There are n ⥠3 coins identical in appearance; either all are genuine or exactly one of them is fake. It is unknown whether the fake coin is lighter or heavier than the genuine one. You have a balance scale which you can compare any two sets of coins. That is, by tipping to the left, to the right, or staying even, the balance scale will tell whether the sets weigh the same or which of the sets is heavier than the other, but not by how much. The problem is to find whether all the coins are genuine and, if not, to find the fake coin and establish whether it is lighter or heavier than the genuine ones. a) Prove that any algorithm for this problem must make at least [log3(2n+1)ceiling weighings in the worst case.
b) Draw a decision tree for an algorithm that solves the problem for n = 3 coisn in two weighings.
c) Prove that there exists no algorithm that solves the problem for n = 4 coins in two weighings.

ansver
Answers: 1

Other questions on the subject: Computers and Technology

image
Computers and Technology, 23.06.2019 02:00, kelseybell5522
For a typical middle-income family, what is the estimated cost of raising a child to the age of 18? $145,500 $245,340 $304,340 $455,500
Answers: 1
image
Computers and Technology, 24.06.2019 06:30, titalili0204
Adrawing that places all lines parallel to the z axis at an angle from the horizon is 99 ! a. an oblique drawing b. a perspective drawing c. an auxiliary view d. a one-point perspective drawing
Answers: 2
image
Computers and Technology, 24.06.2019 14:30, SmartScholar4094
Two students are discussing electricity that has a frequency of 60 hz. student a says that this type of electricity is referred to as ac. student b says that in this type of electricity, the electrons flow in only one direction. which of the following statements is correct? a. only student a is correct b. only student b is correct c. both of the two students are correct d. neither of the two students is correct
Answers: 1
image
Computers and Technology, 24.06.2019 15:30, jhony70
What type of forensic evidence was recovered during the bomb set off at the new mexico facility on the video that was similar to the evidence obtained at the boston bombings and how did the evidence allow the researchers to connect other pieces of evidence to the same bomb?
Answers: 2
You know the right answer?
Advanced fake-coin problem There are n ⥠3 coins identical in appearance; either all are genuine or...

Questions in other subjects:

Konu
Mathematics, 13.04.2021 22:20
Konu
Mathematics, 13.04.2021 22:20
Konu
Mathematics, 13.04.2021 22:20
Konu
Chemistry, 13.04.2021 22:20