Lesson 2

Advanced Problems.

1. (20 points) Prove that any \(K_{k+1}\)-free graph (with no clique of size \(k + 1\)) on \(n\) nodes has at most \(\left(1-\frac{1}{k}\right)\frac{n^2}{2}\) edges.
2. (20 points) On a circular road, there are several identical cars. The total amount of gasoline in their tanks is enough for one car to make a full circle. Prove that there exists a car that, starting its motion counter-clockwise and taking gasoline from the stationary cars along its path, can make a full circle.
3. (20 points) Let \(P(x)\) and \(Q(x)\) be two polynomials with natural coefficients. We say that \(P\) is less than \(Q\) if \(P(x) < Q(x)\) for all sufficiently large \(x\). Does there exist an infinite sequence of polynomials \(P_{1}, P_{2}, …\), in which each subsequent polynomial is less than the previous one?
4. (20 points) Prove that in any directed graph, there exists an independent set such that the distance from this set to any vertex not in the set is at most two.
   Hint:

   Induction on the number of nodes. Take an inclusion-wise maximal independent set.
5. (20 points) Prove that, for any \(n \in \mathbb{Z}_{\geq2}\): \[\sqrt{2 \cdot \sqrt{3 \cdot \ldots \cdot \sqrt{n-1 \cdot \sqrt{n}}}}< 3\]
   Hint:

   Fix \(n \in \mathbb{Z}_{\ge 2}\). Use backward induction to prove something for \[\sqrt{ k \cdot \sqrt{ (k + 1) \cdot \sqrt{  \ldots \sqrt{  n } } } }.\]
6. (20 points) Several lamps are illuminated on a display panel. There are also several buttons: pressing a button changes the state of the lamps to which it is connected. It is known that for any set of lamps, there exists a button connected to an odd number of lamps within that set. Prove that by pressing the buttons, it is possible to turn off all lamps.
7. (20 points) Positive integers \(a_{1}, a_{2}, \dotsc, a_{n}\) satisfy the condition \(a_{k} \leq k\), and their sum is even, equaling \(2S\). Prove that these numbers can be partitioned into two groups, with the sum of each group equaling \(S\).
   Hint:

   Consider using mathematical induction on the number of integers, \(k\). Strengthen the induction hypothesis to prove a stronger result.
8. (20 points) For \(a, b \in \mathbb{Z}_{>0}\), \(a^{2}+b^{2}=k(ab+1)\) where \(k \in \mathbb{Z}_{>0}\). Prove that \(k\) is a perfect square.
9. (20 points) Prove that, for any \(n \in \mathbb{Z}_{>0}\), the set \([2n]\) can be partitioned into pairs \[(a_{1}, b_{1}), \dotsc, (a_{n}, b_{n})\] such that \(a_{i}+b_{i}\) is prime, for all \(i \in [n]\).
   Hint:

   Use Bertrand's postulate.