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.
Problem
Source: IMO 1991, Day 1, Problem 3, IMO ShortList 1991, Problem 12 (CHN 3)
Tags: combinatorics, IMO, Extremal combinatorics, Set systems, relatively prime, imo 1991
Ilthigore
22.04.2008 21:01
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.
Wave-Particle
26.07.2017 00:55
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.
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.
xwang1
18.09.2017 08:34
Sorry for the bump, but why is this problem difficult enough to be a #3? To me this problem looks more like something you would find early-mid AIME than IMO level. Is it just because IMO 25 years ago was much easier than what it is nowadays?
HamstPan38825
16.07.2022 02:25
The answer is $\boxed{217}$. Partition $S$ into sets $A_i$ such that$$A_i = \{a \in \mathbb N \mid p_i \text{ divides } a \text{ and } p_j \nmid a \ \forall j < i\},$$where $p_i$ denotes the $i$th prime. Observe that $|A_1|+|A_2|+|A_3|+|A_4| = 216$ by a PIE computation. Notice that by definition, any two numbers that fall in different sets are relatively prime. Furthermore, if we pick 217 numbers, by Pigeonhole two of them must fall in the same set because $|A_i|$ is strictly decreasing as $i$ increases (and thus, 186 is the maximum possible sum of the cardinalities of any four of these sets). Therefore we have the result.
StarLex1
30.11.2022 10:16
is my method correct here since we wanted to find the smallest n for all subset Worst Case is when n divisible by 2 so you need to pick at least (140) so it left by things not divisible by 2 Again Worst Case is when n is divisible by 3 but u need to count the inclusion when 2 doesn't divide n there is 93 multiple of 3 in the set but there is 46 number divisible by 2 subtracting we get 47 Why worst case since they are the one that appear the most in the set Worst case when n divisible by 5 there is 56 number multiple of 5 but we need to find the pure one it is not divisible by 2 not divisible by 3 using PIE 56 = Pure+(|divisible by 10|+|divisible by 15|-|divisible by 30|) = Pure + (|28|+|18|-9) Pure = 19 Worst case when n divisible by 7 but doesn't have (2,3,5) as factor just bash since quite small $7*1,7^2,7*11,7*13,7*17,7*19,7*23,7*29,7*31,7*37= 10$ $140+47+19+10 = 216$ is the required which there exist already (4) by adding one more number since the one that being left are already relative prime to 2,3,5,7 (216+1) done
Assassino9931
10.12.2024 14:59
HamstPan38825 wrote: Notice that by definition, any two numbers that fall in different sets are relatively prime. I don't think so? What is the problem for two numbers to be divisible by $101$ but one of them to be in $A_1$ and the other one in $A_2$?