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

We work modulo $49 = 7^2$. For distinct $x,y,z \in \{1,\ldots,49\}$, no single difference can be divisible by $49$ (two numbers congruent mod $49$ in this range would be equal). So $49 \mid (x-y)(y-z)(z-x)$ requires at least two of the three differences to be divisible by $7$.

With three numbers, if two pairwise differences are divisible by $7$ then so is the third: if $x \equiv y$ and $y \equiv z \pmod 7$, then $x \equiv z \pmod 7$. Hence the product is divisible by $49$ exactly when all three numbers lie in the same residue class mod $7$ (then $7^3 \mid$ product).

Now partition $\{1,2,\ldots,49\}$ into the $7$ residue classes mod $7$. Each class has exactly $7$ elements.

$|\{k : 1 \le k \le 49,\ k \equiv r \pmod 7\}| = 7 \quad \text{for each } r \in \{0,1,\ldots,6\}.$

Largest "bad" subset (no valid triple). A subset avoids a same-class triple iff it takes at most $2$ elements from each class. The maximum such subset has

$7 \text{ classes} \times 2 = 14 \text{ elements},$

and a $14$-element example (two per class) really has no valid triple. So $n = 14$ does not force a triple.

Pigeonhole. Any subset of size $15$ has, by the pigeonhole principle, some residue class with at least $\lceil 15/7 \rceil = 3$ elements — three numbers congruent mod $7$, giving $49 \mid (x-y)(y-z)(z-x)$.

Therefore the smallest guaranteeing value is $n = 15$, option (2).

Exam trick: Reduce the divisibility condition to a coloring: "product of differences divisible by $7^2$" $\iff$ "three points share a color mod $7$." Then it is just $2$-per-class extremal counting plus pigeonhole; the smallest forcing $n$ is (max bad size) $+1 = 14 + 1 = 15$.