Combinatorics Problems: Very Difficult Problems with Solutions

Solution:
Every natural number can be written uniquely as [tex]2^k m[/tex], where [tex]k\ge 0[/tex] is an integer and [tex]m[/tex] is odd; we call [tex]m[/tex] the odd part of the number.
The odd part of a number from [tex]\{1, 2, \ldots, 2n\}[/tex] does not exceed the number itself, so it is one of the [tex]n[/tex] odd numbers [tex]1, 3, 5, \ldots, 2n-1[/tex].
There are [tex]n+1[/tex] chosen numbers and only [tex]n[/tex] possible odd parts, so by the pigeonhole principle two of the chosen numbers, say [tex]a\lt b[/tex], have the same odd part [tex]m[/tex]:
[tex]a=2^k m, \quad b=2^l m, \quad a\lt b\ \Rightarrow\ k\lt l\ \Rightarrow\ b=2^{l-k}\times a[/tex]
Hence [tex]a[/tex] divides [tex]b[/tex], which proves the statement.

Solution:
Let the numbers be [tex]a_1\lt a_2\lt \ldots\lt a_{102}[/tex], all from the set [tex]\{1, 2, \ldots, 200\}[/tex]. Consider the [tex]101[/tex] numbers
[tex]a_2-a_1, a_3-a_1, \ldots, a_{102}-a_1[/tex]
which are pairwise different and lie between [tex]1[/tex] and [tex]199[/tex], and the [tex]101[/tex] numbers
[tex]a_2, a_3, \ldots, a_{102}[/tex]
which are pairwise different and lie between [tex]2[/tex] and [tex]200[/tex]. Together these are [tex]202[/tex] numbers from a set with only [tex]200[/tex] elements, so by the pigeonhole principle two of them are equal. They cannot belong to the same group, because within each group the numbers are different. Hence for some [tex]i, j\in\{2, 3, \ldots, 102\}[/tex] we have
[tex]a_i-a_1=a_j\ \Rightarrow\ a_1=a_i-a_j[/tex]
Here [tex]i\ne j[/tex], because [tex]a_1\gt 0[/tex] gives [tex]a_i\gt a_j[/tex], and [tex]a_i[/tex], [tex]a_j[/tex] are different from [tex]a_1[/tex], because [tex]i, j\ge 2[/tex]. Therefore the smallest number [tex]a_1[/tex] is the difference of two other given numbers.

Solution:
Write every such number with exactly five digits, adding leading zeros if necessary: [tex]n=\overline{d_1d_2d_3d_4d_5}[/tex]. This is a one-to-one correspondence between the numbers [tex]0\le n\lt 10^5[/tex] and the ordered sequences of five digits, and leading zeros do not change the digit sum. So we count the integer solutions of
[tex]d_1+d_2+d_3+d_4+d_5=12,\qquad 0\le d_i\le 9[/tex]
Without the upper bound [tex]d_i\le 9[/tex], the number of solutions in non-negative integers is (stars and bars: [tex]12[/tex] stars and [tex]4[/tex] bars)
[tex]\binom{16}{4}=1820[/tex]
Now we remove the solutions in which some digit is at least [tex]10[/tex]. Two digits cannot both be at least [tex]10[/tex], since [tex]10+10\gt 12[/tex], so these cases do not overlap. If, for example, [tex]d_1\ge 10[/tex], we put [tex]d_1=10+e_1[/tex] with [tex]e_1\ge 0[/tex]; then [tex]e_1+d_2+d_3+d_4+d_5=2[/tex], which has [tex]\binom{6}{4}=15[/tex] solutions. The same holds for each of the [tex]5[/tex] positions, so the number of bad solutions is
[tex]5\times 15=75[/tex]
Hence the required number is
[tex]1820-75=1745[/tex]

Solution:
The number of words with exactly [tex]k[/tex] letters [tex]a[/tex] is [tex]\binom{n}{k}3^{n-k}[/tex]: we choose the [tex]k[/tex] positions of the letter [tex]a[/tex], and each of the other [tex]n-k[/tex] positions holds one of the letters [tex]b, c, d[/tex].
Let [tex]E_n[/tex] and [tex]O_n[/tex] be the numbers of words with an even and with an odd number of letters [tex]a[/tex], respectively. By the binomial theorem
[tex]E_n+O_n=\sum_{k=0}^{n}\binom{n}{k}3^{n-k}=(3+1)^n=4^n[/tex]
[tex]E_n-O_n=\sum_{k=0}^{n}\binom{n}{k}(-1)^k3^{n-k}=(3-1)^n=2^n[/tex]
Subtracting the two equalities, we get
[tex]2O_n=4^n-2^n\Rightarrow O_n=\frac{4^n-2^n}{2}[/tex]
Check: for [tex]n=1[/tex] we get [tex]1[/tex] (the word [tex]a[/tex]); for [tex]n=2[/tex] we get [tex]6[/tex] (the words [tex]ab, ac, ad, ba, ca, da[/tex]).

Solution:
We must choose [tex]5[/tex] of [tex]12[/tex] places around a circle so that no two chosen places are adjacent.
Lemma. From [tex]m[/tex] objects in a row one can choose [tex]k[/tex] pairwise non-adjacent objects in [tex]\binom{m-k+1}{k}[/tex] ways. Indeed, the [tex]m-k[/tex] objects that are not chosen form [tex]m-k+1[/tex] gaps (including the two ends), and a choice without adjacent objects corresponds exactly to putting the [tex]k[/tex] chosen objects into [tex]k[/tex] different gaps, at most one per gap.
Number the knights [tex]1, 2, \ldots, 12[/tex] around the table. Case 1: knight [tex]1[/tex] is chosen. Then knights [tex]2[/tex] and [tex]12[/tex] cannot be chosen, and we must choose [tex]4[/tex] pairwise non-adjacent knights among [tex]3, 4, \ldots, 11[/tex]. These [tex]9[/tex] knights form a row (none of them is a neighbor of knight [tex]1[/tex], and knights [tex]3[/tex] and [tex]11[/tex] are not neighbors), so by the lemma the number of ways is
[tex]\binom{9-4+1}{4}=\binom{6}{4}=15[/tex]
Case 2: knight [tex]1[/tex] is not chosen. Then we choose [tex]5[/tex] pairwise non-adjacent knights among [tex]2, 3, \ldots, 12[/tex]. These [tex]11[/tex] knights form a row, since knights [tex]2[/tex] and [tex]12[/tex] are separated by knight [tex]1[/tex], so the number of ways is
[tex]\binom{11-5+1}{5}=\binom{7}{5}=21[/tex]
The two cases are disjoint, so the answer is
[tex]15+21=36[/tex]

Solution:
Introduce coordinates so that Kermit starts at [tex]\left(0, 0\right)[/tex]. He makes exactly [tex]100[/tex] jumps, and each jump changes one of the coordinates by [tex]\pm 1[/tex].
Every jump changes [tex]|x|+|y|[/tex] by at most [tex]1[/tex], so at the end [tex]|x|+|y|\le 100[/tex]. Every jump changes [tex]x+y[/tex] by [tex]\pm 1[/tex], i.e. changes its parity; after an even number of jumps the number [tex]x+y[/tex], and hence also [tex]|x|+|y|[/tex], is even.
Conversely, every node with [tex]d=|x|+|y|\le 100[/tex] and [tex]d[/tex] even is reachable: Kermit makes [tex]|x|[/tex] horizontal and [tex]|y|[/tex] vertical jumps towards it, and then spends the remaining even number [tex]100-d[/tex] of joules by jumping east and back west [tex]\frac{100-d}{2}[/tex] times.
For [tex]d\ge 1[/tex] there are exactly [tex]4d[/tex] nodes with [tex]|x|+|y|=d[/tex], and for [tex]d=0[/tex] there is one node. Writing [tex]d=2t[/tex], we get the number of possible nodes:
[tex]1+\sum_{t=1}^{50}4\times 2t=1+8\times \frac{50\times 51}{2}=1+10200=10201=101^2[/tex]

Solution:
The polynomial is
[tex]P(x)=\sum_{k=0}^{100}x^{k}(1+x)^{100-k}[/tex]
We use the identity [tex]a^{n}-b^{n}=(a-b)\left(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1}\right)[/tex] with [tex]a=1+x[/tex], [tex]b=x[/tex], [tex]n=101[/tex]. Since [tex]a-b=1[/tex], the second factor is exactly [tex]P(x)[/tex], hence
[tex]P(x)=(1+x)^{101}-x^{101}[/tex]
The term [tex]x^{101}[/tex] does not affect the coefficient of [tex]x^{50}[/tex], so by the binomial theorem this coefficient is [tex]\binom{101}{50}[/tex].
Check in another way: for [tex]k\le 50[/tex] the coefficient of [tex]x^{50}[/tex] in [tex]x^{k}(1+x)^{100-k}[/tex] is [tex]\binom{100-k}{50-k}=\binom{100-k}{50}[/tex] (for [tex]k\gt 50[/tex] it is [tex]0[/tex]), and by the hockey-stick identity [tex]\sum_{m=r}^{N}\binom{m}{r}=\binom{N+1}{r+1}[/tex]
[tex]\sum_{m=50}^{100}\binom{m}{50}=\binom{101}{51}=\binom{101}{50}[/tex]

Solution:
The prime digits are [tex]2, 3, 5, 7[/tex] (four digits); the other six digits [tex]0, 1, 4, 6, 8, 9[/tex] are not prime. There are [tex]9\times 10^6=9\,000\,000[/tex] seven-digit numbers, so we count the complement: the numbers in which no two adjacent digits are both prime.
For [tex]k=1, 2, \ldots, 7[/tex] let [tex]p_k[/tex] and [tex]q_k[/tex] be the numbers of admissible beginnings of length [tex]k[/tex] (first digit non-zero, no two adjacent prime digits) that end with a prime digit and with a non-prime digit, respectively, and let [tex]T_k=p_k+q_k[/tex]. For the first digit (the non-prime non-zero digits are [tex]1, 4, 6, 8, 9[/tex])
[tex]p_1=4,\qquad q_1=5,\qquad T_1=9[/tex]
A prime digit may follow only a non-prime digit, and a non-prime digit may follow any digit, hence
[tex]p_{k+1}=4q_k,\qquad q_{k+1}=6T_k[/tex]
Then [tex]T_2=4\times 5+6\times 9=74[/tex], and for [tex]k\ge 2[/tex]
[tex]T_{k+1}=6T_k+4q_k=6T_k+24T_{k-1}[/tex]
Therefore
[tex]T_3=6\times 74+24\times 9=660,\qquad T_4=6\times 660+24\times 74=5736[/tex]
[tex]T_5=6\times 5736+24\times 660=50\,256,\qquad T_6=6\times 50\,256+24\times 5736=439\,200[/tex]
[tex]T_7=6\times 439\,200+24\times 50\,256=3\,841\,344[/tex]
So the required number is
[tex]9\,000\,000-3\,841\,344=5\,158\,656[/tex]

Solution:
The rectangle condition means that there are no two rows and two columns whose four common cells all contain [tex]1[/tex]; in other words, any two rows have ones in at most one common column.
For each row consider the pairs of columns in which this row has ones: every row gives [tex]\binom{3}{2}=3[/tex] such pairs. If the same pair of columns appeared for two different rows, these two rows and two columns would form a rectangle with ones in all four corners (sum [tex]4[/tex]), which is forbidden. Hence all [tex]3n[/tex] pairs are different pairs of columns, so
[tex]3n\le\binom{n}{2}=\frac{n(n-1)}{2}\Rightarrow n-1\ge 6\Rightarrow n\ge 7[/tex]
For [tex]n=7[/tex] such a table exists: number the rows and the columns from [tex]1[/tex] to [tex]7[/tex], and in row [tex]i[/tex] write [tex]1[/tex] in the columns [tex]i[/tex], [tex]i+1[/tex], [tex]i+3[/tex] (taken modulo [tex]7[/tex]) and [tex]0[/tex] elsewhere. The rows contain ones in the columns
[tex]\{1, 2, 4\},\ \{2, 3, 5\},\ \{3, 4, 6\},\ \{4, 5, 7\},\ \{5, 6, 1\},\ \{6, 7, 2\},\ \{7, 1, 3\}[/tex]
Every row and every column contains exactly three ones, and any two of these sets have exactly one common element, so no rectangle has ones in all four corners. Hence the smallest possible value is [tex]n=7[/tex].

Solution:
Let [tex]\omega=-\frac{1}{2}+\frac{\sqrt{3}}{2}i[/tex]. Then
[tex]\omega^3=1,\qquad 1+\omega+\omega^2=0,\qquad 1+\omega=-\omega^2[/tex]
Since [tex]\omega^j[/tex] depends only on the remainder of [tex]j[/tex] modulo [tex]3[/tex], we have [tex]\sum_{0\lt j\lt n}\binom{n}{j}\omega^j=S_0+S_1\omega+S_2\omega^2[/tex]. By the binomial theorem [tex]\sum_{j=0}^{n}\binom{n}{j}\omega^j=(1+\omega)^n[/tex], so removing the terms with [tex]j=0[/tex] and [tex]j=n[/tex] gives
[tex]S_0+S_1\omega+S_2\omega^2=(1+\omega)^n-1-\omega^n=(-1)^n\omega^{2n}-1-\omega^n[/tex]
Claim: [tex]S_0=S_1=S_2[/tex] if and only if [tex]S_0+S_1\omega+S_2\omega^2=0[/tex]. If all three sums equal [tex]s[/tex], the left side is [tex]s(1+\omega+\omega^2)=0[/tex]. Conversely, substituting [tex]\omega^2=-1-\omega[/tex] gives [tex](S_0-S_2)+(S_1-S_2)\omega=0[/tex] with real coefficients; since [tex]\omega[/tex] is not real, [tex]S_1=S_2[/tex], and then also [tex]S_0=S_2[/tex].
So we need [tex](-1)^n\omega^{2n}=1+\omega^n[/tex]. Both sides depend only on the remainder of [tex]n[/tex] modulo [tex]6[/tex]; we compute them in the six cases:
[tex]n=6k:\quad (-1)^n\omega^{2n}=1,\quad 1+\omega^n=2[/tex]
[tex]n=6k+1:\quad (-1)^n\omega^{2n}=-\omega^2,\quad 1+\omega^n=1+\omega=-\omega^2[/tex]
[tex]n=6k+2:\quad (-1)^n\omega^{2n}=\omega^4=\omega,\quad 1+\omega^n=1+\omega^2=-\omega[/tex]
[tex]n=6k+3:\quad (-1)^n\omega^{2n}=-\omega^6=-1,\quad 1+\omega^n=1+\omega^3=2[/tex]
[tex]n=6k+4:\quad (-1)^n\omega^{2n}=\omega^8=\omega^2,\quad 1+\omega^n=1+\omega^4=1+\omega=-\omega^2[/tex]
[tex]n=6k+5:\quad (-1)^n\omega^{2n}=-\omega^{10}=-\omega,\quad 1+\omega^n=1+\omega^5=1+\omega^2=-\omega[/tex]
The two sides are equal only for [tex]n=6k+1[/tex] and [tex]n=6k+5[/tex] (for [tex]n=6k+2[/tex] and [tex]n=6k+4[/tex] they are opposite non-zero numbers). Hence the condition holds exactly for [tex]n=6k+1[/tex] and [tex]n=6k+5[/tex], [tex]k=0, 1, 2, \ldots[/tex], i.e. for the natural numbers divisible neither by [tex]2[/tex] nor by [tex]3[/tex].
Check for [tex]n=5[/tex]: [tex]S_1=\binom{5}{1}+\binom{5}{4}=10[/tex], [tex]S_2=\binom{5}{2}=10[/tex], [tex]S_0=\binom{5}{3}=10[/tex]; for [tex]n=4[/tex]: [tex]S_1=\binom{4}{1}=4[/tex], but [tex]S_2=\binom{4}{2}=6[/tex].

Solution:
Assume the contrary: every grandfather has at most [tex]13[/tex] grandchildren in the village. Take any child [tex]X[/tex] and let [tex]A[/tex] and [tex]B[/tex] be its two grandfathers. Every other child has a common grandfather with [tex]X[/tex], so every child is a grandchild of [tex]A[/tex] or of [tex]B[/tex].
Let [tex]a[/tex] and [tex]b[/tex] be the numbers of grandchildren of [tex]A[/tex] and of [tex]B[/tex] in the village, and [tex]t[/tex] the number of children who are grandchildren of both. By inclusion–exclusion
[tex]a+b-t=20\Rightarrow t=a+b-20\le 13+13-20=6[/tex]
Let [tex]P[/tex] be the set of children who are grandchildren of [tex]A[/tex] but not of [tex]B[/tex], and [tex]Q[/tex] the set of children who are grandchildren of [tex]B[/tex] but not of [tex]A[/tex]. Then
[tex]|P|=a-t=20-b\ge 7,\qquad |Q|=b-t=20-a\ge 7,\qquad |P|+|Q|=20-t\ge 14[/tex]
In particular, both sets are nonempty. Take any [tex]Y\in P[/tex] with grandfathers [tex]A[/tex] and [tex]C[/tex] (here [tex]C\ne B[/tex]) and any [tex]Z\in Q[/tex] with grandfathers [tex]B[/tex] and [tex]D[/tex] (here [tex]D\ne A[/tex]). The children [tex]Y[/tex] and [tex]Z[/tex] have a common grandfather. It is not [tex]A[/tex], because [tex]Z[/tex] is not a grandchild of [tex]A[/tex], and it is not [tex]B[/tex], because [tex]Y[/tex] is not a grandchild of [tex]B[/tex]. Therefore [tex]C=D[/tex].
Fixing [tex]Z[/tex] and letting [tex]Y[/tex] run through [tex]P[/tex], we see that all children in [tex]P[/tex] have the same second grandfather [tex]D[/tex]; fixing [tex]Y[/tex] and letting [tex]Z[/tex] run through [tex]Q[/tex], we see that all children in [tex]Q[/tex] also have the grandfather [tex]D[/tex]. So [tex]D[/tex] has at least [tex]|P|+|Q|\ge 14[/tex] grandchildren, which contradicts the assumption. Hence some grandfather has at least [tex]14[/tex] grandchildren in the village.