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

From TCS Wiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
imported>Etone
No edit summary
imported>Etone
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
*<font color="red" size=4>每道题目的解答都要有完整的解题过程。中英文不限。</font>
:
*<font color="red" size=4>这次作业只有一个星期的时间。</font>
== Problem 1==
== Problem 1==
Solve the following recurrences:
* <math>a_n=3a_{n-1}-2a_{n-2}</math>, given that <math>a_0=2</math> and <math>a_1=3</math>.
* <math>b_n=\frac{1}{2}(b_{n-1}+b_{n-2})</math>, given that <math>b_0=0</math> and <math>b_1=1</math>.
== Problem 2 ==
<math>n</math> persons are to be allocated to <math>q</math> distinct rooms. Find the number of ways that this can be done if only <math>m</math> of the <math>q</math> rooms have exactly <math>k</math> persons each, where <math>1\le m\le q</math> and <math>mk\le n</math>.
== Problem 3==
Prove the following identity:  
Prove the following identity:  
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.


(Hint: Use double counting.)
(Hint: Use double counting.)
== Problem 2 ==
Show that among any group of <math>n</math> people, where <math>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>S</math> be a subset of <math>\{1,2,\ldots,2n\}</math> such that <math>|S|>n</math>. Show that there exist <math>a,b\in S</math> such that <math>a</math> and <math>b</math> are coprime.


== Problem 4 ==
== Problem 4 ==
Show that among any group of <math>n</math> people, where <math>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).
(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 {<font color=red>red</font>,<font color=red>red</font>,<font color=blue>blue</font>,<font color=blue>blue</font>}).


== Problem 5 ==
== Problem 5 ==
Let <math>S</math> be a subset of <math>\{1,2,\ldots,2n\}</math> such that <math>|S|>n</math>. Show that there exist <math>a,b\in S</math> such that <math>a</math> and <math>b</math> are coprime.
(Erdős-Spencer 1974)
 
Let <math>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>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 if there is a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math>, then there is a way to determine the weights of <math>n</math> coins with <math>m</math> weighings.
* Use pigeonhole principle to show that if a collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is determining, then it must hold that <math>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>n</math> coins.)

Latest revision as of 22:44, 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 (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"