سوال ۱۱۶ کنکور ارشد علوم کامپیوتر ۱۴۰۱

We count strings of length $n$ over the $5$-letter alphabet $\{0,1,2,3,4\}$ in which the number of positions holding a $0$ or a $1$ is even.

Split the alphabet into two groups.

• Marked symbols: $\{0,1\}$ — there are $2$ of them.
• Unmarked symbols: $\{2,3,4\}$ — there are $3$ of them.

The condition only cares about how many positions are marked; the actual identities of marked/unmarked symbols are free. If exactly $k$ of the $n$ positions are marked, the number of such strings is

$\binom{n}{k}\,2^{k}\,3^{\,n-k}.$

We need $k$ even, so the answer is

$N=\sum_{\substack{k=0\\ k\ \text{even}}}^{n}\binom{n}{k}\,2^{k}\,3^{\,n-k}.$

Extract the even-index sum with the $\pm$ trick. For any $a,b$,

$(b+a)^n=\sum_{k}\binom{n}{k}a^{k}b^{\,n-k},\qquad (b-a)^n=\sum_{k}\binom{n}{k}(-1)^k a^{k}b^{\,n-k}.$

Adding these cancels every odd $k$ term and doubles every even $k$ term:

$\sum_{k\ \text{even}}\binom{n}{k}a^{k}b^{\,n-k}=\frac{(b+a)^n+(b-a)^n}{2}.$

Plug in $a=2$ (marked) and $b=3$ (unmarked):

$N=\frac{(3+2)^n+(3-2)^n}{2}=\frac{5^{\,n}+1^{\,n}}{2}=\frac{5^{\,n}+1}{2}.$

This is option 1.

Sanity checks.

• $n=1$: only $\{2,3,4\}$ have an even (zero) count of marked symbols $\Rightarrow 3$ strings. Formula: $\tfrac{5+1}{2}=3$. ✓
• $n=2$: $\tfrac{25+1}{2}=13$. Direct: $0$ marked gives $3^2=9$, $2$ marked gives $2^2=4$, total $13$. ✓

Exam trick: To count arrangements where a subset of symbols must occur an even number of times, collapse the alphabet into "marked" ($a$ choices) and "unmarked" ($b$ choices), then read off the even part of $(a+b)^n$ as $\dfrac{(a+b)^n+(b-a)^n}{2}$. Here it instantly gives $\dfrac{5^n+1}{2}$.