#4 Extremal Principle

Let \(M\) be the largest element of the set. By the condition, \(f(M)\) belongs to the same set and \(f(M)>M\). This contradicts the maximality of \(M\). Therefore no such assignment exists.

Start from an arbitrary point \(v_1\) and always follow the arrow: \(v_1,v_2,v_3,\ldots\). Since there are finitely many points, some point repeats: \(v_i=v_j\) with \(i

Then the segment \(v_i,v_{i+1},\ldots,v_{j-1},v_j=v_i\) forms a directed cycle. Hence such a cycle exists.

Suppose \(v_k\) is adjacent to a vertex \(u\) outside the path. Then \(v_1v_2\ldots v_k u\) is a path with one more vertex.

This contradicts the choice of the original path as a longest path. Therefore all neighbours of \(v_k\) lie on the path.

Choose a longest path \(v_1v_2\ldots v_k\) in the tree. If \(v_k\) has a neighbour outside the path, the path can be extended, impossible.

If \(v_k\) is adjacent to an earlier vertex of the path other than \(v_{k-1}\), a cycle appears. A tree has no cycles. Thus the only neighbour of \(v_k\) is \(v_{k-1}\), so the degree of \(v_k\) is \(1\).

Let \([a,b]\) be an interval with the smallest right endpoint \(b\). Consider any other interval \([c,d]\). By the choice of \(b\), we have \(b\le d\).

Since \([a,b]\) and \([c,d]\) intersect, we cannot have \(b

Consider all connected subgraphs containing all vertices of the original graph. Choose one, \(H\), with the smallest number of edges. It exists because the original graph is among them.

If \(H\) contains a cycle, remove one edge of that cycle. Its endpoints are still connected through the rest of the cycle, so connectivity is preserved. This gives a connected spanning subgraph with fewer edges, a contradiction.

Thus \(H\) has no cycles. The desired graph is obtained by deleting redundant edges.

Choose a longest path \(v_1v_2\ldots v_k\). All neighbours of \(v_k\) lie on this path; otherwise the path could be extended.

Since the degree of \(v_k\) is at least \(2\), besides \(v_{k-1}\) it has another neighbour on the path. Let it be \(v_i\), where \(i

From each pair \(\{i,2n+1-i\}\), we cannot take both numbers because their sum is \(2n+1\). Thus at most one number is taken from each pair.

Suppose some pair contributes no number. Then one number from this pair can be added to \(A\): its only partner for the sum \(2n+1\) is also absent. The condition would remain true, contradicting maximality by inclusion.

Therefore exactly one number is taken from each pair.

Suppose uncovered vertices \(x\) and \(y\) are joined by an edge \(xy\). Since both vertices are uncovered, \(xy\) shares no endpoint with any chosen edge.

Then \(xy\) can be added to the chosen set, and the edges remain pairwise disjoint. This contradicts the assumption that no edge can be added. Hence no such edge exists.

We have \(8=3+5\), \(9=3+3+3\), and \(10=5+5\). Suppose counterexamples exist, and let \(n\) be the smallest one.

Since \(8,9,10\) are representable, \(n\ge 11\). Then \(n-3\ge 8\), and by the minimality of \(n\), the number \(n-3\) is representable: \(n-3=3a+5b\).

Therefore \(n=3(a+1)+5b\), contradicting the fact that \(n\) is a counterexample. Hence the statement is true for all \(n\ge 8\).

Call a pair of positions \(i

When neighbouring numbers \(x>y\) are swapped, the pair \((x,y)\) stops being an inversion. Their relations with all other numbers do not change the total number of inversions because the two numbers were adjacent. Thus the number of inversions decreases by \(1\).

It cannot decrease forever, so the process stops. At the end there is no neighbouring pair in the wrong order. Therefore the whole sequence is increasing.

The answer is \(n-2\). First show that \(n-1\) is impossible. If \(n-1\) people know everyone, then the remaining person knows each of these \(n-1\) people. Hence the remaining person also knows everyone, contradicting the condition.

Now show attainability. Let two people \(A\) and \(B\) not know each other, while everyone else knows everyone. Then exactly \(n-2\) people know all others, and \(A\) and \(B\) do not know everyone. The condition is satisfied.

Choose a directed path of maximum length \(v_1\to v_2\to\cdots\to v_k\). Suppose there is a vertex \(u\) outside the path.

If \(u\to v_1\), then \(u\) can be placed before \(v_1\), giving a longer path. Hence \(v_1\to u\). If \(v_k\to u\), then \(u\) can be placed after \(v_k\), so \(u\to v_k\).

Moving from left to right, let \(j\) be the first index such that \(u\to v_j\). Then \(j>1\), and by the minimality of \(j\) we have \(v_{j-1}\to u\). Thus \(u\) can be inserted between \(v_{j-1}\) and \(v_j\): \(v_1\to\cdots\to v_{j-1}\to u\to v_j\to\cdots\to v_k\). This is a longer path, a contradiction.

Therefore no outside vertex exists, and the path contains all vertices.

Suppose two neighbouring unchosen cells \(i\) and \(i+1\) have different colours. Then the pair \((i,i+1)\) satisfies the condition and is disjoint from all chosen pairs, because both cells are unchosen.

It can be added to the current set of pairs while preserving all conditions. This contradicts maximality by inclusion. Therefore no such neighbouring unchosen cells exist.

Choose a longest path \(v_1v_2\ldots v_m\). All neighbours of \(v_m\) lie on this path; otherwise the path could be extended.

The vertex \(v_m\) has at least \(k\) neighbours among \(v_1,\ldots,v_{m-1}\). Let \(v_i\) be the earliest of these neighbours on the path. Then among \(v_i,v_{i+1},\ldots,v_{m-1}\) there are at least \(k\) neighbours of \(v_m\), so \(m-i\ge k\).

The path edges from \(v_i\) to \(v_m\), together with the edge \(v_m v_i\), form the cycle \(v_i v_{i+1}\ldots v_m v_i\). It has \(m-i+1\ge k+1\) vertices.

Let the sum of all numbers in \(A\) be \(S\). The set \(A\) has \(2^k\) subsets, including the empty subset. By the condition, the sums of different nonempty subsets are distinct; the empty subset has sum \(0\), which does not coincide with them because all numbers are positive.

Thus we obtain \(2^k\) distinct integer sums. Each of them lies between \(0\) and \(S\), and there are exactly \(S+1\) integers in this interval. Hence \(S+1\ge 2^k\), so \(S\ge 2^k-1\).

Consider the unique path from \(A\) to \(B\). If the degree of \(A\) is greater than \(1\), then \(A\) has a neighbour \(C\) different from the next vertex on the path to \(B\).

In a tree, the path from \(C\) to \(B\) passes through \(A\), so the distance \(CB\) is one greater than \(AB\). This contradicts the maximal choice of \(A,B\). Hence the degree of \(A\) is \(1\). Similarly, the degree of \(B\) is \(1\).

For each position \(i\), let \(p_i\) be the length of the longest increasing subsequence ending at \(a_i\), and let \(q_i\) be the length of the longest decreasing subsequence ending at \(a_i\).

Suppose there is neither an increasing nor a decreasing subsequence of length \(n+1\). Then all pairs \((p_i,q_i)\) take values in \(\{1,\ldots,n\}\times\{1,\ldots,n\}\), so only \(n^2\) pairs are possible.

We show that pairs for different indices are distinct. If \(ip_i\). If \(a_i>a_j\), similarly \(q_j>q_i\). In both cases the pairs differ.

But there are \(n^2+1\) elements and at most \(n^2\) possible pairs. Contradiction. Therefore the required subsequence exists.

Choose a vertex \(v\) with maximum outdegree. Let \(u\) be a vertex not reached by an edge from \(v\). Then in the tournament we must have \(u\to v\).

Suppose no out-neighbour \(w\) of \(v\) has an edge \(w\to u\). Then for every such \(w\), the edge is directed \(u\to w\). Also \(u\to v\). Hence \(u\) defeats everyone defeated by \(v\), and also defeats \(v\) itself. Thus \(u\) has larger outdegree than \(v\), a contradiction.

Therefore there is an out-neighbour \(w\) of \(v\) such that \(w\to u\). Then \(v\to w\to u\). Vertices directly defeated by \(v\) are reached in one step. Hence \(v\) reaches every vertex in at most two steps.

Let two maximum-length paths \(P\) and \(Q\) be disjoint. Denote their length by \(L\). Since the graph is connected, there is a path joining some vertex \(x\) of \(P\) to some vertex \(y\) of \(Q\). Choose such a joining path as short as possible; then its internal vertices do not lie on \(P\) or \(Q\).

The vertex \(x\) splits \(P\) into two parts whose lengths sum to \(L\). One of these parts has length at least \(\frac{L}{2}\). Similarly, \(y\) splits \(Q\) into two parts, one of length at least \(\frac{L}{2}\).

Take the longer part of \(P\), then the joining path from \(x\) to \(y\), then the longer part of \(Q\). This is a simple path: the internal vertices of the joining path are outside \(P\) and \(Q\), and \(P\) and \(Q\) are disjoint.

Its length is at least \(\frac{L}{2}+1+\frac{L}{2}=L+1\), because the joining path has positive length. This is greater than the maximum length \(L\), a contradiction. Therefore two longest paths must share a vertex.