组合数学 (Spring 2013)/Problem Set 2

From TCS Wiki
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
  • 每道题目的解答都要有完整的解题过程。中英文不限。
  • 这次作业只有一个星期的时间。

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 (like {red,red,blue,blue}).

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 (that is, to known 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 if there is a determining collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math], then there is a way to determine the weights of [math]\displaystyle{ n }[/math] coins with [math]\displaystyle{ m }[/math] weighings.
  • Use pigeonhole principle to show that if a collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math] is determining, then it must hold that [math]\displaystyle{ m\ge \frac{n}{\log_2(n+1)} }[/math].

(This gives a lower bound for the number of weighings required to determine the weights of [math]\displaystyle{ n }[/math] coins.)

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Spring_2013)/Problem_Set_2&oldid=5628"