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

• 每道题目的解答都要有完整的解题过程。中英文不限。
• 这次作业只有一个星期的时间。

## Problem 1

Prove the following identity:

• ${\displaystyle \sum _{k=1}^{n}k{n \choose k}=n2^{n-1}}$.

(Hint: Use double counting.)

## Problem 2

Show that among any group of ${\displaystyle n}$ people, where ${\displaystyle n\geq 2}$, 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 ${\displaystyle S}$ be a subset of ${\displaystyle \{1,2,\ldots ,2n\}}$ such that ${\displaystyle |S|>n}$. Show that there exist ${\displaystyle a,b\in S}$ such that ${\displaystyle a}$ and ${\displaystyle b}$ 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 ${\displaystyle 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. 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 ${\displaystyle S_{1},S_{1},\ldots ,S_{m}\subseteq [n]}$ is called determining if an arbitrary subset ${\displaystyle T\subseteq [n]}$ can be uniquely determined by the cardinalities ${\displaystyle |S_{i}\cap T|,1\leq i\leq m}$.

• Prove that if there is a determining collection ${\displaystyle S_{1},S_{1},\ldots ,S_{m}\subseteq [n]}$, then there is a way to determine the weights of ${\displaystyle n}$ coins with ${\displaystyle m}$ weighings.
• Use pigeonhole principle to show that if a collection ${\displaystyle S_{1},S_{1},\ldots ,S_{m}\subseteq [n]}$ is determining, then it must hold that ${\displaystyle m\geq {\frac {n}{\log _{2}(n+1)}}}$.

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