Book 2. Olympiad Combinatorics Methods

Each edge contributes \(2\) to the degree sum, so the sum of degrees is \(2E\), even. The sum of even degrees is even, hence the sum of odd degrees is even. A sum of an odd number of odd integers would be odd, so the number of odd-degree vertices is even.

The number of pairs \((student, club)\) where the student attends the club is \(120\cdot4=480\). If every club had at most \(31\) members, there would be at most \(15\cdot31=465\) such pairs, a contradiction. Hence some club has at least \(32\) members.

Count pairs \((cell, line)\), where the line is a row or column containing the marked cell. Each marked cell gives \(2\) pairs, so there are \(140\). There are \(24\) lines. The average is \(\frac{140}{24}>5\), so some line contains at least \(6\) marked cells.

The right side \(2^n\) counts subsets by independent choices: each element is either included or not. The left side counts the same subsets by size: choose the size \(k\), then choose the \(k\)-element subset. These are the same objects, so the identity follows.

If we first choose \(A\) of size \(k\), then the marked element \(x\in A\) can be chosen in \(k\) ways, giving the left side. If we first choose \(x\), there are \(n\) choices, and the remaining elements of the subset are chosen freely: \(2^{n-1}\) choices. This gives \(n2^{n-1}\).

The number of pairs \((x,A)\), where \(x\in A\), is at least \(18\cdot4=72\). These pairs are distributed among \(10\) elements. The average number of sets containing an element is at least \(7.2\), so some element belongs to at least \(8\) sets.

The sum of degrees is \(2E>(r-1)n\). If all degrees were at most \(r-1\), the sum of degrees would be at most \((r-1)n\), a contradiction. Hence some vertex has degree at least \(r\).

There are \(\binom n2\) games, and each game gives exactly one win. The average number of wins per player is \(\frac{\binom n2}{n}=\frac{n-1}{2}\). Therefore someone has at least the average, and someone has at most the average.

Count pairs \((A,\{x,y\})\), where \(A\subseteq[n]\) and \(x,y\in A\). If we first choose \(A\) of size \(k\), we get \(\binom{k}{2}\binom nk\). Summing over \(k\) gives the left side. If we first choose \(\{x,y\}\), there are \(\binom n2\) choices, and the remaining \(n-2\) elements are free: \(2^{n-2}\) choices.

Each row with \(3\) marks gives \(\binom32=3\) pairs of columns. There are \(6\cdot3=18\) pair occurrences. There are only \(\binom62=15\) pairs of columns. If each pair appeared at most once, there would be at most \(15\) occurrences, a contradiction. Hence some pair of columns appears in at least two rows.

Let \(d_i\) be the number of subsets containing the \(i\)-th element. Then \(\sum d_i=24\). The sum of all pairwise intersection sizes is \(\sum_{i=1}^5\binom{d_i}{2}\). With fixed sum \(24\), this is minimised by the balanced distribution \(5,5,5,5,4\), giving \(46\). If every pairwise intersection had size at most \(1\), the sum would be at most \(\binom82=28\). Contradiction.

The total number of solved-problem incidences is at least \(30\cdot3=90\). If each problem were solved by at most \(14\) participants, the total would be at most \(6\cdot14=84\), a contradiction. Hence some problem was solved by at least \(15\) participants.

Each chosen subset contains \(\binom{k}{2}\) pairs of elements, giving \(m\binom{k}{2}\) pair occurrences. But the same pair of elements cannot lie in two different chosen subsets; otherwise those two subsets would share at least two elements. The whole ground set has only \(\binom n2\) pairs. Therefore \(m\binom{k}{2}\le\binom n2\).

Each row gives \(\binom r2\) pairs of marked columns, for a total of \(n\binom r2\) occurrences. By the condition, each pair of columns appears at most once. There are \(\binom n2\) column pairs in total. Hence \(n\binom r2\le\binom n2\).

Fix the middle vertex \(v_i\). To form a length-\(2\) path with this middle vertex, choose two distinct neighbours among its \(d_i\) neighbours: \(\binom{d_i}{2}\) ways. Each unordered length-\(2\) path has exactly one middle vertex, so summing over all vertices gives the exact number.

Let \(d_j\) be the number of students who solved problem \(j\). Then \(\sum d_j\ge21\cdot6=126\). The number of triples \((\{u,v\}, problem)\), where both students solved the problem, is \(\sum_{j=1}^{10}\binom{d_j}{2}\). With total \(126\) over \(10\) problems, this sum is minimised by the balanced distribution \(13,13,13,13,13,13,12,12,12,12\), giving \(6\binom{13}{2}+4\binom{12}{2}=732\). There are \(\binom{21}{2}=210\) pairs of students. If every pair had at most \(3\) common solved problems, there would be at most \(630\) triples, a contradiction. Hence some pair has at least \(4\) common solved problems.

If any two chosen subsets intersect in at most one element, then the same pair of elements cannot lie in two different subsets. Thus the total number of pair occurrences is at most \(\binom{20}{2}=190\). But each of the \(30\) subsets of size \(6\) contains \(\binom62=15\) pairs, for \(450\) occurrences. Contradiction. Hence two subsets have at least two common elements.

Each chosen \(k\)-element set contains \(\binom{k}{t+1}\) subsets of size \(t+1\), giving \(m\binom{k}{t+1}\) occurrences. But the same \((t+1)\)-element subset cannot lie in two chosen sets; otherwise those two sets would have at least \(t+1\) common elements, which is forbidden. The ground set has \(\binom{n}{t+1}\) such subsets in total. The inequality follows.

The number of length-\(2\) paths is \(\sum_i\binom{d_i}{2}\), where \(d_i\) are vertex degrees. The function \(\binom{x}{2}=\frac{x(x-1)}2\) is convex, so for fixed sum \(\sum d_i=2m\), the sum \(\sum\binom{d_i}{2}\) is at least \(n\binom{2m/n}{2}\). If the average degree \(\frac{2m}{n}>r\), then the average value of \(\binom{d_i}{2}\) is greater than \(\binom r2\) in the needed strict sense, so some vertex contributes more than \(\binom r2\) length-\(2\) paths.

The sum of all pairwise intersection sizes is \(\sum_x\binom{d(x)}2\), because each element \(x\) contributes to pairs of sets containing it. Since \(\sum d(x)\ge mr\), convexity gives

\[\sum_x\binom{d(x)}2\ge n\binom{mr/n}{2}=\frac{mr(mr-n)}{2n}.\]

There are \(\binom m2\) pairs of sets. Hence the average pairwise intersection size is at least

\[\frac{\frac{mr(mr-n)}{2n}}{\binom m2}=\frac{r(mr-n)}{n(m-1)}.\]

Therefore one intersection is at least this average.

By inclusion-exclusion, the answer is \(18+14-6=26\). The six students studying both languages were counted twice, so subtract them once.

There are \(\left\lfloor\frac{200}{3}\right\rfloor=66\) multiples of \(3\), and \(40\) multiples of \(5\). Multiples of both, i.e. of \(15\), number \(13\). The answer is \(66+40-13=93\).

There are \(4^6\) words in total. Without \(A\), each position has \(3\) choices, so \(3^6\) words. The answer is \(4^6-3^6=4096-729=3367\).

There are \(3^5\) words. If a chosen letter is missing, there are \(2^5\) words, and \(3\) choices of the missing letter. If two chosen letters are missing, there is \(1^5\) word, with \(3\) choices; add these back. The answer is \(3^5-3\cdot2^5+3=150\).

By inclusion-exclusion, \(4!-\binom41 3!+\binom42 2!-\binom43 1!+\binom44 0!=24-24+12-4+1=9\).

The number divisible by at least one of \(2,3,5\) is \(500+333+200-166-100-66+33=734\). Therefore the number divisible by none of them is \(1000-734=266\).

There are \(3^6\) functions in total. Subtract functions missing a chosen value: \(3\cdot2^6\). Add back functions missing two chosen values: \(\binom32\cdot1^6\). The answer is \(3^6-3\cdot2^6+3=540\).

Without restrictions, \(8!\). If chosen \(i\) among \(1,2,3\) are fixed, the remaining \(8-i\) elements are permuted freely. The answer is \(8!-\binom31 7!+\binom32 6!-\binom33 5!=27240\).

If \(i\) elements are chosen to be fixed, the remaining \(n-i\) elements can be permuted in \((n-i)!\) ways. By inclusion-exclusion,

\[D_n=\sum_{i=0}^n(-1)^i\binom ni(n-i)!=n!\sum_{i=0}^n\frac{(-1)^i}{i!}.\]

First choose the \(2\) fixed points: \(\binom72=21\). The remaining \(5\) elements must have no fixed points, so they can be permuted in \(D_5=44\) ways. The answer is \(21\cdot44=924\).

There are \(10^8\) strings. If one of the three digits is missing, there are \(9^8\) strings; \(3\) choices. If two are missing, there are \(8^8\) strings; \(3\) choices. If all three are missing, \(7^8\). The answer is \(10^8-3\cdot9^8+3\cdot8^8-7^8\).

By inclusion-exclusion:

\[6!-\binom41 5!+\binom42 4!-\binom43 3!+\binom44 2!=720-480+144-24+2=362.\]

There are \(m^n\) functions in total. If \(i\) values are chosen to be unused, then all \(n\) domain elements must map to the remaining \(m-i\) values: \((m-i)^n\) functions. The \(i\) unused values can be chosen in \(\binom mi\) ways. Alternating signs by inclusion-exclusion gives the formula.

Choose the \(k\) elements that will be fixed: \(\binom nk\) ways. The remaining \(n-k\) elements must have no fixed points among their positions; otherwise there would be more than \(k\) fixed points. This can be done in \(D_{n-k}\) ways. The result is \(\binom nkD_{n-k}\).

In a derangement, element \(1\) goes to position \(j\ne1\), giving \(n-1\) choices. Consider element \(j\). If \(j\) goes to position \(1\), the remaining \(n-2\) elements form a derangement: \(D_{n-2}\) ways. If \(j\) does not go to position \(1\), after merging the roles of positions \(1\) and \(j\), the problem reduces to a derangement of \(n-1\) elements: \(D_{n-1}\) ways. Hence \(D_n=(n-1)(D_{n-1}+D_{n-2})\).

There are \(5!=120\) permutations. One violation fixes one cell and gives \(4!\) permutations; there are \(3\) such violations, so subtract \(72\). Two violations are compatible only for the pair \((1,2)\) and \((2,1)\). The pair \((1,1),(1,2)\) is impossible because \(\pi(1)\) cannot be both \(1\) and \(2\). The pair \((1,1),(2,1)\) is impossible because two values cannot both land in \(1\). The compatible pair gives \(3!\) permutations. A triple violation is impossible. The answer is \(120-3\cdot24+6=54\).

In the formula for \(|A_1\cup\cdots\cup A_m|\), an object lying in exactly \(r\) sets is counted \(\binom r1\) times in the single sums, \(\binom r2\) times in pairwise intersections, and so on. Its total contribution is \(\binom r1-\binom r2+\cdots+(-1)^{r+1}\binom rr\). This equals \(1-(1-1)^r=1\). Hence every object in the union is counted exactly once.

Let \(A_j\) be the event that element \(j\) is fixed, for \(j=1,\ldots,r\). If \(i\) such events are chosen, then \(i\) elements are fixed and the remaining \(n-i\) can be permuted in \((n-i)!\) ways. By inclusion-exclusion, the number of permutations avoiding these \(r\) events is \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).

Each distribution is a function from the set of balls to the set of boxes. Requiring every box to be nonempty means the function is onto. By inclusion-exclusion, the number is

\[\sum_{i=0}^{m}(-1)^i\binom mi(m-i)^n.\]

Here \(i\) is the number of chosen boxes declared empty.

Apply inclusion-exclusion to the forbidden events: “an element is fixed” and “a pair forms a transposition”. If \(i\) fixed elements and \(j\) disjoint transpositions are chosen, the forbidden structure can be chosen in \(\frac{n!}{i!\,j!\,2^j\,(n-i-2j)!}\) ways. The remaining \(n-i-2j\) elements are permuted freely in \((n-i-2j)!\) ways. The sign is \((-1)^{i+j}\). Hence the number is

\[\sum_{\substack{i,j\ge0\\ i+2j\le n}}(-1)^{i+j}\frac{n!}{i!\,j!\,2^j}.\]

To a subset \(A\), assign the string \(a_1\ldots a_n\), where \(a_i=1\) if \(i\in A\), and \(a_i=0\) otherwise. From such a string we recover \(A=\{i:a_i=1\}\). Hence this is a bijection. There are \(2^n\) binary strings of length \(n\).

Each path consists of exactly \(5\) steps \(R\) and \(4\) steps \(U\). The step sequence gives a word of length \(9\), and conversely every such word gives a path. Hence the number is \(\binom{9}{4}=126\).

A solution corresponds to a string of \(10\) stars and \(2\) bars: the numbers of stars in the three gaps are \(x_1,x_2,x_3\). Conversely, every such string gives a solution. There are \(\binom{12}{2}=66\) strings.

Since \(x_i\ge1\), set \(y_i=x_i-1\ge0\). Then \(y_1+y_2+y_3+y_4=13\). By stars and bars, the number of solutions is \(\binom{13+4-1}{4-1}=\binom{16}{3}=560\).

To each \(k\)-subset \(A\subseteq[n]\), assign \([n]\setminus A\). It has \(n-k\) elements. The inverse map is again taking the complement, so this is a bijection.

Fix an element \(a\). To each subset \(S\), assign \(S\triangle\{a\}\): if \(a\in S\), remove it; otherwise add it. The size changes by \(1\), so parity changes. The operation is its own inverse, hence a bijection between even-sized and odd-sized subsets.

All \(k\)-subsets of \([n]\) split into two classes. If a subset does not contain \(n\), it is a \(k\)-subset of \([n-1]\): \(\binom{n-1}{k}\) choices. If it contains \(n\), the remaining \(k-1\) elements are chosen from \([n-1]\): \(\binom{n-1}{k-1}\) choices. These classes are disjoint and cover all objects.

The path to \((3,2)\) contains \(3\) steps \(R\) and \(2\) steps \(U\), so there are \(\binom{5}{2}=10\) choices. From \((3,2)\) to \((7,5)\), we need \(4\) steps \(R\) and \(3\) steps \(U\), so \(\binom{7}{3}=35\) choices. The parts are independent, so the answer is \(10\cdot35=350\).

Set \(y_1=x_1-2\), \(y_2=x_2-4\), \(y_3=x_3\), \(y_4=x_4-5\). Then \(y_i\ge0\), and the sum is \(30-2-4-5=19\). The number of nonnegative solutions to \(y_1+\cdots+y_4=19\) is \(\binom{19+4-1}{3}=\binom{22}{3}=1540\).

The no-adjacency condition gives \(a_{i+1}\ge a_i+2\). Then \(b_i=a_i-i+1\) form an ordinary \(5\)-subset of \(\{1,\ldots,14\}\). Conversely, from \(b_1<\cdots

A partition into at most \(k\) parts is represented by a diagram with at most \(k\) rows. Transpose the diagram: rows become columns. Now each row length is at most \(k\), so every part of the new partition is at most \(k\). The inverse transformation is transposition again, hence a bijection.

Write \(n\) ones in a row. To split them into \(k\) nonempty groups, choose \(k-1\) of the \(n-1\) gaps between consecutive ones and place bars there. The group sizes are the summands. Conversely, every composition gives such bars. The answer is \(\binom{n-1}{k-1}\).

There are \(\binom{2n}{n}\) paths in total. A bad path first goes above the diagonal by a step \(U\), landing at a point with \(y=x+1\). Reflect the initial part up to this step in the line \(y=x+1\). This gives a bijection from bad paths to paths from \((-1,1)\) to \((n,n)\), of which there are \(\binom{2n}{n-1}\). Therefore the number of good paths is

\[\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}.\]

There are \(\binom{p+q}{q}\) words in total. The classical reflection bijection shows that the number of bad words is \(\binom{p+q}{q-1}\): a bad word first reaches equality after an initial \(A\)-lead, and reflecting the corresponding initial segment changes one \(A\) into an extra \(B\). Hence the number of good words is

\[\binom{p+q}{q}-\binom{p+q}{q-1}=\frac{p-q}{p+q}\binom{p+q}{q}.\]

Encode an opening parenthesis as a step \(R\), and a closing parenthesis as a step \(U\). In a correct parenthesis sequence, every prefix has at least as many opening parentheses as closing ones, so the number of \(U\)'s does not exceed the number of \(R\)'s. This is exactly \(y\le x\). There are \(n\) opening and \(n\) closing parentheses, so the path ends at \((n,n)\). Conversely, any path with \(y\le x\) gives a sequence whose every prefix has at least as many openings as closings, hence a correct parenthesis sequence.

From a partition into odd parts, group equal odd parts \(q\). If \(q\) appears \(m\) times, write \(m\) in binary: \(m=\sum 2^s\). Replace these \(m\) copies of \(q\) by parts \(2^s q\). For each \(q\), the powers \(2^s q\) are distinct, and different odd \(q\)'s give different parts. Thus we get a partition into distinct parts.

Conversely, write each distinct part uniquely as \(2^s q\), with \(q\) odd, and replace it by \(2^s\) copies of \(q\). This gives a partition into odd parts. The two operations are inverse.

The sum counts even-sized subsets with sign \(+\) and odd-sized subsets with sign \(-\). Fix element \(1\). The map \(S\mapsto S\triangle\{1\}\) changes the parity of the size and is its own inverse. Thus every even subset is paired with an odd subset, and each pair cancels. The sum is \(0\).

From a tree, build a sequence of length \(n-2\): while more than two vertices remain, remove the leaf of smallest label and record the label of its neighbour. Conversely, from a sequence \(c_1,\ldots,c_{n-2}\), reconstruct the tree: at each step take the smallest label not appearing in the current sequence, connect it to \(c_1\), then remove that label from the vertex set and delete \(c_1\) from the sequence. Finally connect the two remaining vertices.

These procedures are inverse: the leaf removed at each step is exactly the smallest label that will no longer appear in the code. Thus trees are in bijection with sequences of length \(n-2\) over \(n\) labels. There are \(n^{n-2}\) such sequences.

Fix a side of the polygon. In any triangulation, there is a unique triangle adjacent to this side; its third vertex splits the polygon into two smaller parts. Similarly, every correct parenthesis sequence is uniquely written as \((A)B\), where \(A\) and \(B\) are correct sequences. Choose the third vertex so that the number of pairs in \(A\) equals the number of triangles in the left part, and \(B\) corresponds to the right part. Applying the same rule recursively gives a bijection. The base case \(n=0\) is clear.

There are \(\binom{a+b}{b}\) paths in total. A bad path first violates the condition by stepping to the line \(y=x+1\). Reflect the initial segment up to this step in the line \(y=x+1\). This gives a path from \((-1,1)\) to \((a,b)\). Such a path must have \(a+1\) steps \(R\) and \(b-1\) steps \(U\), so the number of bad paths is \(\binom{a+b}{b-1}\). Therefore the number of good paths is

\[\binom{a+b}{b}-\binom{a+b}{b-1}=\frac{a-b+1}{a+1}\binom{a+b}{b}.\]

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.

In one move, the number of black coins either increases by \(2\), decreases by \(2\), or stays the same. Therefore its parity is preserved.

Initially the number of black coins is \(1\), which is odd. In the target position it is \(0\), which is even. The invariant values differ, so the position is unreachable.

Under chessboard colouring, each \(1\times2\) domino covers one black and one white square. Therefore any region tiled by dominoes contains equal numbers of black and white squares.

The full \(8\times8\) board has equal numbers of black and white squares. Removing two squares of the same colour destroys this equality. Hence a domino tiling is impossible.

Interpret \(+\) as \(1\) and \(-\) as \(-1\). One move changes two signs, so the product of the three numbers is multiplied by \((-1)^2=1\).

Initially the product is \(1\). For the state \(-,-,-\), the product is \(-1\). The invariant differs, so the state is impossible.

Each move changes the coordinate by a multiple of \(5\). Therefore the coordinate modulo \(5\) is invariant.

The initial coordinate has residue \(0\), while \(2026\equiv 1\pmod 5\). Hence point \(2026\) is unreachable.

After the move, the pile sizes become \(a-1\) and \(b+1\). The difference between the old and new sums of squares is

\[a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1).\]

Since \(a\ge b+2\), the right-hand side is positive. Therefore the sum of squares strictly decreases.

Let the numbers of red, blue, and green stones be \(r,b,g\). In a move, for example, \(r\) and \(b\) decrease by \(1\), while \(g\) increases by \(2\). The difference \(r-b\) is unchanged, while \(b-g\) and \(g-r\) change by multiples of \(3\). Therefore all pairwise differences modulo \(3\) are invariant.

Initially \(r-b=20-21=-1\), so \(r-b\equiv 2\pmod 3\). If all stones became one colour, then two of \(r,b,g\) would be \(0\), and the third would be \(63\), so all differences would be divisible by \(3\). Contradiction.

When \((a,b)\) is replaced by \((a-b,b)\) for \(a\ge b\), the gcd does not change: \(\gcd(a,b)=\gcd(a-b,b)\). The same holds when \(b\) is replaced by \(b-a\).

Initially \(\gcd(84,30)=6\). The pair \(7,7\) has gcd \(7\). Since the gcd is invariant, this pair is unreachable.

One move changes exactly two signs, so the product of all signs is multiplied by \((-1)^2=1\). Therefore the product is an invariant.

Initially the product is \(-1\), because there is one negative sign. In the all-positive state, the product is \(1\). The invariant differs, so the state is unreachable.

Colour the board like a chessboard. Every knight move takes the knight to a square of the opposite colour.

If a path through all \(25\) squares were closed, it would form a cycle of odd length \(25\) with colours alternating. But a closed alternating cycle must have even length. Contradiction.

Consider the parity of the number of black cells in each row. One move affects two cells in one chosen row and two cells in another chosen row. Hence the parity in every row is preserved. Similarly, the parity in every column is preserved.

Initially all row and column parities are \(0\). If there is exactly one black cell, its row and its column have odd parity. This is impossible.

An inversion is a pair of numbers in which the larger one stands to the left of the smaller one. The number of inversions is a nonnegative integer.

Swapping a neighbouring wrong pair decreases the number of inversions by exactly \(1\): that pair stops being an inversion, and the relations of these two numbers with all other numbers do not change the total number of inversions.

Therefore the number of inversions strictly decreases and cannot decrease forever. The process terminates.

Let \(S\) be the sum of the indices of the cells containing stones, counting stones with multiplicity. Each move increases \(S\) by exactly \(1\).

If there are \(m\) stones, then \(S\le mn\), because no stone can go beyond the \(n\)-th cell. Thus \(S\) strictly increases but is bounded above. Infinitely many moves are impossible.

Necessity: one move changes two signs, so the parity of the number of negative signs is preserved. If in the end there are \(0\) negative signs, then initially their number must be even.

For sufficiency, take a spanning tree and choose a root. Process leaves other than the root. If a leaf has a minus sign, apply the move to the edge joining the leaf to its parent; the leaf becomes positive, while the parent changes sign. If the leaf is positive, do nothing. After that, the leaf need not be touched again.

This makes all vertices except possibly the root positive. The parity of the number of negative signs has been preserved, and at the final stage there are no negative signs outside the root. Therefore the root is also positive. Hence all signs can be made positive.

Number the rows \(1,\ldots,10\) and the columns \(1,\ldots,14\). Let black cells be those for which \(i+j\) is odd. Let \(x_{ij}\) be \(0\) or \(1\), indicating whether the cell is marked.

Modulo \(2\), the number of marked black cells is

\[\sum_{i,j}(i+j)x_{ij}=\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

In every row and every column the number of marks is odd, so each such sum is \(1\) modulo \(2\). Therefore the desired parity is

\[\sum_{i=1}^{10} i+\sum_{j=1}^{14} j=55+105=160\equiv 0\pmod 2.\]

Thus the number of marked black cells is even.

In the initial colouring, every row and every column contains \(0\) black cells, an even number.

One move chooses two rows and two columns. In each chosen row, exactly two cells change colour, so the parity of the number of black cells in that row is preserved. Other rows do not change. The same argument applies to columns.

Therefore after any number of moves, all rows and columns preserve parity \(0\).

Consider the sum of squares of all pile sizes. If a stone is moved from a pile of size \(a\) to a pile of size \(b\), where \(a\ge b+2\), then the contribution of these two piles changes from \(a^2+b^2\) to \((a-1)^2+(b+1)^2\). As computed, the old sum exceeds the new one by \(2(a-b-1)>0\).

The sum of squares is a nonnegative integer, so it cannot strictly decrease forever. The process terminates.

If in the final state two piles differed by at least \(2\), a move would still be allowed. Hence in the end any two pile sizes differ by at most \(1\).

The gcd of the pair does not change when \((a,b)\) is replaced by \((a-b,b)\) or \((a,b-a)\), because common divisors are preserved in both directions.

If the numbers are not equal, one move decreases the sum \(a+b\): the larger number is replaced by a positive smaller number. The sum is a positive integer, so the process cannot continue forever.

When no move remains, the numbers are equal; let the pair be \(c,c\). The gcd has been preserved throughout, so \(c=\gcd(c,c)=\gcd(a,b)=d\). Thus the final pair is \(d,d\).

Necessity: one move changes two cells in each of two neighbouring rows and two cells in each of two neighbouring columns. Therefore the parity of the number of black cells in every row and every column is preserved. Initially all these parities are \(0\).

For sufficiency, let the target colouring have even rows and columns. We construct it from the white board. For \(i=1,\ldots,m-1\) and \(j=1,\ldots,n-1\), scan cells from left to right and top to bottom. If the current cell \((i,j)\) differs from the target, apply the move to the \(2\times2\) block with top-left corner \((i,j)\). After that, cell \((i,j)\) matches the target, and later moves will not affect it, because they start no higher and no further left.

After this procedure, all cells outside the last row and last column match the target. It remains to check the last row and last column. In every row and column, the current board has even black parity, and so does the target board. Therefore in each almost completed row, the last cell is forced to match the target. Similarly, the cells of the last row match. Hence the whole colouring is reachable.

Number the rows \(1,\ldots,14\) and the columns \(1,\ldots,18\). Let white cells be those for which \(i+j\) is even. Let \(x_{ij}\) be the indicator of whether the cell is marked.

Modulo \(2\), the number of marked white cells is

\[\sum_{i,j}(1+i+j)x_{ij}.\]

Expanding modulo \(2\), we get

\[\sum_{i,j}x_{ij}+\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

The total number of marked cells has parity \(14\), because each of the \(14\) rows contains an odd number of marks; hence this contribution is \(0\). Row and column mark sums are odd, so the remaining value is

\[\sum_{i=1}^{14}i+\sum_{j=1}^{18}j=105+171=276\equiv0\pmod2.\]

Therefore the number of marked white cells is even.

Represent a cell colour by \(0\) for white and \(1\) for black. If rows are switched according to variables \(r_i\in\{0,1\}\) and columns according to variables \(c_j\in\{0,1\}\), then the colour of cell \((i,j)\) is \(r_i+c_j\pmod2\).

For the rectangle corners \((i,j),(i,l),(k,j),(k,l)\), the sum of colours is

\[(r_i+c_j)+(r_i+c_l)+(r_k+c_j)+(r_k+c_l)\equiv0\pmod2.\]

Thus the number of black corners is always even.

Now prove the converse. Let a colouring \(a_{ij}\) have this property. Set \(r_i=a_{i1}\) for every row and \(c_j=a_{1j}+a_{11}\) for every column. Applying the rectangle condition to rows \(1,i\) and columns \(1,j\), we get

\[a_{ij}+a_{i1}+a_{1j}+a_{11}\equiv0\pmod2.\]

Hence \(a_{ij}=r_i+c_j\pmod2\). Therefore it is enough to switch all rows with \(r_i=1\) and all columns with \(c_j=1\). The colouring is reachable.

If there are at most \(2\) red edges and at most \(2\) blue edges, then there are at most \(4\) edges in total. But there are \(5\). Hence at least one colour appears at least \(3\) times.

A triangle has \(3\) edges and only \(2\) colours. By the pigeonhole principle, two edges have the same colour.

Choose a vertex \(v\). From it, \(3\) edges leave in two colours. By the pigeonhole principle, two of them have the same colour, say \(va\) and \(vb\).

Then \(a-v-b\) is a path of two edges of one colour.

Place the vertices as a pentagon. Colour the five sides red and the five diagonals blue.

The red graph is a cycle of length \(5\), so there is no red triangle. The blue graph is also a cycle of length \(5\), so there is no blue triangle.

If there are at most \(m-1\) red edges and at most \(m-1\) blue edges, then there are at most \(2m-2\) edges in total. But there are \(2m-1\) edges. Hence one colour appears at least \(m\) times.

Choose a vertex \(v\). From it, \(5\) edges leave, so at least \(3\) have the same colour. Let these be red edges to vertices \(a,b,c\).

If at least one of the edges \(ab,bc,ca\) is red, it forms a red triangle with \(v\). If none of these edges is red, then all of them are blue, and vertices \(a,b,c\) form a blue triangle.

Build a graph on \(6\) vertices: the vertices are people. Colour an edge red if the two people are acquainted, and blue if they are not.

By the \(K_6\) result, this colouring contains a monochromatic triangle. A red triangle means \(3\) pairwise acquainted people, and a blue triangle means \(3\) pairwise unacquainted people.

The \(K_6\) result shows that with \(6\) vertices a monochromatic triangle is unavoidable, so \(R(3,3)\le6\).

On the other hand, colour \(K_5\) as follows: the sides of a pentagon are red and the diagonals are blue. Each colour forms a cycle of length \(5\), so there is no monochromatic triangle. Hence \(R(3,3)>5\).

Therefore \(R(3,3)=6\).

Take a vertex \(v\). If three red edges leave it to \(a,b,c\), then no edge among \(a,b,c\) can be red, otherwise there is a red triangle with \(v\). Hence all edges among \(a,b,c\) are blue, giving a blue triangle. Contradiction.

Thus the red degree of every vertex is at most \(2\). Similarly, the blue degree is at most \(2\). But \(n-1\) edges leave a vertex, so \(n-1\le4\), hence \(n\le5\).

From any vertex, \(2m-1\) edges leave. By the strengthened pigeonhole principle, among these edges there are at least \(m\) edges of one colour. Thus any vertex works.

First show that \(t\) vertices are enough. In a red-blue colouring of \(K_t\), if there is a red edge, then there is a red \(K_2\). If there are no red edges, then all edges are blue, and all \(t\) vertices form a blue \(K_t\).

Fewer than \(t\) vertices are not enough: colour all edges blue. Then there is no red \(K_2\), and there is no blue \(K_t\) because there are fewer than \(t\) vertices. Hence \(R(2,t)=t\).

Among any chosen \(6\) of the \(7\) people, by \(R(3,3)=6\), there are already either \(3\) pairwise acquainted people or \(3\) pairwise unacquainted people. Hence such a triple also exists among all \(7\) people.

The number \(7\) is not the exact threshold because the same result is already guaranteed for \(6\) people.

Let \(N=R(s-1,t)+R(s,t-1)\), and colour the edges of \(K_N\) red and blue. Choose a vertex \(v\). The remaining \(N-1\) vertices split into red neighbours and blue neighbours of \(v\).

If there are at least \(R(s-1,t)\) red neighbours, then inside them there is either a red \(K_{s-1}\) or a blue \(K_t\). In the first case, together with \(v\) we get a red \(K_s\); in the second case, we already have a blue \(K_t\).

If there are fewer than \(R(s-1,t)\) red neighbours, then there are at least \(R(s,t-1)\) blue neighbours. Inside them there is either a red \(K_s\), or a blue \(K_{t-1}\), which together with \(v\) gives a blue \(K_t\).

In all cases, the required structure exists.

By Ramsey recursion,

\[R(3,4)\le R(2,4)+R(3,3).\]

Using \(R(2,4)=4\) and \(R(3,3)=6\), we get \(R(3,4)\le10\). Thus every red-blue colouring of the edges of \(K_{10}\) contains either a red \(K_3\) or a blue \(K_4\).

Translate this into people: red edge means acquaintance, blue edge means non-acquaintance. We get either \(3\) pairwise acquainted people or \(4\) pairwise unacquainted people.

By Ramsey recursion,

\[R(4,4)\le R(3,4)+R(4,3).\]

By symmetry, \(R(4,3)=R(3,4)\). Since \(R(3,4)\le10\), we obtain

\[R(4,4)\le10+10=20.\]

Colour the edge between two people red if they are acquainted, and blue if they are not. By the bound \(R(4,4)\le20\), in \(K_{20}\) there is either a red \(K_4\) or a blue \(K_4\).

A red \(K_4\) means \(4\) pairwise acquainted people, and a blue \(K_4\) means \(4\) pairwise unacquainted people.

If the red graph is connected, we are done. Suppose it is not connected. Then its vertices split into several red components.

Any edge between two different red components cannot be red; otherwise those components would merge. Hence all such edges are blue.

We show that the blue graph is connected. If two vertices lie in different red components, they are joined by a blue edge. If they lie in the same red component, take a vertex from another red component; both edges to it are blue, so there is a blue path of length \(2\). Therefore the blue graph is connected.

Translate the problem into an edge-colouring of \(K_9\): red means acquaintance and blue means non-acquaintance. Suppose there is no red triangle and no blue \(K_4\). Consider the red graph \(G\).

The graph \(G\) contains no triangles. Also, it has no independent set of \(4\) vertices, because such a set would correspond to a blue \(K_4\).

We show that every vertex of \(G\) has degree at most \(3\). Indeed, if a vertex \(v\) had \(4\) red neighbours, then there could be no red edges among these neighbours, otherwise a red triangle with \(v\) would appear. Hence these \(4\) neighbours would form an independent set in \(G\), i.e. a blue \(K_4\). Contradiction.

If every vertex had degree exactly \(3\), then the sum of degrees would be \(9\cdot3=27\), impossible because the sum of degrees of a graph is even. Hence there is a vertex \(v\) of degree at most \(2\).

Now consider the vertices not adjacent to \(v\) in the red graph. There are at least \(9-1-2=6\) of them. The red graph induced by these vertices is still triangle-free. By \(R(3,3)=6\), among these \(6\) vertices there is either a red triangle or an independent triple. There is no red triangle, so there is an independent triple.

This independent triple together with \(v\) forms an independent set of \(4\) vertices in the red graph, i.e. a blue \(K_4\). Contradiction. Therefore the required group of people exists.

Choose a vertex \(v\). From it, \(16\) edges leave in three colours, so by the pigeonhole principle at least \(6\) of them have one colour. Let these be red edges to a set \(A\) of \(6\) vertices.

If there is a red edge inside \(A\), it forms a red triangle together with \(v\). If there are no red edges inside \(A\), then all edges inside \(A\) are coloured with the two remaining colours.

By \(R(3,3)=6\), every two-colouring of the edges on \(6\) vertices contains a monochromatic triangle. It is monochromatic in one of the two remaining colours. Hence the original three-colouring also contains a monochromatic triangle.

We first prove that either the red or the blue graph is connected. If the red graph is connected, then it has a spanning tree, and that tree is red.

Suppose the red graph is not connected. Then its vertices split into red components. Any edge between different red components is blue; otherwise those components would be one component. Therefore the blue graph is connected: vertices in different red components are joined by blue edges, and two vertices inside the same red component are connected by a blue path of length \(2\) through a vertex from another component.

Thus the blue graph is connected, and every connected graph has a spanning tree. This tree is blue and passes through all vertices.

In the sum of degrees, each edge is counted exactly twice: once at each endpoint. Therefore the sum of degrees is \(2m\).

The sum of degrees is \(2m\), so it is even. The sum of degrees of even-degree vertices is even. Hence the sum of degrees of odd-degree vertices is also even. A sum of odd integers is even only when the number of summands is even.

Choose a longest simple path in the tree. If an endpoint has a neighbour outside the path, the path can be extended. If it is adjacent to another vertex of the path besides its neighbour on the path, a cycle appears. Hence its degree is \(1\). The same holds for the other endpoint. Thus there are two leaves.

Every connected graph has a spanning tree. A spanning tree contains all \(n\) vertices and has exactly \(n-1\) edges. The original graph contains all edges of this tree and possibly more. Hence it has at least \(n-1\) edges.

Let the new edge join vertices \(u\) and \(v\). In the tree, there was exactly one simple path between \(u\) and \(v\). This path together with the new edge forms a cycle.

No other cycle can appear: any cycle after the addition must use the new edge, because there were no cycles before. Then the rest of that cycle would be another path between \(u\) and \(v\) in the tree, impossible.

Let the components have \(n_1,n_2,\ldots,n_c\) vertices. Each component is a tree, so it has \(n_i-1\) edges. The total number of edges is

\[\sum_{i=1}^c(n_i-1)=\sum_{i=1}^c n_i-c=n-c.\]

Let the removed edge join \(u\) and \(v\). Since it lies on a cycle, after removing it, the rest of the cycle still contains a path from \(u\) to \(v\).

Any path in the original graph that used edge \(uv\) can be modified: replace \(uv\) by this alternate path. Hence connectedness is preserved.

Suppose the graph contains a cycle. Remove one edge of this cycle; connectedness remains. Then we obtain a connected graph on \(n\) vertices with \(n-2\) edges.

But a connected graph on \(n\) vertices has at least \(n-1\) edges. Contradiction. Hence there are no cycles, and the graph is a tree.

Take a spanning tree of the graph. It has \(n-1\) edges, so the original graph has exactly one edge outside this spanning tree. Adding one edge to a tree creates exactly one cycle.

Every cycle of the original graph must use this single extra edge, because the tree itself has no cycles. Therefore there is exactly one cycle.

Let the graph be split into parts \(A\) and \(B\), and every edge joins a vertex of \(A\) to a vertex of \(B\). Moving along a cycle, the vertices alternate between \(A\) and \(B\). After an odd number of steps, we would be in the other part, but to close the cycle we must return to the starting vertex and starting part. Hence the cycle length is even.

Colour vertices at even distance from \(v\) into one part and vertices at odd distance into the other. We need to prove that no edge joins vertices in the same part.

Suppose an edge \(xy\) joins two vertices with the same distance parity. Take shortest paths from \(v\) to \(x\) and from \(v\) to \(y\). These paths have a common initial segment; after removing it, the remaining two paths have total even length. Adding edge \(xy\) gives an odd cycle. This is forbidden. Hence every edge joins different parts.

If the trail is not closed, then at every internal vertex the used edges are paired: enter and leave. Thus internal vertices have even degree. Only the start and end may have odd degree.

If the trail is closed, then at the starting vertex entrances and exits also pair up, so all degrees are even. Hence the number of odd-degree vertices is either \(0\) or \(2\).

Let \(x\) be a leaf and \(y\) its only neighbour. In a perfect matching, vertex \(x\) must be covered by some edge. The only edge incident to \(x\) is \(xy\). Therefore edge \(xy\) must belong to the matching.

Suppose there is an edge \(uv\) whose two endpoints are not endpoints of chosen matching edges. Then \(uv\) is disjoint from every edge of the matching, so it can be added. This contradicts maximality by inclusion.

Hence every edge has at least one endpoint among the endpoints of chosen edges.

Every edge has one endpoint in \(A\) and one endpoint in \(B\). Counting edges by vertices of \(A\), we get \(d|A|\). Counting by vertices of \(B\), we get \(d|B|\). These are the same number of edges, so \(d|A|=d|B|\). Since \(d>0\), we have \(|A|=|B|\).

Start at any vertex and follow unused edges as long as possible. Since all degrees are even, one cannot get stuck at a vertex different from the start: every entrance requires another exit. Thus we obtain a closed walk.

Choose a closed walk using as many edges as possible. If it does not use all edges, connectedness gives a vertex of the walk incident to an unused edge leading into the unused part. Starting there and moving along unused edges, we again obtain a closed walk, which can be spliced into the first one. This increases the number of used edges, a contradiction.

Therefore the maximal walk uses all edges.

Let \(f\) be the number of faces. By Euler's formula, \(n-m+f=2\). Since the graph is simple and \(n\ge3\), every face is bounded by at least three edges. In the sum of face boundary lengths, every edge is counted twice, so \(3f\le2m\).

Thus \(f\le\frac{2m}{3}\), and \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Hence \(m\le3n-6\).

Necessity follows from entry-exit pairs: only the start and end of a non-closed Euler trail may be odd, while an Euler circuit has no odd vertices.

For sufficiency, if there are no odd vertices, the lemma on even degrees in a connected graph gives an Euler circuit.

If there are exactly two odd vertices, call them \(a\) and \(b\). Add a new edge \(ab\). Now all degrees are even, so the new graph has an Euler circuit. Remove the added edge from this circuit. The remaining sequence of edges is an Euler trail of the original graph from \(a\) to \(b\).

Let \(f\) be the number of faces. By Euler's formula, \(n-m+f=2\). A bipartite graph has no odd cycles, in particular no triangles. Therefore every face boundary has length at least \(4\).

The sum of face boundary lengths is \(2m\), so \(4f\le2m\), i.e. \(f\le\frac{m}{2}\). Then \(2=n-m+f\le n-m+\frac{m}{2}=n-\frac{m}{2}\). Hence \(m\le2n-4\).

A tree has no cycles, hence no odd cycles. Therefore it is bipartite: its vertices can be split into two parts \(A\) and \(B\), with every edge going between the parts.

Inside each part there are no edges, so each part is an independent set. Of the two numbers \(|A|\) and \(|B|\), whose sum is \(n\), one is at least \(\lceil n/2\rceil\). This larger part gives the desired independent set.

Any two edges of the star share the centre, so a matching cannot contain two edges. One edge can be chosen. The answer is \(1\).

Matching edges have no common endpoints. Therefore the \(a\) covered left vertices are joined to \(a\) distinct vertices of the right part. Hence the right part has at least \(a\) vertices.

Each vertex of \(S\) is covered by its matching edge. These edges go to distinct vertices of the right part, and all these vertices lie in \(N(S)\). Therefore \(N(S)\) has at least \(|S|\) vertices.

For example, choose \(1\in A_1\), \(2\in A_2\), and \(3\in A_3\). All representatives are distinct, so this is a system of distinct representatives.

If two uncovered vertices are adjacent, that edge has no common endpoint with any chosen edge. It can be added to the matching, a contradiction.

For one club there are \(2\) options. For any two clubs, the union of lists contains all three names or at least two names. For all three clubs, the union is \(\{a,b,c\}\), of size \(3\). Hall's condition holds, so an SDR exists. For example, \(A_1\to a\), \(A_2\to b\), \(A_3\to c\).

Take any \(S\) in the left part. At least \(3|S|\) edges leave \(S\). All enter \(N(S)\), and each vertex of \(N(S)\) receives at most \(3\) such edges. Thus \(3|S|\le3|N(S)|\), so \(|N(S)|\ge |S|\).

Hall's condition holds, hence there is a matching covering the left part.

For any left-side set \(S\), exactly \(d|S|\) edges leave it. All enter \(N(S)\), and each vertex of \(N(S)\) has degree \(d\), so it receives at most \(d\) of these edges. Hence \(d|S|\le d|N(S)|\), so \(|N(S)|\ge |S|\). By Hall's theorem, the desired matching exists.

Delete an arbitrary element \(x\). Take any \(k\) sets. Before deletion, their union had size at least \(k+1\). After deleting \(x\), the union size decreases by at most \(1\), so at least \(k\) elements remain.

Hall's condition holds for the new family, so an SDR exists.

Remove from the matching the chosen edges of this path and add the unchosen edges of the path. Since the path alternates, the newly chosen edges still have no common endpoints.

The path starts and ends at uncovered vertices, so it has one more unchosen edge than chosen edges. Therefore the matching size increases by \(1\).

Build a bipartite graph: talks on the left, days on the right, and an edge means the talk may be scheduled on that day. The condition says that for every set \(S\) of talks, the neighbour set of days has size at least \(|S|\). By Hall's theorem, there is a matching covering all talks. It gives the schedule.

If representatives are chosen, then any \(k\) sections have \(k\) distinct representatives, all lying in the union of these sections. Therefore the union contains at least \(k\) students.

Conversely, the condition on unions is Hall's condition for the student sets corresponding to the sections. By Hall's theorem, an SDR exists.

Delete two right-side vertices. For any nonempty \(S\subseteq A\), its neighbour set loses at most two vertices. Hence the new neighbour set size is at least \(|S|+2-2=|S|\).

Hall's condition remains true, so there is a matching covering the left part.

For any left-side set \(S\), at least \(5|S|\) edges leave it. All enter \(N(S)\), and each right-side vertex receives at most \(4\) such edges. Thus \(5|S|\le4|N(S)|\), so \(|N(S)|\ge \frac54|S|\ge |S|\).

By Hall's theorem, there is a matching covering the left part.

Let the parts be \(A\) and \(B\). Counting edges by parts gives \(d|A|=d|B|\), hence \(|A|=|B|\).

By the regular bipartite graph argument, there is a matching covering \(A\). Since the parts are equal, it also covers \(B\). Therefore the matching is perfect.

Build a bipartite graph: an exam is joined to a day if it may be held on that day. We check Hall's condition.

For one exam, at least \(n-1\) days are available, and for \(n\ge2\) this is at least \(1\). If \(k\ge2\) exams are chosen, then every day is available to at least one of them: a day can be forbidden for at most one exam. Hence the union of available days is all \(n\) days, and \(n\ge k\).

Hall's condition holds for every set of exams. Therefore a schedule with distinct days exists.

By definition, an augmenting path starts and ends at uncovered vertices and its edges alternate. Switching the status of edges along the path preserves the matching property and adds one more edge than it removes. Thus the matching size increases by \(1\). Hence the original matching was not maximum in size.

If an augmenting path exists, switching along it increases the matching size, so the matching is not maximum.

Conversely, suppose there is a matching \(M'\) larger than \(M\). Consider the graph consisting of edges that belong to exactly one of \(M\) and \(M'\). In this graph, all degrees are at most \(2\), so its components are paths and cycles with edges from \(M\) and \(M'\) alternating.

Since \(|M'|>|M|\), in some component there are more edges from \(M'\) than from \(M\). A cycle has equal numbers of both types, so this component is a path. It starts and ends with edges from \(M'\), and its endpoints are uncovered by \(M\). Therefore it is an augmenting path with respect to \(M\). This contradicts the absence of augmenting paths.

A \(d\)-regular bipartite graph has a perfect matching. Remove its edges. Every vertex degree decreases by \(1\), so the remaining graph is \((d-1)\)-regular and bipartite.

Repeat the argument: find a perfect matching and remove it. After \(d\) steps all edges are removed, and the found matchings are pairwise disjoint and cover all edges.

Take any \(k\) sets. They contain at least \(rk\) element occurrences in total, because each set has size at least \(r\). Each element in their union can be counted at most \(r\) times, since it belongs to at most \(r\) sets overall.

If the union size is \(u\), then \(rk\le ru\), so \(u\ge k\). Hall's condition holds for any \(k\) sets. Therefore an SDR exists.

In the product \((1+x)^9\), each of the nine factors gives a choice: take \(1\) or take \(x\). Degree \(4\) occurs exactly when \(x\) is chosen from four factors. Therefore the coefficient is \(\binom{9}{4}=126\). It counts the four-element subsets of a nine-element set.

The desired number is the coefficient of \(x^{14}\) in \(\frac{1}{(1-x)^3}\). Since \(\frac{1}{(1-x)^3}=\sum_{n\ge 0}\binom{n+2}{2}x^n\), the answer is \(\binom{16}{2}=120\).

Without the upper bound, there are \(\binom{11}{2}=55\) solutions. If \(a\ge 5\), then \(a'=a-5\) gives \(a'+b+c=4\), so there are \(\binom{6}{2}=15\) solutions. There are three possible variables, and two variables cannot both be at least \(5\), because the sum would be at least \(10\). The answer is \(55-3\cdot 15=10\).

We need the coefficient of \(x^8\) in \(\prod_{i=1}^7(1+x^i)\). The sum \(8\) is obtained as \(1+7\), \(2+6\), \(3+5\), \(1+2+5\), and \(1+3+4\). There are no other possibilities: for instance, if \(4\) is chosen with \(2\), the remaining \(2\) cannot be repeated; if \(6\) is chosen, only \(2\) remains, and so on. The answer is \(5\).

On one hand, \((1+x)^r(1+x)^s=(1+x)^{r+s}\), so the coefficient of \(x^n\) is \(\binom{r+s}{n}\). On the other hand, to obtain \(x^n\), we may take \(x^k\) from the first factor and \(x^{n-k}\) from the second. This gives \(\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}\). The coefficients of the same polynomial are equal, so the identity is proved.

The generating function is \(\frac{1}{(1-x^2)^4}\). We need the coefficient of \(x^{18}\), equivalently the coefficient of \(y^9\) in \(\frac{1}{(1-y)^4}\). This is \(\binom{9+3}{3}=\binom{12}{3}=220\).

The number of strings with \(k\) ones is \(\binom{n}{k}\). Thus we need the sum of coefficients of even powers in \((1+x)^n\). It equals \(\frac{(1+1)^n+(1-1)^n}{2}\). For \(n\ge 1\), this is \(\frac{2^n+0}{2}=2^{n-1}\).

The empty composition of \(0\) gives \(c_0=1\). For \(n\ge 2\), the first part is \(1\) or \(2\), so \(c_n=c_{n-1}+c_{n-2}\), with \(c_1=1\). For the series, \(C(x)=1+xC(x)+x^2C(x)\), hence \(C(x)=\frac{1}{1-x-x^2}\). If \(F_0=0\), \(F_1=1\), then \(c_n=F_{n+1}\).

Without restrictions, there are \(\binom{24}{4}=10626\) solutions. If one box contains at least \(7\), subtracting \(7\) leaves sum \(13\), giving \(\binom{17}{4}=2380\) solutions; there are \(5\) boxes. If two boxes contain at least \(7\), the remaining sum is \(6\), giving \(\binom{10}{4}=210\) solutions; there are \(\binom{5}{2}=10\) pairs. Three such boxes are impossible. The answer is \(10626-5\cdot 2380+10\cdot 210=826\).

The expansion \(\frac{1}{(1-x)^2(1-x^3)}=(1+x+x^2+\cdots)^2(1+x^3+x^6+\cdots)\) shows that the coefficient equals the number of triples \((a,b,c)\) such that \(a+b+3c=10\). For \(c=0,1,2,3\), the numbers of solutions for \(a+b\) are \(11,8,5,2\), respectively. The sum is \(11+8+5+2=26\).

Each part \(i\) can be taken either once or not at all, so the generating function is \(\prod_{i=1}^{11}(1+x^i)\). The partitions are \(11\), \(10+1\), \(9+2\), \(8+3\), \(8+2+1\), \(7+4\), \(7+3+1\), \(6+5\), \(6+4+1\), \(6+3+2\), \(5+4+2\), \(5+3+2+1\). There are \(12\) of them.

The coefficient \(c_k\) equals the number of tuples \((a_1,\ldots,a_n)\) such that \(0\le a_i\le m\) and \(a_1+\cdots+a_n=k\). Map such a tuple to \((m-a_1,\ldots,m-a_n)\). The new numbers still lie between \(0\) and \(m\), and their sum is \(mn-k\). This correspondence is reversible, so \(c_k=c_{mn-k}\).

Let \(b_i=a_i-1\). Then \(b_1+\cdots+b_6=18\) and \(0\le b_i\le 6\). Without the upper bound, there are \(\binom{23}{5}=33649\) solutions. If one \(b_i\ge 7\), the remaining sum is \(11\), giving \(\binom{16}{5}=4368\) solutions; there are \(6\) choices of the variable. If two \(b_i\ge 7\), the remaining sum is \(4\), giving \(\binom{9}{5}=126\) solutions; there are \(\binom{6}{2}=15\) pairs. Three variables cannot be at least \(7\), because the remaining sum would be negative. The answer is \(33649-6\cdot 4368+15\cdot 126=9331\).

Without the upper bound, there are \(\binom{19}{7}=50388\) solutions. If a chosen variable is at least \(4\), subtracting \(4\) leaves sum \(8\), giving \(\binom{15}{7}=6435\) solutions; there are \(8\) choices of the variable. For two variables, the remaining sum is \(4\), giving \(\binom{11}{7}=330\) solutions; there are \(\binom{8}{2}=28\) pairs. For three variables, the remaining sum is \(0\), giving \(1\) solution; there are \(\binom{8}{3}=56\) triples. Four variables are impossible. The desired coefficient is

\[50388-8\cdot 6435+28\cdot 330-56=8092.\]

Let the chosen numbers be \(i_1<\cdots

If a tiling has exactly \(k\) dominoes, then the number of single squares is \(n-2k\). Compress each domino into one block. Then there are \(k+(n-2k)=n-k\) blocks in total, and we only need to choose which \(k\) of them are dominoes. This can be done in \(\binom{n-k}{k}\) ways. The reconstruction is unique: chosen blocks expand into dominoes, and the others remain single squares.

Partitions into distinct parts are encoded by \(\prod_{i\ge 1}(1+x^i)\), because each part \(i\) may be taken at most once. Use \(1+x^i=\frac{1-x^{2i}}{1-x^i}\):

\[\prod_{i\ge 1}(1+x^i)=\frac{\prod_{i\ge 1}(1-x^{2i})}{\prod_{i\ge 1}(1-x^i)}.\]

The denominator contains factors for all positive \(i\), while the numerator cancels all even factors. What remains is \(\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}\), the generating function for partitions into odd parts. Therefore the coefficients of \(x^n\) are equal.

Set \(y_i=5-x_i\). Then \(0\le y_i\le 5\) and \(y_1+\cdots+y_8=10\). The condition that \(x_1+x_2+x_3\) is even is equivalent to \(15-(y_1+y_2+y_3)\) being even, so \(y_1+y_2+y_3\) is odd.

Let \(A_3(t)\) be the number of triples from \(0\) to \(5\) with sum \(t\), and let \(A_5(u)\) be the number of 5-tuples from \(0\) to \(5\) with sum \(u\). We need to sum \(A_3(t)A_5(10-t)\) over odd \(t\). Coefficients of \((1+x+\cdots+x^5)^3\) and \((1+x+\cdots+x^5)^5\) give:

\[3\cdot 540+10\cdot 305+21\cdot 126+27\cdot 35+25\cdot 5=8386.\]

The answer is \(8386\).

Let \(\omega\ne 1\) be a cube root of unity, so \(1+\omega+\omega^2=0\). If \(F(t)=\prod_{j=1}^{3m}(1+t^j)\), then the number of coefficients whose degree is divisible by \(3\) is

\[\frac{F(1)+F(\omega)+F(\omega^2)}{3}.\]

We have \(F(1)=2^{3m}\). Among the numbers \(1,\ldots,3m\), each residue \(0,1,2\) modulo \(3\) appears \(m\) times. Hence

\[F(\omega)=(1+1)^m(1+\omega)^m(1+\omega^2)^m=2^m((1+\omega)(1+\omega^2))^m.\]

But \((1+\omega)(1+\omega^2)=1+\omega+\omega^2+\omega^3=1\), so \(F(\omega)=2^m\). Similarly \(F(\omega^2)=2^m\). Thus the answer is \(\frac{2^{3m}+2^m+2^m}{3}=\frac{2^{3m}+2^{m+1}}{3}\).

Let \(a_i\in\{0,1,2,3\}\) be the number of weights \(2^i\) taken. We need to solve \(\sum_{i=0}^{m-1}a_i2^i=2^m-1\), whose binary form consists of \(m\) ones.

Process the digits from low to high. Before each digit, the carry is \(0\) or \(1\). If the carry is \(0\), then to obtain a one in this digit we may take \(a_i=1\) and keep carry \(0\), or take \(a_i=3\) and create carry \(1\). If the carry is \(1\), then we may take \(a_i=0\) and get carry \(0\), or take \(a_i=2\) and keep carry \(1\). Thus after each of the \(m\) digits, the number of ways to reach carry \(0\) equals the number of ways to reach carry \(1\), and both are the sum of the two previous states.

After the first digit, there is \(1\) way in each state. After \(m\) digits, each state has \(2^{m-1}\) ways. At the end, the carry must be \(0\); otherwise the sum exceeds \(2^m-1\). Therefore the answer is \(2^{m-1}\).