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 01:10, brooklynneramos9956
Problem 1 - hashing we would like to use initials to locate an individual. for instance, mel should locate the person mark e. lehr. note: this is all upper case. generate a hash function for the above using the numbers on your telephone. you know, each letter has a number associated with it, so examine your telephone keypad. generate 512 random 3 letter initials and take statistics on a linked list array size 512 to hold this information report how many have no elements, 1 element, 2 elements, does this agree with the hashing statistics distribution?
Answers: 1
image
Computers and Technology, 23.06.2019 19:00, jacobbecker99
Choose the correct citation for the case which established the "minimum contacts" test for a court's jurisdiction in a case. select one: a. brown v. board of education of topeka, 347 u. s. 483 (1954). b. international shoe co. v. washington, 326 u. s. 310 (1945) c. haynes v. gore, 531 u. s. 98 (2000). d. international shoe co. v. washington, 14 u. s. code 336.
Answers: 1
image
Computers and Technology, 24.06.2019 00:00, miguelturner
Which tool could be used to display only rows containing presidents who served two terms
Answers: 3
image
Computers and Technology, 24.06.2019 13:30, lorelaistudent
Does anybody know how to hack into a google account? i had important information on it and it is gone now and i need getting it back.
Answers: 1
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, 12.12.2020 21:50
Konu
Mathematics, 12.12.2020 21:50
Konu
Mathematics, 12.12.2020 21:50
Konu
Mathematics, 12.12.2020 21:50