The book that I am currently studying has the following exercise.
Given is a set of $n$ coins of weights $0$ or $1$ and a scale to weight them. We would like to determine the weight of each coin by using the smallest amount of weightings possible.
I am asked to show using the pigeonhole principle that we need at least $n/\log_2{(n+1)}$ weightings.
The hint suggested that I define a determing sequence $S_1,\ldots,S_m$ to be a collections of subsets of $\{1,\ldots,n\}$ such that for any subset $T \subseteq \{1,\ldots,n\}$ the sequence $|T\cap S_1|,\ldots,|T \cap S_m|$ uniquely determines $T$ and deduce the claim from the fact that $|T \cap S_i|$ can have at most $n+1$ values.
Somehow I don't see how to go from here. How can I obtain the desired result from this point?
Let $T$ be the (unknown) set of heavy coins. Any weighing strategy must look as follows: At the $k$th step, you select a subset $S_k\subseteq \{1,\ldots,n\}$ (where the choice of $S_k$ may depend on the weighing results of previous rounds, but that does not matter) and the scale tells you the $k$th weighing result $w_k=|T\cap S_k|$, which is a number between $0$ and $|S_k|\le n$, inclusive. After a sequence of $m$ weighings, all you have is this sequence $w_1, \ldots, w_m$ (at most $(n+1)^m$ possibilities) and this must allow you to determine any of the candidates for $T$ (for which there are $2^n$ possibilities). Therefore we must have $(n+1)^m\ge 2^n$, i.e. $m\log_2(n+1)\ge n$.