Coin-weighting problem Let n coins of weights 0 and 1 be given. We are also given a scale with whic

Callum Dudley 2022-07-01 Answered
Coin-weighting problem
Let n coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. The information from previous weighting may be used. The object is to determine the weights of the coins with the minimal number of weightings. Formally, a collection S 1 , , S m subsets of { 1 , , n } is called determing if any T { 1 , , n } can be uniquely determined by the cardinalities | S i T | for 1 i m .. Let D(n) be the minimum m for which such a determing collection exists. Show that D ( n ) n log 2 ( n + 1 ) .
Let S 1 , , S m be an arbitrary determining collection. Also, assume that T be an arbitrary subset of { 1 , , n }. Then there are 2 n possibilities to choose T from { 1 , , n }. On the other hand, for each 1 i m, there are only n + 1 possible | S i T | because 0 | S i T | | S i | n. But now I don't know how to apply the pigeonhole principle. This principle says that: if a set A consisting of at least r s + 1 objects is partitioned into r classes, then some class receives at least s + 1 objects. Equivalently, if A = i = 1 r B i (disjoint union) and | B i | s for every 1 i r, then | A | r s. I can't use this principle in my answer. How can I introduce A and B i s here? I was wondering if someone could help me about it.
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

treccinair
Answered 2022-07-02 Author has 18 answers
Step 1
We see that a collection of m subsets S 1 , S 2 , , S m is determining if there exists a function f such that f ( | S 1 T | , | S 2 T | , , | S m T | ) = T for every T { 1 , 2 , , n }.
Step 2
The number of 'inputs' of f above is ( n + 1 ) m , because | S i T | has at most n + 1 possible values (ranging from 0 to n). On the other hand, notice that there are 2 n possible subsets of { 1 , 2 , , n }. Hence, f must have at least 2 n possible 'inputs'. Therefore, ( n + 1 ) m 2 n , which is equivalent to m n log 2 ( n + 1 ) .

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2022-09-04
I'm confused about how to solve big-oh notation problems using the definition and basic algebra. for example, a problem like this:
Prove that ( x sin x + x log ( 2 x + 4 ) + ( ( x 3 + 1 ) / ( x 2 + 1 ) ) is an element of big-oh(x log x).
hint:This will require both the algebraic properties of O and its formal definition.
I'm thinking I can separate it into 3 parts and show each part is big-oh using limits(though I'm not sure that counts as an algebraic property) and the definition (C,K)?
asked 2022-07-15
Discrete Math On Recurrence
1. Suppose that a geometric sequence starts with and satisfies the recurrence a n = r a n 1 for every positive integer n.
a) Show that a n = a 0 r
b) Find the 100th number in the sequence 3,6,12,24,48, … .
I know this is a another recurrence problem but not sure now to start with this one.
asked 2022-05-22
You have {a,b,c} as your character set. You need to create words having 10 characters that must be chosen from the character set. Out of all the possible arrangements, how many words have exactly 6 as?

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question