1991 IMO Problems/Problem 3

Problem

Let $S = \{1,2,3,\cdots ,280\}$ . Find the smallest integer $n$ such that each $n$ -element subset of $S$ contains five numbers which are pairwise relatively prime.

Solution 1

Let's look at this another way. We aim to find the least number of integers we can remove from S to leave a set which does not contain 5 pairwise coprime integers.

Let $S_p = \{p^k | p^k \leq 280\}$ And more generally $S_{p_1,p_2,...,p_l} = \{n = p_1^{q_1}p_2^{q_2}....p_l^{q_l}| n \leq 280 \}$ And finally $S_1 = \{1\}$ It is clear that these sets taken over all collections of primes and 1 forms a partition of S.

If there are representatives from five sets $S_p$ , there are five mutually coprime integers, so all but four of the sets $S_p$ must be completely removed. It is clear that (with the exception of 1, which can clearly be removed first) if $p>q, |S_p| \leq |S_q|$ so it is worth removing $S_p$ before removing $S_q$ (if we are striving for a minimum). Furthermore, if we remove two sets $S_p, S_q$ , we must also (to stop there from being 5 mutually coprime integers) remove $S_{p,q}$ and so on, and these have similar ordering relations. So once we have removed everything we need to keeping sizes of sets removed to a minimum, we are left with $S_2,S_3,S_5,S_7$ and the multi-index sets not coprime to all of these. In other words, we have the set of multiples of 2,3,5 and 7, which can be calculated (by lots of inclusion-exclusion) to have cardinality $216$ . Therefore, a subset of $S$ of size $217$ must contain 5 coprime integers.

This solution was posted and copyrighted by Ilthigore. The original thread for this problem can be found here: [1] Firstly note that $\lfloor\sqrt{280}\rfloor = 16$ . Therefore, we only need to check primes $p\le 16$ to check if a number from $1$ to $280$ is prime.

Solution 2

I claim the answer is $\boxed{217}$ . First, let's look at a subset of $S$ that consists only of multiples of $2,3,5,7$ . It is easy to calculate by PIE that the total number of elements in this set is $\left\lfloor\tfrac{280}{2}\right\rfloor+\left\lfloor\tfrac{280}{7}\right\rfloor+\left\lfloor\tfrac{280}{3}\right\rfloor+\left\lfloor\tfrac{280}{5}\right\rfloor-\left\lfloor\tfrac{280}{14}\right\rfloor-\left\lfloor\tfrac{280}{6}\right\rfloor-\left\lfloor\tfrac{280}{10}\right\rfloor-\left\lfloor\tfrac{280}{15}\right\rfloor-\left\lfloor\tfrac{280}{21}\right\rfloor-\left\lfloor\tfrac{280}{35}\right\rfloor+\left\lfloor\tfrac{280}{70}\right\rfloor+\left\lfloor\tfrac{280}{105}\right\rfloor+\left\lfloor\tfrac{280}{42}\right\rfloor+\left\lfloor\tfrac{280}{30}\right\rfloor-\left\lfloor\tfrac{280}{210}\right\rfloor=216.$ Now, note that no matter what $5$ element subset we consider of this subset we just made, consisting of multiples of $2,3,5,7$ , we will always have at least $2$ of those elements that exist in the subset that share a factor greater than $1$ by the Pigeonhole Principle since $\left\lfloor\tfrac{5}{4}\right\rfloor+1=2$ . Thus, we know $n>216$ from this. We also know that there are $212$ composite numbers and $4$ prime numbers (obviously just $2,3,5,7$ ) in this subset of $S$ . Now we do casework on the numbers $11,13$ (we don't have to check higher numbers because remember $p\le 16$ !) to find the other composite numbers. We find that all of numbers, $121,143,169,187,209,221,247,253$ fills in the rest of the composite numbers from $1$ to $280$ . This gives a total of $8$ numbers when counted. So we can now count up the total as $220$ composite numbers and the remaining must be prime so $59$ prime numbers ( $1$ not included as prime or composite). Now suppose $X$ is a subset of our set $S$ such that $|X|=217$ ( $|X|$ represents its cardinality or the number of elements in the subset $X$ ). Also suppose that there is no $5$ element subset of $X$ such that all $5$ elements are relatively prime to each other. This means we would have to have at most $4$ prime numbers and at least $213$ composite numbers to make this subset $X$ . This means the set $S-X$ (everything that is in $S$ but not in $X$ ) has at most $220-213=7$ composite numbers. Now consider the following $8$ sets and notice that at least one of these must be a subset of $X$ !: $\{2^2,3^2,5^2,7^2,13^2\}$ $\{2\times31,3\times29,5\times23,7\times19,11\times17\}$ $\{2\times47,3\times43,5\times41,7\times37,13\times19\}$ $\{2\times41,3\times37,5\times31,7\times29,11\times23\}$ $\{2\times23,3\times19,5\times17,7\times13,11^2\}$ $\{2\times43,3\times41,5\times37,7\times31,13\times17\}$ $\{2\times37,3\times31,5\times29,7\times23,11\times19\}$ $\{2\times29,3\times23,5\times19,7\times17,11\times13\}$ And obviously each of these sets has $5$ elements that are all relatively prime numbers, as desired.

This solution was posted and copyrighted by Wave-Particle. The original thread for this problem can be found here: [2]

1991 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

1991 IMO Problems/Problem 3

Contents

Problem

Solution 1

Solution 2

See Also