Competition problem — Combinatorics

Library / /18 of 133

Combinatorics Difficulty 4.9 AIME Prove it Saudi Arabia

Let $\mathbb{N}$ denote the set of positive integers, and let $S$ be a set. There exists a function $f: \mathbb{N} \rightarrow S$ such that if $x$ and $y$ are a pair of positive integers with their difference being a prime number, then $f(x) \neq f(y)$ . Determine the minimum number of elements in $S$ .

Solution

Let $f: \mathbb{N} \rightarrow S$ be such a function. Because the difference of any two numbers in $\{1, 3, 6, 8\}$ is a prime number, the cardinality of $\{f(1), f(3), f(6), f(8)\}$ is $4$ . Hence, the minimum number of elements in $S$ is greater than or equal to $4$ .

Now, consider the function $f: \mathbb{N} \rightarrow \{0, 1, 2, 3\}$ that associates to each $n \in \mathbb{N}$ its remainder when divided by $4$ . This function satisfies the condition of the problem since when $f(n_1) = f(n_2)$ , for $n_1, n_2 \in \mathbb{N}$ , then $n_1 - n_2$ is not a prime number since it is a multiple of $4$ . Therefore, the minimum number of elements in $S$ is $4$ .

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.