Combinatorics Problems: Difficult Problems with Solutions

Solution:
A collection is completely determined by the numbers [tex]a,b,c,d\ge 0[/tex] of coins of [tex]1[/tex], [tex]5[/tex], [tex]10[/tex] and [tex]20[/tex] cents, where
[tex]a+b+c+d=15[/tex]
Encode such a quadruple as a row of [tex]15[/tex] stars and [tex]3[/tex] bars: [tex]a[/tex] stars, a bar, [tex]b[/tex] stars, a bar, [tex]c[/tex] stars, a bar, [tex]d[/tex] stars. This is a bijection between the collections and the rows of [tex]18[/tex] symbols with exactly [tex]3[/tex] bars, and such a row is determined by the positions of its bars:
[tex]\binom{18}{3}=\frac{18\times 17\times 16}{6}=816[/tex]
(Equivalently, these are combinations with repetition: [tex]15[/tex] coins chosen from [tex]4[/tex] kinds, [tex]\binom{4+15-1}{15}=\binom{18}{3}[/tex].)

Solution:
Let [tex]N\gt 3.6\times 10^9[/tex] be the number of people. At most [tex]0.01N[/tex] of them are older than [tex]100[/tex] years, so the number of people who are not older than [tex]100[/tex] years is at least
[tex]0.99N\gt 0.99\times 3.6\times 10^9=3\,564\,000\,000[/tex]
The age of each of them in completed years is at most [tex]100[/tex], i.e. each of them has lived less than [tex]101[/tex] years, so all of them were born during the last [tex]101[/tex] years. A period of [tex]101[/tex] years contains at most [tex]101\times 366[/tex] days, so its length in seconds is at most
[tex]101\times 366\times 24\times 3600=3\,193\,862\,400[/tex]
Even counting the incomplete seconds at the two ends, this period meets at most [tex]3\,193\,862\,401[/tex] different clock seconds.
Regard these seconds as boxes and put each of these people into the box of the second in which he or she was born. There are more than [tex]3\,564\,000\,000[/tex] people and at most [tex]3\,193\,862\,401[/tex] boxes, so by the pigeonhole principle some box contains at least two people, i.e. these two people were born in the same second.

Solution:
The word has [tex]6[/tex] letters: O and S occur twice each, C and M once each. Without restrictions the number of arrangements (permutations with repetition) is
[tex]\frac{6!}{2!\times 2!}=180[/tex]
Let [tex]A[/tex] be the set of arrangements in which the two letters O are adjacent and [tex]B[/tex] the set of those in which the two letters S are adjacent. Gluing the two letters O into one block, we arrange [tex]5[/tex] objects among which S occurs twice; similarly for [tex]B[/tex]. If both pairs are glued, we arrange [tex]4[/tex] different objects:
[tex]|A|=\frac{5!}{2!}=60,\quad |B|=60,\quad |A\cap B|=4!=24[/tex]
By the inclusion-exclusion principle the number of “bad” arrangements is
[tex]|A\cup B|=60+60-24=96[/tex]
Therefore the required number is [tex]180-96=84[/tex].

Solution:
Without restrictions, each of the six positions can hold any of the three letters, so there are [tex]3^6=729[/tex] words.
Let [tex]A_1, A_2, A_3[/tex] be the sets of words in which the first, the second and the third letter, respectively, does not occur. Then [tex]|A_i|=2^6=64[/tex]; for [tex]i\ne j[/tex] the set [tex]A_i\cap A_j[/tex] contains only the word formed by the remaining letter, so [tex]|A_i\cap A_j|=1[/tex]; finally, [tex]A_1\cap A_2\cap A_3=\varnothing[/tex].
By the inclusion-exclusion principle the number of words in which at least one letter is missing is
[tex]|A_1\cup A_2\cup A_3|=3\times 64-3\times 1+0=189[/tex]
Hence the number of words containing all three letters is [tex]729-189=540[/tex].

Solution:
Since [tex]2187=3^7[/tex], every digit divides [tex]3^7[/tex]. The digit [tex]0[/tex] is impossible (the product is not [tex]0[/tex]), so the only possible digits are [tex]1[/tex], [tex]3[/tex] and [tex]9[/tex] ([tex]27[/tex] is not a digit).
Let the number contain [tex]a[/tex] threes, [tex]b[/tex] nines and [tex]5-a-b[/tex] ones. Then
[tex]3^a\times 9^b=3^{a+2b}=3^7\Rightarrow a+2b=7,\quad a+b\le 5[/tex]
Substituting [tex]a=7-2b[/tex] gives [tex]7-b\le 5[/tex], i.e. [tex]b\ge 2[/tex], while [tex]a\ge 0[/tex] gives [tex]b\le 3[/tex].
Case [tex]b=2[/tex], [tex]a=3[/tex]: the digits are [tex]3, 3, 3, 9, 9[/tex] and they can be arranged in [tex]\frac{5!}{3!\times 2!}=10[/tex] ways.
Case [tex]b=3[/tex], [tex]a=1[/tex]: the digits are [tex]9, 9, 9, 3, 1[/tex] and they can be arranged in [tex]\frac{5!}{3!}=20[/tex] ways.
No digit is [tex]0[/tex], so every arrangement is a five-digit number. In total there are [tex]10+20=30[/tex] such numbers.

Solution:
The general term is
[tex]T_{k+1}=\binom{n}{k}\left(\sqrt{x}\right)^{n-k}\left(\frac{1}{2\sqrt[4]{x}}\right)^{k}=\frac{1}{2^k}\binom{n}{k}x^{\frac{n-k}{2}-\frac{k}{4}}[/tex]
and the exponent of [tex]x[/tex] decreases as [tex]k[/tex] grows. For three terms to exist we need [tex]n\ge 2[/tex]. The coefficients of the first three terms ([tex]k=0, 1, 2[/tex]) are
[tex]1, \quad \frac{n}{2}, \quad \frac{1}{4}\binom{n}{2}=\frac{n(n-1)}{8}[/tex]
They form an arithmetic progression exactly when
[tex]2\times \frac{n}{2}=1+\frac{n(n-1)}{8}\iff 8n=8+n^2-n\iff n^2-9n+8=0[/tex]
with roots [tex]n=1[/tex] and [tex]n=8[/tex]. The root [tex]n=1[/tex] is rejected, because then the expansion has only two terms. For [tex]n=8[/tex] the coefficients are [tex]1, 4, 7[/tex], which is indeed an arithmetic progression. Hence [tex]n=8[/tex].

Solution:
Because of [tex]\lg x[/tex] we need [tex]x\gt 0[/tex]. The general term of [tex]\left(a+b\right)^5[/tex] is [tex]T_{k+1}=\binom{5}{k}a^{5-k}b^k[/tex]; here [tex]a=x^{\lg x}[/tex], [tex]b=x[/tex], and the third term corresponds to [tex]k=2[/tex]:
[tex]T_3=\binom{5}{2}\left(x^{\lg x}\right)^3x^2=10\,x^{3\lg x+2}[/tex]
The condition [tex]T_3=100[/tex] gives [tex]x^{3\lg x+2}=10[/tex]. Both sides are positive, so we may take logarithms to base [tex]10[/tex]:
[tex]\left(3\lg x+2\right)\lg x=1[/tex]
With [tex]u=\lg x[/tex] this becomes
[tex]3u^2+2u-1=0\Rightarrow u=\frac{1}{3}\text{ or }u=-1[/tex]
Hence [tex]x=10^{\frac{1}{3}}=\sqrt[3]{10}[/tex] or [tex]x=10^{-1}=\frac{1}{10}[/tex]; both values are positive, so both are admissible.
Check: for [tex]x=\frac{1}{10}[/tex] we have [tex]x^{\lg x}=10[/tex] and [tex]T_3=10\times 10^3\times \frac{1}{100}=100[/tex]; for [tex]x=\sqrt[3]{10}[/tex] we have [tex]T_3=10\times 10^{\frac{1}{3}}\times 10^{\frac{2}{3}}=100[/tex].

Solution:
The odd numbers occupy the odd positions, so the even numbers [tex]2, 4, 6, 8, 10[/tex] fill the even positions [tex]2, 4, 6, 8, 10[/tex], and none of them may stand in its own place. So we must find the number [tex]D_5[/tex] of permutations of [tex]5[/tex] elements in which no element is in its own place (derangements).
By inclusion-exclusion: the [tex]m[/tex] numbers that are required to stay in their places can be chosen in [tex]\binom{5}{m}[/tex] ways, and the remaining [tex]5-m[/tex] numbers can be arranged in [tex](5-m)![/tex] ways. Hence
[tex]D_5=5!-\binom{5}{1}\times 4!+\binom{5}{2}\times 3!-\binom{5}{3}\times 2!+\binom{5}{4}\times 1!-\binom{5}{5}\times 0![/tex]
[tex]D_5=120-120+60-20+5-1=44[/tex]

Solution:
Write the sum in reverse order, using [tex]\binom{n}{k}=\binom{n}{n-k}[/tex]:
[tex]S=(n+1)\binom{n}{0}+n\binom{n}{1}+\ldots+(n+1-k)\binom{n}{k}+\ldots+1\times \binom{n}{n}[/tex]
Adding the two expressions term by term, the coefficient of each [tex]\binom{n}{k}[/tex] becomes [tex](k+1)+(n+1-k)=n+2[/tex], and by the binomial theorem [tex]\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=(1+1)^n=2^n[/tex]:
[tex]2S=(n+2)\left(\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}\right)=(n+2)\times 2^n\ \Rightarrow\ S=(n+2)\times 2^{n-1}[/tex]

Solution:
Introduce coordinates so that the points are [tex]\left(x, y\right)[/tex], where [tex]x\in\{0, 1, 2, 3, 4\}[/tex], [tex]y\in\{0, 1, 2\}[/tex]. Three points are vertices of a triangle exactly when they are not collinear. The number of all triples of points is
[tex]\binom{15}{3}=455[/tex]
From this we subtract the collinear triples. The triples on one row are [tex]3\times \binom{5}{3}=30[/tex].
Any other line is not horizontal, so it meets each row in at most one point, and a collinear triple on it has one point in each row. Since their [tex]y[/tex]-coordinates are [tex]0, 1, 2[/tex], the middle point is the midpoint of the segment joining the other two, i.e. the points are [tex]\left(a, 0\right), \left(a+d, 1\right), \left(a+2d, 2\right)[/tex], where [tex]0\le a\le 4[/tex] and [tex]0\le a+2d\le 4[/tex]. This gives [tex]5[/tex] triples for [tex]d=0[/tex] (the columns), [tex]3[/tex] triples for each of [tex]d=\pm 1[/tex] and [tex]1[/tex] triple for each of [tex]d=\pm 2[/tex] ([tex]\left|d\right|\ge 3[/tex] is impossible), i.e.
[tex]5+2\times 3+2\times 1=13[/tex]
Hence there are [tex]30+13=43[/tex] collinear triples, and the number of triangles is
[tex]455-43=412[/tex]

Solution:
Factor the base:
[tex]1+x+\frac{1}{x^2}+\frac{1}{x^3}=(1+x)+\frac{1}{x^3}(x+1)=(1+x)\left(1+x^{-3}\right)[/tex]
Hence the expression equals
[tex](1+x)^6\left(1+x^{-3}\right)^6=\left(\sum_{i=0}^{6}\binom{6}{i}x^i\right)\left(\sum_{j=0}^{6}\binom{6}{j}x^{-3j}\right)[/tex]
A product of two terms gives [tex]x^0[/tex] exactly when [tex]i=3j[/tex]. Since [tex]0\le i\le 6[/tex], the possible pairs are [tex]\left(i, j\right)=\left(0, 0\right), \left(3, 1\right), \left(6, 2\right)[/tex], so the constant term is
[tex]\binom{6}{0}\binom{6}{0}+\binom{6}{3}\binom{6}{1}+\binom{6}{6}\binom{6}{2}=1+20\times 6+15=136[/tex]

Solution:
Number the horizontal grid lines [tex]0, 1, \ldots, n[/tex] from the base upwards. Line [tex]j[/tex] contains [tex]n-j+1[/tex] nodes, which we number [tex]0, 1, \ldots, n-j[/tex] from left to right (node [tex]0[/tex] lies on the left side of the big triangle).
An upward triangle of side [tex]s[/tex] is determined by its lower-left vertex. If this vertex is node [tex]i[/tex] on line [tex]j[/tex], then the lower-right vertex is node [tex]i+s[/tex] on the same line and the top vertex is node [tex]i[/tex] on line [tex]j+s[/tex]. The triangle lies in the grid exactly when
[tex]i+s\le n-j\iff i+j\le n-s, \quad i, j\ge 0[/tex]
The number of such pairs [tex]\left(i, j\right)[/tex] is [tex]1+2+\ldots+(n-s+1)=\binom{n-s+2}{2}[/tex]. Summing over [tex]s=1, 2, \ldots, n[/tex] and using [tex]\binom{k}{2}=\binom{k+1}{3}-\binom{k}{3}[/tex] (the sum telescopes), we get
[tex]N=\binom{n+1}{2}+\binom{n}{2}+\ldots+\binom{2}{2}=\binom{n+2}{3}=\frac{n(n+1)(n+2)}{6}[/tex]

Solution:
Each written number divides [tex]64=2^6[/tex], so it equals [tex]2^a[/tex] with an integer [tex]a\ge 0[/tex]. A row [tex]2^{a_1}, 2^{a_2}, \ldots, 2^{a_5}[/tex] has product [tex]64[/tex] exactly when
[tex]a_1+a_2+a_3+a_4+a_5=6, \quad a_i\ge 0[/tex]
Each such ordered solution corresponds to an arrangement of [tex]6[/tex] units and [tex]4[/tex] separators in a row (stars and bars), so the number of possible rows is
[tex]\binom{6+4}{4}=\binom{10}{4}=210[/tex]
If we choose [tex]4\times 210+1=841[/tex] students, then by the pigeonhole principle some row has been written by at least [tex]5[/tex] of them.
[tex]840[/tex] students are not enough: it may happen that each of the [tex]210[/tex] rows was written by at least [tex]4[/tex] students (this needs [tex]840\le 999[/tex] students), and if we choose exactly [tex]4[/tex] students for each row, no five of the chosen [tex]840[/tex] wrote the same row. Hence the answer is [tex]841[/tex].

Solution:
Let a candidate have [tex]c[/tex] correct and [tex]w[/tex] wrong answers, where [tex]c, w\ge 0[/tex] and [tex]c+w\le 40[/tex]; the score is [tex]s=4c-w[/tex]. For a fixed [tex]c[/tex] the number [tex]w[/tex] takes all values from [tex]0[/tex] to [tex]40-c[/tex], so [tex]s[/tex] takes all integer values in the interval
[tex]\left[5c-40, 4c\right][/tex]
The intervals for [tex]c[/tex] and [tex]c+1[/tex] leave no gap between them exactly when [tex]5(c+1)-40\le 4c+1[/tex], i.e. [tex]c\le 36[/tex]. Hence the values [tex]c=0, 1, \ldots, 37[/tex] together give all integers from [tex]-40[/tex] to [tex]4\times 37=148[/tex], i.e. [tex]189[/tex] scores. The remaining values of [tex]c[/tex] give
[tex]c=38:\ 150, 151, 152\qquad c=39:\ 155, 156\qquad c=40:\ 160[/tex]
The scores [tex]149, 153, 154, 157, 158, 159[/tex] are impossible, so the number of possible scores is
[tex]189+3+2+1=195[/tex]
With [tex]390=2\times 195[/tex] candidates it may happen that each possible score is obtained by exactly two candidates, and then no three have equal scores. With [tex]391\gt 2\times 195[/tex] candidates, by the pigeonhole principle some score is obtained by at least three of them. The answer is [tex]391[/tex].