Competition problem — Number theory

Library / /16 of 520

Number theory Difficulty 5.6 AIME, harder Find the answer

1 Let $X=\{1,2,3, \cdots, 1993\}, A$ be a subset of $X$ , and satisfy: (1) For any two numbers $x \neq y$ in $A$ , 93 does not divide $x \pm y$ . (2) $S(A)=1993$ . Find the maximum value of $|A|$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. Divide $X$ into 47 subsets: $A_{i}=\{x \mid x \equiv i$ , or $x \equiv 93-i(\bmod 93)\}$ , $i=0,1,2, \cdots, 46$ . For any $x, y \in A_{i}$ , we have $x-y \equiv 0(\bmod 93)$ , or $x+y \equiv$ $0(\bmod 93)$ , so $A$ can contain at most one number from $A_{i}$ . Therefore, $|A| \leqslant 47$ . Let $A=\{10$ , $11, \cdots, 46\} \cup\{93,94, \cdots, 101\} \cup\{84\}$ , then $A$ meets the requirement. Hence, the maximum value of $|A|$ is 47.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.