Book 1. Foundations of Olympiad Combinatorics

There are \(6+5=11\) cards in total, so one card can be chosen in \(11\) ways.

For each of the \(4\) soups, there are \(3\) choices of main dish. Total: \(4\cdot3=12\) lunches.

The tens digit has \(5\) choices, and the units digit has \(4\) choices. Total: \(5\cdot4=20\).

Each element is either included or not, so there are \(2^6=64\) subsets. One is empty, so \(64-1=63\) are nonempty.

The number \(a\) can be \(1,2,3,4,5,6\). After choosing \(a\), \(b=7-a\) is positive and determined. Answer: \(6\).

If the last digit is \(0\), the hundreds digit has \(5\) choices and the tens digit \(4\): \(20\). If the last digit is \(2\) or \(4\), the hundreds digit cannot be \(0\) or the last digit: \(4\) choices, then \(4\) for the tens digit. For two such cases: \(2\cdot4\cdot4=32\). Total: \(52\).

We must place \(2\) up steps among \(5\) total steps. This can be done in \(10\) ways: choose the two positions of the up steps among five.

First letter: \(3\) choices. Each of the next three letters: \(2\) choices. Total: \(3\cdot2^3=24\).

Multiples of \(3\): \(66\). Multiples of \(5\): \(40\). Multiples of both, i.e. \(15\): \(13\). Answer: \(66+40-13=93\).

The chair can be chosen in \(12\) ways, then the secretary in \(11\) ways. Total: \(12\cdot11=132\).

There are \(35\) teams of \(3\) from \(7\) people. All-boy teams: \(4\). Therefore the answer is \(35-4=31\).

Choose the first stripe in \(4\) ways, the second in \(3\), and the third in \(3\). Total: \(4\cdot3\cdot3=36\).

If the last digit is \(0\), the first has \(7\) choices, then \(6\) and \(5\): \(210\). If the last digit is \(5\), the first is chosen from \(1,2,3,4,6,7\): \(6\) choices, then \(6\) and \(5\): \(180\). Total: \(390\).

Choose \(3\) positions out of \(10\) for the ones; all remaining positions are zeros. This gives \(120\) strings.

Total: \(3^5=243\). Without \(A\): \(2^5=32\). Without \(B\): \(32\). Without both letters: only \(CCCCC\), one word. Answer: \(243-32-32+1=180\).

There are \(35\) paths in total: choose the positions of three up moves among seven. Through \((2,1)\): \(3\) paths to the point and \(6\) paths from it to \((4,3)\). Forbidden paths: \(18\). Answer: \(35-18=17\).

Among \(1\) to \(20\), there are \(10\) even and \(10\) odd numbers. Pairs with even sum: both even \(10\cdot10\) or both odd \(10\cdot10\). Total: \(200\).

Choose any \(3\) digits from \(1,2,\ldots,9\). After choosing them, there is exactly one increasing order. There are \(84\) such choices.

After placing one ball in each box, \(2\) balls remain. Possibilities: both in one box — \(3\) ways; one in each of two boxes — \(3\) ways. Total: \(6\).

A \(4\) by \(5\) grid has \(5\) horizontal and \(6\) vertical grid lines. Choose \(2\) vertical and \(2\) horizontal lines: \(15\cdot10=150\).

There are \(5\) even and \(5\) odd decimal digits. For six digits, the digit sum is even if the number of odd digits is \(2\) or \(4\). With \(2\) odd digits, there are \(10\) sets without zero and \(40\) with zero; contribution \(10\cdot720+40\cdot600=31200\). With \(4\) odd digits, there are \(30\) sets without zero and \(20\) with zero; contribution \(30\cdot720+20\cdot600=33600\). Total: \(64800\).

There are \(2^{20}\) subsets. With no even number: choose only from \(10\) odd numbers, \(2^{10}\). With no multiple of \(5\): \(16\) available numbers, \(2^{16}\). With neither even numbers nor multiples of \(5\): \(8\) odd nonmultiples of \(5\), so \(2^8\). Answer: \(2^{20}-2^{10}-2^{16}+2^8\).

If all \(5\) symbols are equal, there are \(4\) strings. If the multiplicities are \(3\) and \(2\), choose the letter appearing \(3\) times: \(4\) ways, the letter appearing \(2\) times: \(3\) ways, and the positions of the first letter: \(10\) ways. Total: \(4+4\cdot3\cdot10=124\).

Consider the \(7\) possible forbidden adjacencies. If \(k\) adjacencies are chosen, they form \(c\) blocks of consecutive edges in a path. Such \(k\) edges can be chosen in \(C(k-1,c-1)C(8-k,c)\) ways. Each block has \(2\) orientations, so \(2^c\) orientations, and after gluing there are \(8-k\) objects to permute, giving \((8-k)!\). Inclusion-exclusion gives \(40320-70560+51840-20400+4608-612+48-2=5242\).

The answer is \(5!=120\).

If all \(4\) letters were distinct, there would be \(4!=24\) arrangements. Each word is counted \(2!\cdot2!=4\) times. Answer: \(24/4=6\).

The first can be chosen in \(7\) ways, the second in \(6\), the third in \(5\). Total: \(7\cdot6\cdot5=210\).

Fix one person to remove rotations. Arrange the remaining \(4\) people in \(4!=24\) ways.

The block and \(4\) other people make \(5\) objects, arranged in \(5!\) ways. The block has \(2\) internal orders. Answer: \(2\cdot5!=240\).

There are \(6!=720\) total arrangements. They stand together in \(2\cdot5!=240\) ways. Therefore the answer is \(720-240=480\).

There are \(6\) letters. Divide \(6!\) by \(3!\) for the \(A\)'s and by \(2!\) for the \(N\)'s. We get \(6!/(3!\cdot2!)=60\).

Total: \(7!=5040\). If the two are adjacent, glue them: \(6!\cdot2=1440\). Answer: \(5040-1440=3600\).

The three subject blocks can be arranged in \(3!\) ways. Inside the blocks: \(3!\), \(2!\), \(2!\). Total: \(3!\cdot3!\cdot2!\cdot2!=144\).

The pair forms a block. There are \(5\) objects around a circle, arranged in \((5-1)!=24\) ways. The block has \(2\) internal orders. Answer: \(48\).

Total: \(24\). With one specified fixed point: \(3!\), and there are \(4\) choices. With two: \(2!\), and \(6\) pairs. With three: \(1!\), and \(4\) choices. With four: \(1\). Answer: \(24-4\cdot6+6\cdot2-4\cdot1+1=9\).

There are \(5!=120\) permutations. By symmetry, exactly half have \(1\) before \(2\). Answer: \(60\).

The boys can be arranged in \(5!\) ways. Around them are \(6\) gaps: before the first, between neighbors, and after the last. Choose \(4\) gaps for the girls and arrange the girls in \(4!\) ways. Answer: \(5!\cdot15\cdot4!=43200\).

Total: \(6!/(2!2!2!)=90\). If \(AA\) is adjacent, count the block \(AA\), \(B,B,C,C\): \(5!/(2!2!)=30\), and there are \(3\) letters. If two pairs are adjacent, for example \(AA\) and \(BB\), we get \(4!/2!=12\), with \(3\) choices. If all three pairs are adjacent, \(3!=6\). Answer: \(90-3\cdot30+3\cdot12-6=30\).

If the last digit is \(0\), the first digit has \(6\) choices, then \(5\) and \(4\): \(120\). If the last digit is \(5\), the first digit is not \(0\) or \(5\): \(5\) choices, then \(5\) and \(4\): \(100\). Total: \(220\).

Total: \((8-1)!=5040\). If the two are adjacent, glue them into a block: \(7\) objects around a circle, \((7-1)!=720\), and \(2\) internal orders. Bad cases: \(1440\). Answer: \(5040-1440=3600\).

There are \(8!\) arrangements. The relative orders of \(A,B,C\) are equally likely, and there are \(3!=6\). Exactly one order works, so the answer is \(8!/6=6720\).

The even numbers \(2,4,6\) can be placed in positions \(2,4,6\) in \(3!\) ways. The odd numbers \(1,3,5,7\) occupy the remaining positions in \(4!\) ways. Answer: \(3!\cdot4!=144\).

There are \(10\) pairs of positions for the two \(A\)'s. Adjacent pairs: \(4\), so non-adjacent pairs: \(6\). The remaining \(3\) positions can be filled independently with \(B,C,D\): \(3^3=27\). Answer: \(6\cdot27=162\).

Fix Anton. Boris has \(2\) seats at distance two around the circle from Anton. Arrange the remaining \(3\) people in \(3!\) ways. Answer: \(2\cdot3!=12\).

Total: \(5!=120\). By inclusion-exclusion over specified fixed points: \(120-5\cdot4!+10\cdot3!-10\cdot2!+5\cdot1!-1=120-120+60-20+5-1=44\).

The boys can be seated around the table in \((6-1)!=120\) ways. This creates \(6\) gaps, into which the \(6\) girls can be placed in \(6!\) ways. Answer: \(120\cdot720=86400\).

The numbers \(4,5,6,7,8\) can be arranged in \(5!\) ways. They create \(6\) gaps, including the ends. Choose \(3\) gaps for \(1,2,3\) and arrange these numbers in \(3!\) ways. Answer: \(5!\cdot20\cdot6=14400\).

There are \(10!/(2!^5)=113400\) total permutations. If \(k\) letters are chosen whose pairs are glued, we get \(C(5,k)(10-k)!/(2!^{5-k})\) arrangements. Inclusion-exclusion gives \(113400-113400+50400-12600+1800-120=39480\).

Ordered selection gives \(5\cdot4=20\) ways, but each pair is counted twice. Answer: \(10\).

There are \(2^4=16\) subsets. One is empty, so \(15\) are nonempty.

We get \(\binom{7}{3}=7\cdot6\cdot5/3!=35\).

Each choice of \(3\) elements corresponds to the choice of the \(7\) elements not taken. This is a bijection, so the numbers are equal.

Choose \(2\) positions out of \(6\). Answer: \(\binom{6}{2}=15\).

Choose the girls in \(\binom{5}{2}=10\) ways and the boy in \(4\) ways. Total: \(40\).

We get \(\binom{5}{2}\binom{4}{2}+\binom{5}{3}\binom{4}{1}+\binom{5}{4}=10\cdot6+10\cdot4+5=105\).

Any two vertices determine a segment: \(\binom{12}{2}=66\). Among these are \(12\) sides. Therefore there are \(66-12=54\) diagonals.

Total: \(\binom{10}{4}=210\). Without top students, choose \(4\) from the other \(7\): \(\binom{7}{4}=35\). Answer: \(175\).

Let \(a_1

The string consists of \(8\) ones and \(2\) dividers, \(10\) symbols total. Choose the divider positions: \(\binom{10}{2}=45\).

Let \(x'=x-1\), \(y'=y-1\), \(z'=z-1\). Then \(x'+y'+z'=7\) in nonnegative variables. Answer: \(\binom{9}{2}=36\).

Count \(k\)-element subsets of an \(n\)-element set. The special element is either not chosen: \(\binom{n-1}{k}\), or chosen: \(\binom{n-1}{k-1}\). The sum of these disjoint cases gives all subsets.

A team of \(3\) can contain \(3,2,1,0\) boys. These cases are disjoint. In each case choose the required number of boys and girls, giving the stated sum.

For chosen \(a_1<\cdots

Total: \(\binom{20}{4}=4845\). There are \(16\) numbers not divisible by \(5\), so subsets with no multiple of \(5\): \(\binom{16}{4}=1820\). Answer: \(3025\).

Cases: \(3\) boys and \(2\) girls: \(\binom{6}{3}\binom{5}{2}=200\); \(4\) boys and \(1\) girl: \(\binom{6}{4}\binom{5}{1}=75\); \(5\) boys: \(\binom{6}{5}=6\). Total: \(281\).

Choose \(3\) vertices from \(9\). Answer: \(\binom{9}{3}=84\).

Let \(x'=x-2\), \(y'=y-3\). Then \(x'+y'+z=7\), all variables nonnegative. The number of solutions is \(\binom{9}{2}=36\).

Cases: \(3\) red and \(2\) blue: \(\binom{10}{3}\binom{8}{2}=3360\); \(4\) red and \(1\) blue: \(\binom{10}{4}\binom{8}{1}=1680\); \(5\) red: \(\binom{10}{5}=252\). Total: \(5292\).

Consider all \((r+1)\)-element subsets of \(\{1,\ldots,n+1\}\). There are \(C(n+1,r+1)\). If the largest element is \(t+1\), where \(r\le t\le n\), then the other \(r\) elements are chosen from the first \(t\) elements: \(C(t,r)\) ways. Summing over \(t\) gives the left side.

After choosing \(1\), choose \(4\) more numbers from \(\{3,\ldots,15\}\) with no adjacency. This is an interval of length \(13\). The number of ways to choose \(4\) nonconsecutive elements from \(13\) is \(\binom{13-4+1}{4}=\binom{10}{4}=210\).

The possibilities are \(2\) boys and \(4\) girls, \(3\) and \(3\), \(4\) and \(2\). We get \(\binom{8}{2}\binom{7}{4}+\binom{8}{3}\binom{7}{3}+\binom{8}{4}\binom{7}{2}=28\cdot35+56\cdot35+70\cdot21=4410\).

It is enough to split all subsets into \(6\) chains, because then \(7\) chosen subsets hit one chain twice by the pigeonhole principle. For example, take the chains \(\varnothing\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\subset\{1,2,3,4\}\); \(\{2\}\subset\{2,3\}\subset\{2,3,4\}\); \(\{3\}\subset\{1,3\}\subset\{1,3,4\}\); \(\{4\}\subset\{1,4\}\subset\{1,2,4\}\); and the singleton chains \(\{2,4\}\), \(\{3,4\}\). Any two sets in one chain are comparable by inclusion.

Each handshake corresponds to a pair of people. There are \(10\cdot9/2=45\) pairs.

There are \(20\cdot2=40\) pairs.

When summing by rows, each entry is counted once. When summing by columns, each entry is also counted once. Therefore the totals are equal.

Each of the \(12\) words gives \(5\) positions. Total: \(12\cdot5=60\) pairs.

Choose \(2\) vertices from \(6\): \(6\cdot5/2=15\).

The sum of degrees is \(2E\), hence even. The sum of degrees of even-degree vertices is even, so 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 average club size is \(60/8=7.5\). If every club had at most \(7\), the total would be at most \(56\), contradiction. Hence some club has at least \(8\).

Each of the \(5\) elements belongs to exactly half of all subsets, i.e. \(2^4=16\) subsets. The sum of subset sizes equals the number of pairs \((S,x)\), so it is \(5\cdot16=80\).

Choose \(x\) in \(6\) ways. For each \(x\), each of the other \(5\) elements either belongs to \(S\) or not: \(2^5\) ways. Total: \(6\cdot2^5=192\).

Choose the middle vertex \(B\) in \(6\) ways. Choose \(A\) in \(5\) ways and \(C\) in \(4\) ways. Total: \(6\cdot5\cdot4=120\).

From each of the \(n\) vertices, \(n-3\) diagonals are drawn, so there are \(n(n-3)\) diagonal endpoints. Each diagonal has two endpoints, so the number of diagonals is \(n(n-3)/2\).

If everyone solved at most \(3\) problems, the total would be at most \(25\cdot3=75\), less than \(100\). Therefore someone solved at least \(4\) problems.

By size \(S=k\): there are \(C(n,k)\) subsets and \(k\) choices of the marked element, giving the left side. By marked element: \(n\) choices for \(x\), and the other \(n-1\) elements are chosen freely for \(S\), \(2^{n-1}\) ways. This gives the right side.

Choose a three-element subset of \(\{1,\ldots,n+1\}\). If the largest element is \(t+1\), the other two are chosen from \(1,\ldots,t\), in \(C(t,2)\) ways. Summing over \(t=2,\ldots,n\) gives the left side, while the total number is \(C(n+1,3)\).

Total memberships: \(40\cdot2=80\). If every club had at most \(15\) students, the total would be at most \(5\cdot15=75\), contradiction. Hence some club has at least \(16\) students.

Each element is either outside \(B\), in \(B\) but not in \(A\), or in both sets. Three independent states for each of \(n\) elements give \(3^n\) pairs.

Choose \(2\) points out of \(12\). This gives \(12\cdot11/2=66\) segments.

There are \(n(n-1)/2\) games, each giving exactly one win. The average number of wins per player is \((n(n-1)/2)/n=(n-1)/2\). Hence some player has at least the average.

A \(5\) by \(6\) grid has \(6\) horizontal and \(7\) vertical lines. A rectangle is determined by choosing two vertical and two horizontal lines. Answer: \(C(7,2)C(6,2)=21\cdot15=315\).

Total memberships: \(12\cdot5=60\). The average number of committees per person is \(60/20=3\). Hence some person belongs to at least \(3\) committees.

Build the acquaintance graph. The sum of degrees is at least \(15\cdot7=105\). Each acquainted pair contributes twice to the degree sum, so the number of edges is at least \(105/2=52.5\). Since it is an integer, it is at least \(53\).

By size \(S=k\), there are \(k^2\) ways to choose the ordered pair \((x,y)\), giving the left side. Count by \((x,y)\). If \(x=y\), choose this element in \(n\) ways and choose the rest of \(S\) freely: \(2^{n-1}\). If \(x e y\), choose the ordered pair in \(n(n-1)\) ways and the remaining \(n-2\) elements freely: \(2^{n-2}\). Total: \(n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}\).

By lines, there are \(9\cdot5=45\) incidences. If there are \(N\) points, counting by points gives \(3N\). Thus \(3N=45\), so \(N=15\).

Assume any two chosen triples share at most one element. Then no pair of elements can occur in two different triples; otherwise those two triples would share that pair, i.e. two common elements. Each triple contains \(3\) pairs, so \(17\) triples would contain \(51\) distinct element-pairs. But a \(10\)-element set has only \(10\cdot9/2=45\) pairs. Contradiction. Hence two triples share at least two elements.

There are \(12\) months and \(13\) people. By the pigeonhole principle, some month contains at least two birthdays.

The boxes are last digits \(0,1,\ldots,9\). There are \(11\) numbers, so two fall into the same box.

Assume no color appears three times. Then each color appears at most \(2\), so there are at most \(4\) socks, but we have \(5\). Contradiction.

There are \(n\) residues modulo \(n\). Among \(n+1\) numbers, two have the same residue. Their difference is divisible by \(n\).

Pairs: \((1,10),(2,9),(3,8),(4,7),(5,6)\). Six numbers are chosen and there are five pairs, so one pair is fully chosen. Its sum is \(11\).

There are \(8\) residue classes. If each contains at most \(2\) numbers, the total is at most \(16\), but there are \(17\). Hence some class contains at least \(3\).

Each person has \(0\) to \(5\) acquaintances. If someone has \(0\), no one has \(5\); if someone has \(5\), no one has \(0\). Thus at most \(5\) values are possible for \(6\) people. By pigeonhole, two values coincide.

Each number has the form \(2^k m\), where \(m\) is odd. There are only \(9\) possible odd parts in \(1,\ldots,18\). Among \(10\) chosen numbers, two have the same odd part. Then they are \(2^a m\) and \(2^b m\), and the smaller divides the larger.

There are \(100\) residues modulo \(100\). Among \(101\) integers, two have the same residue, so their difference is divisible by \(100\).

There are \(10\) pairs, each with sum \(21\). Since \(11\) numbers are chosen, one pair is fully chosen.

After dividing into \(4\) unit squares, \(5\) points force two points into one small square. The distance between any two points in a unit square is at most its diagonal \(\sqrt{2}\).

Let \(s_i\) be the sum of the first \(i\) numbers. If some \(s_i\) is divisible by \(10\), done. Otherwise the \(10\) partial sums have only \(9\) nonzero residues, so two have the same residue. Their difference is the sum of a consecutive block divisible by \(10\).

Consider \(s_1,\ldots,s_n\). If some \(s_i\equiv0\pmod n\), the first \(i\) numbers work. Otherwise all \(s_i\) have one of \(n-1\) nonzero residues. Two sums have the same residue; their difference is the sum of a nonempty consecutive block and is divisible by \(n\).

There are \(6\) boxes of residues: \(0\), \(5\), and opposite residue pairs. Seven numbers put two in the same box. If their residues are equal, the difference is divisible by \(10\). If opposite, the sum is divisible by \(10\).

Each point has parity type \((x\bmod2,y\bmod2)\), only \(4\) types. Among \(5\) points, two have the same type. Then the sums of their \(x\)-coordinates and \(y\)-coordinates are even, so the midpoint has integer coordinates.

Choose a person \(A\). Among the other \(5\), either \(3\) are acquainted with \(A\), or \(3\) are not. In the first case, if among those three there is an acquainted pair, together with \(A\) they form three mutual acquaintances; if not, those three are mutual strangers. The second case is analogous: if among three strangers to \(A\) there is a stranger pair, together with \(A\) they form three mutual strangers; otherwise those three are mutual acquaintances.

Join the midpoints of the sides to obtain \(4\) small equilateral triangles of side \(1\). Five points force two into one small triangle. The distance between any two points in such a triangle is at most \(1\).

There are \(50\) pairs of consecutive numbers. Since \(51\) numbers are chosen, one pair is fully chosen. These two numbers are consecutive.

There are \(5\) residues modulo \(5\). Among \(6\) integers, two have the same residue, so their difference is divisible by \(5\).

There are \(2^{10}-1=1023\) nonempty subsets. Any subset sum lies between \(1\) and \(1000\), so there are at most \(1000\) possible sums. By pigeonhole, two different nonempty groups have the same sum.

There are \(1023\) nonempty subsets. Their sums lie from \(1\) to \(990\), at most \(990\) possible sums. Thus two different nonempty subsets have equal sum. Remove their common elements. The remaining parts still have equal sums; they are not both empty, otherwise the original subsets were equal. Hence we get two nonempty disjoint groups with equal sum.

Choose any person \(A\). Among the other \(9\), each is either acquainted with \(A\) or not. There are two boxes: acquaintances and strangers. By the strengthened pigeonhole principle, one contains at least \(\lceil9/2 ceil=5\) people. Thus \(A\) has \(5\) acquaintances or \(5\) strangers.

List the numbers in any order and apply the partial-sum lemma to this sequence of length \(n\). We get a nonempty consecutive block whose sum is divisible by \(n\). This block is a subset of the chosen numbers.

For each number \(a_i\), write \((u_i,d_i)\), where \(u_i\) is the maximum length of an increasing subsequence starting at \(a_i\), and \(d_i\) the maximum length of a decreasing one. If there is no monotone subsequence of length \(4\), then \(u_i,d_i\in\{1,2,3\}\), only \(9\) pairs. Among \(10\) numbers, two pairs coincide; let \(iu_j\), contradiction. If \(a_i>a_j\), similarly \(d_i>d_j\). Contradiction.

The initial number is even, and adding \(2\) preserves parity. The number \(99\) is odd, so it cannot be obtained.

The number of heads changes by \(-2\), \(0\), or \(2\), so its parity is preserved. It starts at \(9\) and would need to become \(0\). Odd cannot become even.

Initially there are \(15\) stones, while the target has \(20\). Since moving a stone does not change the total, the target is impossible.

The residue modulo \(3\) is preserved. \(5\equiv2\pmod3\), while \(100\equiv1\pmod3\). Therefore \(100\) cannot be obtained.

Changing two signs changes the number of minuses by \(-2\), \(0\), or \(2\). Its parity is preserved. Initially it is \(0\), but the target is \(3\), impossible.

Changing two signs multiplies the product by \((-1)^2=1\). Initially the product is \(+1\). With \(7\) minuses, the product is \(-1\). Impossible.

Initially there are \(14\) tokens, while the target has \(15\). Moving a token preserves the total, so the target is impossible.

If \(h\) heads are among the flipped coins, the number of heads changes by \(4-2h\), an even number. Parity is preserved. Initially \(15\) is odd; \(2\) is even. Impossible.

The initial sum is \(11\), the target sum is \(15\). The operation preserves the sum, so it is impossible.

In chessboard coloring, diagonally adjacent squares have the same color. Thus the token's color is preserved. It cannot move from black to white.

Changing \(4\) signs multiplies the product by \((-1)^4=1\). Initially the product is \(+1\), while with one minus it is \(-1\). Impossible.

In one move, the sum changes by \(1+1-2=0\). Thus the sum itself is preserved, and therefore its residue modulo \(3\) is preserved.

If \(h\) of the chosen lamps are on, the number of on lamps changes by \(100-2h\), an even number. Initially \(0\) lamps are on, even; finally \(2025\) would be on, odd. Impossible.

In one move, the total number of tokens changes by \(4-1=3\), so its residue modulo \(3\) does not change.

The original board has \(32\) black and \(32\) white cells. Opposite corners have the same color, so after removal there are \(30\) cells of one color and \(32\) of the other. Each domino covers one black and one white cell, so tiling is impossible.

Each move changes \(4\) signs, so the product of all \(16\) signs is multiplied by \((-1)^4=1\). Initially the product is \(+1\). With exactly one minus, it is \(-1\). Impossible.

The sum \(1+2+\cdots+10=55\) is odd. Changing the sign of \(a\) changes the sum by \(-2a\), an even number. Thus the parity of the sum remains odd. Zero is even, so it is impossible.

A knight move changes the square color. After an odd number of moves, the color is opposite to the initial one. Since \(2025\) is odd, the knight is on a black square, not white.

Parity is preserved because even numbers are added. The initial number \(1\) is odd, while \(100\) is even. Impossible.

Each move increases \(x+y\) by \(3\). Thus \(x+y\) modulo \(3\) is preserved and equals \(0\). At \((10,10)\), the coordinate sum is \(20\equiv2\pmod3\). It cannot be reached.

The product of all \(36\) entries is preserved: one move multiplies it by \((-1)^6=1\). Initially the product is \(1\). A table with one \(-1\) has product \(-1\). Thus it is unreachable.

Every knight move changes the square color. After \(15\) moves, since \(15\) is odd, the knight is on the opposite color. The starting square is black, so it cannot return to it.

One move changes the sum by \(2+2-1=3\), so the sum modulo \(3\) is preserved. Initially the sum is \(3\equiv0\pmod3\), finally \(30\equiv0\pmod3\), so this invariant does not forbid it. In fact the state is reachable: apply three moves, subtracting from a different coordinate each time; all coordinates increase by \(3\). Repeating this three-move cycle three times gives \((10,10,10)\).

The initial number of inversions is \(0\). Each adjacent swap changes inversion parity. After \(27\) moves, inversion parity would be odd. But in \(87654321\), the number of inversions is \(C(8,2)=28\), which is even. Contradiction; exactly \(27\) moves are impossible.

The board has area \(25\), while each domino has area \(2\). The total area covered by dominoes is always even, so an area of \(25\) cannot be tiled.

The full \(6\times6\) board has equal numbers of black and white cells. Removing two cells of the same color destroys this equality. But every domino covers one black and one white cell, so any domino tiling would cover equal numbers of the two colors. Contradiction.

On a \(7\times7\) board, the corner color occurs \(25\) times and the other color \(24\) times. Dominoes cover equal numbers of the two colors. Hence the remaining cell must have the color that occurred one more time, the corner color.

Every knight move changes the square color. After an odd number of moves the color is opposite to the initial one. Since \(9\) is odd, the knight is on a white square. It cannot be on black after \(9\) moves.

Under the coloring by \(i+j\pmod3\), every straight tromino covers one cell of each color. On the \(5\times5\) board, colors \(0,1,2\) occur \(9,8,8\) times. The cell \((1,1)\) has color \(2\), so after removing it the counts become \(9,8,7\). They are not equal, so no tiling exists.

In chessboard coloring, opposite corners of an \(8\times8\) board have the same color. After removing them, one color has two fewer cells than the other. Each domino covers one cell of each color, so the remaining region cannot be tiled.

In chessboard coloring, cell \((i,i)\) always has the same color because \(i+i\) is even. Thus \(8\) cells of one color are removed. The full board had equal color counts, and after removal they are unequal. Dominoes cover colors equally, so tiling is impossible.

Color the columns alternately in two colors. A horizontal domino covers one cell of each column color, while a vertical domino covers two cells of one column color. The board has \(18\) cells of each color. Horizontal dominoes keep the balance, so vertical dominoes must contribute equal numbers of cells of the two colors. Thus the number of vertical dominoes in the two types of columns must be equal. But their total is \(5\), impossible.

Under the coloring \((i,j)\mapsto i+j\pmod3\), every straight tromino covers one cell of each color. On a \(7\times7\) board, colors \(0,1,2\) occur \(16,16,17\) times. The cell \((1,2)\) has color \(0\), so after removal the counts are \(15,16,17\). They are not equal, so the remaining region cannot be tiled by straight trominoes.

Under coloring by \(i+j\pmod4\), each straight tetromino covers one cell of each of the four colors. On the \(5\times5\) board, colors \(0,1,2,3\) occur \(6,6,7,6\) times. The cell \((1,2)\) has color \(3\), so after removing it the counts are \(6,6,7,5\). They are not equal, so no tiling exists.

Opposite corners of a \(4\times4\) board have the same color. But every knight move changes color, so after \(15\) moves, an odd number, the knight must be on the opposite color. Therefore it cannot finish in the opposite corner.

Since \(mn\) is odd, one color occurs one more time in chessboard coloring. Dominoes cover one cell of each color. Hence after all domino-covered cells are removed, the remaining cell must have the majority color.

In chessboard coloring, all cells on the main diagonal have the same color. The full \(10\times10\) board has equal color counts, and after removing \(10\) cells of one color the equality is broken. A domino always covers one cell of each color, so tiling is impossible.

Under the coloring \((i,j)\mapsto i+j\pmod3\), every tromino covers one cell of each color. Thus \(21\) trominoes cover \(21\) cells of each color. On the \(8\times8\) board, colors \(0,1,2\) occur \(22,21,21\) times. Therefore the single cell must have color \(0\). But \((1,1)\) has color \(2\), and \((8,8)\) has color \(16\equiv1\pmod3\). Neither can be the single cell.

Color the columns alternately. A horizontal domino always covers one cell of each column color. A vertical domino covers two cells of one color. Since the board has equal color counts, vertical dominoes must be split equally between the two types of columns. Their number must be even. Since \(17\) is odd, such a tiling is impossible.

Color the board as a chessboard. Every knight move changes color, so the knight graph is bipartite: all edges go between the two colors. A closed tour through \(25\) cells would be a cycle of length \(25\). But every cycle in a bipartite graph has even length, because colors alternate. Contradiction.

On a \(9\times9\) board, the corner color occurs \(41\) times and the other color \(40\) times. All dominoes together cover equal numbers of the two colors. The one remaining cell, covered by the monomino, must have the majority color, the corner color.

Color cell \((i,j)\) by \(i+j\pmod4\). A straight tetromino covers one cell of each color. On the full \(8\times8\) board each color occurs \(16\) times. On the main diagonal the colors alternate only between \(0\) and \(2\): four cells of color \(0\) and four of color \(2\) are removed, while colors \(1\) and \(3\) are not removed. The remaining counts are \(12,16,12,16\), not all equal. Hence no tiling exists.

Under coloring by \(i+j\pmod3\), every straight tromino covers one cell of each color. Thus \(16\) trominoes cover \(16\) cells of each color. On the \(7\times7\) board the color counts are \(16,16,17\), with the extra color being \(2\). Therefore the monomino must stand on a cell of color \(2\), meaning \(i+j\equiv2\pmod3\).

The full \(8\times8\) board has \(32\) cells of each color. Dominoes cover equal numbers of black and white cells. If one uncovered cell were black and the other white, the covered cells would include \(31\) black and \(31\) white cells, which is consistent. Thus the proposed statement is false: the two uncovered cells may have different colors. For example, leave two adjacent cells and tile the rest. Therefore the correct conclusion is that coloring does not force the two cells to have the same color.

Color cell \((i,j)\) by \(i+j\pmod4\). Each straight tetromino covers one cell of each color. On the full \(8\times8\) board each color occurs \(16\) times. The corners have colors \(2,1,1,0\), so after removal the counts are \(15,14,15,16\). These are not equal, so the region cannot be split into pieces each taking one cell of each color.

Color cell \((i,j)\) by \(i+j\pmod4\). Each straight tetromino covers one cell of each color, so \(20\) tetrominoes cover \(20\) cells of each color. On the \(9\times9\) board, the counts of colors \(0,1,2,3\) are \(20,20,21,20\). Hence the single monomino must cover the extra cell of color \(2\).

Color the columns alternately. As before, horizontal dominoes cover one cell of each color, while vertical dominoes cover two cells of one color. Since the whole board has equal color counts, vertical dominoes must be split equally between the two types of columns. Hence their total number is even. Thus an odd number of vertical dominoes is impossible. Example with \(16\): tile the first four columns entirely by vertical dominoes, giving \(16\) vertical dominoes; tile the remaining four columns by horizontal dominoes along rows.

Color cell \((i,j)\) by the residue \(i+j\pmod4\). Any straight tetromino covers one cell of each of the four colors. On the full \(10\times10\) board, the counts of colors \(0,1,2,3\) are \(25,24,25,26\). On the main diagonal \((i,i)\), colors alternate between \(2\) and \(0\), so \(5\) cells of color \(0\) and \(5\) cells of color \(2\) are removed. On the other diagonal \((i,11-i)\), the sum of indices is \(11\), so all these \(10\) cells have color \(3\). After removal the counts are \(20,24,20,16\). They are not equal. But a tiling by straight tetrominoes would require equal numbers of all four colors. Contradiction.

With moves \(1\) or \(2\), the losing positions are \(0,3,6,9,12,\ldots\). From a multiple of \(3\), every move leaves a non-multiple, while from any other residue one can leave a multiple of \(3\). Since \(14\equiv2\pmod3\), the first player takes \(2\) stones and leaves \(12\). Then the first player complements each opponent move to \(3\) stones.

The losing positions are multiples of \(4\). Since \(20\) is divisible by \(4\), the first player is in a losing position. Whatever the first player takes, the second takes enough to make the two moves remove \(4\) stones. Therefore the second player makes the last move.

The first player first adds \(1\). After an opponent move of \(a\), where \(1\le a\le4\), the first player adds \(5-a\). Then after the first player’s moves the totals are \(1,6,11,16,21\). Therefore the first player wins.

After each first-player move, the second player takes the same number of stones from the other pile. Thus after the second player’s move the piles are equal again. If the first player could take stones from one pile, the other pile had the same number of stones, so the response is legal. Hence the second player will not run out of moves before the first and will make the last move.

The first player places a token in the center. All other cells split into centrally symmetric pairs. If the second player places a token in one cell of a pair, the first player places a token in the other. Thus the first player always responds and makes the last move.

Since one may take from \(1\) to \(4\), the losing positions are multiples of \(5\). The number \(37\) has residue \(2\) modulo \(5\). The first player takes \(2\) stones and leaves \(35\). After that, if the opponent takes \(a\), the first player takes \(5-a\), again leaving a multiple of \(5\).

If one stone remains, the player to move loses. Then losing positions repeat every \(4\): \(1,5,9,\ldots\). Since \(28\equiv0\pmod4\), the first player takes \(3\) stones and leaves \(25\equiv1\pmod4\). Then the first player complements each opponent move to \(4\), until the opponent is left with one stone.

Since \(50\equiv1\pmod7\), the first player starts with \(1\). If the second adds \(a\), the first adds \(7-a\). Then after the first player’s moves the total increases by \(7\): \(1,8,15,22,29,36,43,50\). The first player wins.

The second player pairs the numbers as \((1,20),(2,19),\ldots,(10,11)\). Whenever the first player takes a number from a pair, the second takes the other number in that pair. Each pair sums to \(21\), and each player gets exactly one number from each pair. Therefore the final sums are equal.

After the first player’s move, the second places a domino on the cells centrally symmetric to those just occupied. On a \(6\times6\) board, no domino coincides with its central reflection, and the reflection of adjacent cells is again adjacent. If the reflected cells had already been occupied, then by symmetry the cells of the first player’s move would also have been occupied, impossible. Hence the response is always legal, and the second player makes the last move.

After \(k\) moves, exactly \(k\) rows and \(k\) columns are occupied. If \(k<7\), a free row and a free column remain, and a rook can be placed at their intersection. Thus the game always lasts exactly \(7\) moves. The seventh move is made by the first player, so the first player wins.

Initially there is \(1\) piece, and at the end there must be \(24\) unit squares. Each move increases the number of pieces by exactly \(1\). Therefore there are \(24-1=23\) moves. The odd-numbered last move is made by the first player, so the first player wins.

Positions with equal piles are losing: the opponent can copy the move in the other pile. Therefore the first player should reduce the pile \(17\) to \(12\), taking \(5\) stones. After that, every second-player move is copied in the other pile, and the first player wins.

Multiples of \(3\) are losing: from such a position, moves \(1,2,4\) lead to residues \(2,1,2\) modulo \(3\), while from any non-multiple of \(3\) one can take \(1\) or \(2\) to leave a multiple of \(3\). Since \(30\) is divisible by \(3\), the first player loses with perfect play.

Check positions with residues \(0\) and \(2\) modulo \(7\). From them, moves \(1,3,4\) never lead again to residues \(0\) or \(2\). From every other residue one can move to \(0\) or \(2\): from \(1\) take \(1\), from \(3\) take \(1\), from \(4\) take \(4\), from \(5\) take \(3\), from \(6\) take \(4\). Thus the losing positions are residues \(0\) and \(2\) modulo \(7\). Since \(31\equiv3\pmod7\), the first player takes \(1\) stone and leaves \(30\equiv2\pmod7\).

After each first-player move of \(a\), the second player adds \(10-a\). Then after the second player’s moves the totals are \(10,20,30,\ldots,100\). Therefore the second player reaches \(100\) and wins.