Lesson 1

Basic Problems.

1. (5 points) Are the sets \((0,1)\) and \(\mathbb{Q}\) isomorphic as linearly ordered sets, with the order induced by the usual comparison of numbers?
2. (10 points) A line of new recruits is standing in front of a sergeant. The sergeant commands: “Left face!” Due to inexperience, some of the soldiers turn left, while others turn right. After this, every second, a pair of adjacent soldiers who are facing each other simultaneously turn 180 degrees. Prove that this process of turning must eventually stop.
   Hint:

   Play around with a toy example like the following one: \[\text{LLLRLLLRRLRRL}\to \text{LLLRLLLRLRRRL}\] Intuitively, \(\texttt{L}\)'s move to the left whereas \(\texttt{R}\)'s move to the right. Formalize this intuitions.
3. (10 points) The universe is the set of all six-sided dice with digits from 1 to 9 on the sides. We say that \(A \succ B\) if the probability that the outcome of \(A\) is larger than the outcome of \(B\) is larger than \(1/2\). Is this a valid ordering?
   Hint:

   Try to find a counterexample to transitivity.
4. (15 points) What is the maximum size of an antichain in the set of (positive) divisors of the number \(2016\) with the partial order “\(x\) is a divisor of \(y\)”?
   Hint:

   Note that it is not sufficient to draw the Hasse diagram of this poset and to find the largest size of its layers: there exist antichains that contain elements from different layers.
5. (15 points) Let \(P(x)\) and \(Q(x)\) be two polynomials with non-negative integer coefficients. We say that \(P\) is less than \(Q\), denoted \(P < Q\), if \(P(x) < Q(x)\) for all sufficiently large \(x\). Does there exist an infinite sequence of polynomials \(P_{1}, P_{2}, \dotsb\) such that \(P_{k+1}< P_{k}\) for all \(k \ge 1\)?
   Hint:

   The comparison of polynomials for large \(x\) is determined first by their degrees, and then by their coefficients, starting from the leading one. Consider the sequence of degrees of the polynomials \(P_{k}\).
6. (15 points) The Erdős–Szekeres theorem states that for any \(r, s \ge 1\), any sequence of \((r - 1)(s - 1) + 1\) distinct real numbers has either a monotonically increasing subsequence of length \(r\) or a monotonically decreasing subsequence of length \(s\). Prove it using Dilworth's or Mirsky's theorem.
   Hint:

   Consider the elements of the sequence, denoted by \(a_{1}, a_{2}, …, a_{n}\), as a partially ordered set (poset). Define a suitable partial order relation based on both the indices and the values of the elements. Then, determine what chains and antichains in this poset correspond to in terms of subsequences.
7. (15 points) Prove that the orders on the sets \[A = \{x \in \mathbb{Q}\colon 0 < x < 1\} \quad \text{and}\quad B = \{x \in \mathbb{Q}\colon 0 < x < \sqrt{2}\},\] given by the usual comparison of numbers, are isomorphic.
8. (15 points) Let \(I_{1}, \dotsc, I_{10}\) be different intervals on a line such that there are no four intervals that are pairwise disjoint. Prove that there exist four intervals that have a common point.
9. (15 points) Are the lexicographic orders on \(\mathbb{Q}\times \mathbb{Z}\) and \(\mathbb{Q}\times \mathbb{Z}_{>0}\) isomorphic?