obvious

“nothing to prove”

obvious

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} {\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.

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.

TODO

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.

TODO