1991 IMO Problems/Problem 3

Revision as of 17:45, 30 January 2021 by Hamstpan38825 (talk | contribs) (Created page with "==Problem== Let <math> S = \{1,2,3,\cdots ,280\}</math>. Find the smallest integer <math> n</math> such that each <math> n</math>-element subset of <math> S</math> contains fi...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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]

See Also

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