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

We must choose $3$ of the $5$ children and give each of them one distinct prize out of $\{1,2,3,4,5,6\}$, so that no child receives a prize they dislike. So $X$ counts injective assignments (a system of distinct representatives) of prizes to a chosen trio of children, respecting the forbidden prizes.

Allowed prizes per child (out of $6$):

Children $C$ and $E$ are unrestricted; only $A$, $B$, $D$ carry constraints. There are $\binom{5}{3}=10$ possible trios. For each trio we count assignments of $3$ distinct prizes by placing the most restricted child first.

Method (place restricted children first). For a trio, pick the prize for the tightest child, then the next, then the freest, each time subtracting the prizes already used. For example, trio $\{A,B,C\}$: assign $A$ first ($4$ choices), then $B$ from its $5$ allowed minus possibly the one $A$ took, then $C$ from the remaining. Counting carefully (or by the permanent of the $0/1$ allowed-matrix) gives the per-trio totals:

For instance, $\{B,C,E\}$ has only $B$ restricted: total ordered injections of $3$ distinct prizes to $3$ children is $6\cdot5\cdot4=120$; subtract those giving prize $2$ to $B$ ($1\cdot5\cdot4=20$), leaving $100$. And $\{A,C,E\}$: total $120$ minus the $2\cdot5\cdot4=40$ that hand $A$ a forbidden $2$ or $3$, giving $80$.

Sum:

$X = 64+37+64+44+80+44+52+100+52+60 = 597.$

Since $597 \in [300, 600]$, the answer is option 1.

Pitfall: "Each child gets at least one prize" is automatic here — exactly $3$ prizes go to exactly $3$ children, one each. Don't drift into distributing all six prizes; the question asks for assigning three prizes (a one-to-one matching), so it is a counting-with-forbidden-positions problem, not a surjection count.