组合数学 (Spring 2013)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
Line 23: Line 23:
This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>.
This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>.


* Prove that the minimum above <math>m</math> gives the minimum number of weighing to determine the weights of <math>n</math> coins.
* Prove that the minimum <math>m</math> such that there exists a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> equals the minimum number of weighing to determine the weights of <math>n</math> coins.
* Use pigeonhole principle to show that <math>m\ge \frac{n}{\log_2(n+1)}</math>.
* Use pigeonhole principle to show that <math>m\ge \frac{n}{\log_2(n+1)}</math>.

Revision as of 10:35, 17 April 2013

Problem 1

Prove the following identity:

  • [math]\displaystyle{ \sum_{k=1}^n k{n\choose k}= n2^{n-1} }[/math].

(Hint: Use double counting.)

Problem 2

Show that among any group of [math]\displaystyle{ n }[/math] people, where [math]\displaystyle{ n\ge 2 }[/math], there are at least two people who know exactly the same number of people in the group (assuming that "knowing" is a symmetric relation).

Problem 3

Let [math]\displaystyle{ S }[/math] be a subset of [math]\displaystyle{ \{1,2,\ldots,2n\} }[/math] such that [math]\displaystyle{ |S|\gt n }[/math]. Show that there exist [math]\displaystyle{ a,b\in S }[/math] such that [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are coprime.

Problem 4

(Due to Karger)

Balls of 8 different colors are in 6 bins. There are 20 balls of each color. Prove that there must be a bin containing 2 pairs of balls from the two different colors of balls.

Problem 5

(Erdős-spencer 1974)

Let [math]\displaystyle{ n }[/math] coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (i.e. which coins are 0 and which are 1) with the minimal number of weighings.

This problem can be formalized as follows: A collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math] is called determining if an arbitrary subset [math]\displaystyle{ T\subseteq[n] }[/math] can be uniquely determined by the cardinalities [math]\displaystyle{ |S_i\cap T|, 1\le i\le m }[/math].

  • Prove that the minimum [math]\displaystyle{ m }[/math] such that there exists a determining collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math] equals the minimum number of weighing to determine the weights of [math]\displaystyle{ n }[/math] coins.
  • Use pigeonhole principle to show that [math]\displaystyle{ m\ge \frac{n}{\log_2(n+1)} }[/math].