Obvious.

This is again obvious. There must be two numbers which are only \(1\) apart, and hence relatively prime.

Write every number \(a \in A\) in the form \(a = 2^k m\), where \(m\) is an odd number between \(1\) and \(2n - 1\). Since there are \(n + 1\) numbers in \(A\), but only \(n\) different odd parts, there must be two numbers in \(A\) with the same odd part. Hence one is a multiple of the other.

This time the application of the pigeon-hole principle is not immediate. Associate to each \(a_i\) the number \(t_i\), which is the length of a longest increasing subsequence starting at \(a_i\). If \(t_i \geq m+1\) for some \(i\), then we have an increasing subsequence of length \(m+1\). Suppose then that \(t_i \leq m\) for all \(i\). The function \(f : a_i \mapsto t_i\) mapping \(\{ a_1, \dots , a_{mn+1}\} \) to \(\{ 1, \dots , m\} \) tells us by (1) that there is some \(s \in \{ 1, \dots , m\} \) such that \(f(a_i) = s\) for \(\frac{mn}{m} + 1 = n + 1\) numbers \(a_i\). Let \(a_{j_1}, a_{j_2}, \dots , a_{j_{n+1}}\) \((j_1 {\lt} \cdots {\lt} j_{n+1})\) be these numbers. Now look at two consecutive numbers \(a_{j_i}, a_{j_{i+1}}\). If \(a_{j_i} {\lt} a_{j_{i+1}}\), then we would obtain an increasing subsequence of length \(s\) starting at \(a_{j_{i+1}}\), and consequently an increasing subsequence of length \(s+1\) starting at \(a_{j_i}\), which cannot be since \(f(a_{j_i}) = s\). We thus obtain a decreasing subsequence \(a_{j_1} {\gt} a_{j_2} {\gt} \cdots {\gt} a_{j_{n+1}}\) of length \(n+1\).

For the proof we set \(N = \{ 0, 1, \dots , n\} \) and \(R = \{ 0, 1, \dots , n-1\} \). Consider the map \(f : N \to R\), where \(f(m)\) is the remainder of \(a_1 + \cdots + a_m\) upon division by \(n\). Since \(|N| = n+1 {\gt} n = |R|\), it follows that there are two sums \(a_1 + \cdots + a_k, a_1 + \cdots + a_{\ell }\) \((k {\lt} \ell )\) with the same remainder, where the first sum may be the empty sum denoted by \(0\). It follows that

has remainder \(0\) — end of proof.

Again, there is nothing to prove. The first sum classifies the pairs in \(S\) according to the first entry, while the second sum classifies the same pairs according to the second entry.

Consider the matrix \(A\) (as above) for the integers \(1\) up to \(n\). Counting by columns we get \(\sum _{j=1}^{n} t(j)\). How many \(1\)’s are in row \(i\)? Easy enough, the \(1\)’s correspond to the multiples of \(i\): \(1 \cdot i, 2 \cdot i, \dots \), and the last multiple not exceeding \(n\) is \(\lfloor n/i \rfloor \cdot i\). Hence we obtain

where the error in each summand, when passing from \(\lfloor n/i \rfloor \) to \(n/i\), is less than \(1\). Together with the standard estimates \(\log n {\lt} H_n {\lt} \log n + 1\) this gives \(\log n - 1 {\lt} \bar{t}(n) \leq H_n {\lt} \log n + 1\).

Thus we have proved the remarkable result that, while \(t(n)\) is totally erratic, the average \(\bar{t}(n)\) behaves beautifully: It differs from \(\log n\) by less than \(1\).

For the proof consider \(S \subseteq V \times E\), where \(S\) is the set of pairs \((v, e)\) such that \(v \in V\) is an end-vertex of \(e \in E\). Counting \(S\) in two ways gives on the one hand \(\sum _{v \in V} d(v)\), since every vertex contributes \(d(v)\) to the count, and on the other hand \(2|E|\), since every edge has two ends.

The proof follows from the chain of inequalities above: the key combinatorial step \(\sum \binom {d(u)}{2} \leq \binom {n}{2}\) is established by double counting (Theorem 28.10), and the final bound follows by Cauchy–Schwarz and the quadratic formula.

Each pair \((v, \{ u, w\} )\) with \(u, w \in N(v)\) maps to \(\{ u, w\} \). The \(C_4\)-free condition ensures this map is injective on the second component: if both \(v_1\) and \(v_2\) are common neighbors of \(\{ u, w\} \) with \(v_1 \neq v_2\), then \(v_1\)-\(u\)-\(v_2\)-\(w\) forms a \(4\)-cycle, a contradiction.

We will prove a stronger statement: The number of tricolored triangles is not only nonzero, it is always odd.

Consider the dual graph to the triangulation, but don’t take all its edges — only those which cross an edge that has endvertices with the (different) colors \(1\) and \(2\). Thus we get a “partial dual graph” which has degree \(1\) at all vertices that correspond to tricolored triangles, degree \(2\) for all triangles in which the two colors \(1\) and \(2\) appear, and degree \(0\) for triangles that do not have both colors \(1\) and \(2\). Thus only the tricolored triangles correspond to vertices of odd degree (of degree \(1\)).

However, the vertex of the dual graph which corresponds to the outside of the triangulation has odd degree: in fact, along the big edge from \(V_1\) to \(V_2\), there is an odd number of changes between \(1\) and \(2\). Thus an odd number of edges of the partial dual graph crosses this big edge, while the other big edges cannot have both \(1\) and \(2\) occurring as colors.

Now since the number of odd-degree vertices in any finite graph is even (by equation (4)), we find that the number of small triangles with three different colors (corresponding to odd inside vertices of our dual graph) is odd.

Let \(\Delta \) be the triangle in \(\mathbb {R}^3\) with vertices \(e_1 = (1,0,0)\), \(e_2 = (0,1,0)\), and \(e_3 = (0,0,1)\). It suffices to prove that every continuous map \(f : \Delta \to \Delta \) has a fixed point, since \(\Delta \) is homeomorphic to \(B^2\).

We use \(\delta (T)\) to denote the maximal length of an edge in a triangulation \(T\). One can easily construct an infinite sequence of triangulations \(T_1, T_2, \dots \) of \(\Delta \) such that the sequence of maximal diameters \(\delta (T_k)\) converges to \(0\) (for example by iterated barycentric subdivision).

For each of these triangulations, we define a \(3\)-coloring of their vertices \(v\) by setting \(\lambda (v) := \min \{ i : f(v)_i {\lt} v_i\} \), that is, \(\lambda (v)\) is the smallest index \(i\) such that the \(i\)-th coordinate of \(f(v) - v\) is negative. If this smallest index \(i\) does not exist, then we have found a fixed point and are done: To see this, note that every \(v \in \Delta \) lies in the plane \(x_1 + x_2 + x_3 = 1\), hence \(\sum _i v_i = 1\). So if \(f(v) \neq v\), then at least one of the coordinates of \(f(v) - v\) must be negative (and at least one must be positive).

Let us check that this coloring satisfies the assumptions of Sperner’s lemma. First, the vertex \(e_i\) must receive color \(i\), since the only possible negative component of \(f(e_i) - e_i\) is the \(i\)-th component. Moreover, if \(v\) lies on the edge opposite to \(e_i\), then \(v_i = 0\), so the \(i\)-th component of \(f(v) - v\) cannot be negative, and hence \(v\) does not get the color \(i\).

Sperner’s lemma now tells us that in each triangulation \(T_k\) there is a tricolored triangle \(\{ v^{k:1}, v^{k:2}, v^{k:3}\} \) with \(\lambda (v^{k:i}) = i\). Since the simplex \(\Delta \) is compact, some subsequence of \((v^{k:1})_{k \geq 1}\) has a limit point \(v\). The distances of \(v^{k:2}\) and \(v^{k:3}\) from \(v^{k:1}\) are at most the mesh length \(\delta (T_k) \to 0\), so all three sequences converge to the same point \(v\).

But where is \(f(v)\)? We know that the first coordinate of \(f(v^{k:1})\) is smaller than that of \(v^{k:1}\) for all \(k\). Now since \(f\) is continuous, we derive that the first coordinate of \(f(v)\) is smaller or equal to that of \(v\). The same reasoning works for the second and third coordinates. Thus none of the coordinates of \(f(v) - v\) is positive — and we have already seen that this contradicts the assumption \(f(v) \neq v\).