Lesson 2

Advanced Problems.

1. (20 points) Let \(S_{n} = \frac{1}{1}+ \frac{1}{2}+ \frac{1}{3}+ \dotsb + \frac{1}{n}\). Prove that \(S_{n}\not \in \mathbb{Z}\) for any \(n \ge 2\).
   Hint:

   Focus on the highest power of \(2\) that is less than or equal to \(n\).
2. (20 points, Dirichlet's approximation theorem, 1879) Prove that for any \(x \in \mathbb{R}\) and \(n \in \mathbb{Z}_{>0}\), there exists a rational number \(p/q\), such that \(1 \leq q \leq n\) and \[\left| x - \frac{p}{q}\right| \le \frac{1}{nq}.\]
   Hint:

   The inequality can be rewritten as \(|qx - p| \le \frac{1}{n}\). This implies that we need to find a multiple of \(x\), specifically \(qx\) (for \(1 \le q \le n\)), that is sufficiently close to an integer \(p\).

   Consider the fractional parts of the \(n+1\) numbers \(0, x, 2x, …, nx\). Utilize the Pigeonhole Principle to demonstrate that two of these fractional parts must be arbitrarily close to each other.

3. (20 points) Is it possible to cut this figure into two equal parts?

   

   Hint:

   It is possible (though challenging).
4. (20 points) Let \(\mathcal{F} \subseteq 2^{[n]}\) be a family of subsets of an \(n\)-element set satisfying the following two properties:
   • The size of each set in \(\mathcal{F}\) is odd.
   
   
   • The size of the intersection of any two distinct sets in \(\mathcal{F}\) is even.
   
   

   Find the maximum possible size of \(\mathcal{F}\).
5. (20 points) Let \(G\) be a bipartite graph with parts of size \(n\) that has a unique perfect matching. What is the maximum number of edges in \(G\)?
   Hint:

   The answer is \(\frac{n \cdot (n + 1)}{2}\).