Maths Olympiad Prep

Library / /217 of 462

Number theory Difficulty 5.7 AIME, harder Prove it Ireland

An Irish Set is a set of positive integers such that each pair of integers in the set has a common factor greater than 11, and there is no prime number that divides all integers in this set. Is there an Irish Set that contains exactly 20242024 integers, all smaller than 80008000?

Solution

A key observation is that when we add to the Irish Set S={s1,s2,,sn}S = \{s_1, s_2, \dots, s_n\} any positive multiple of an element sis_i that is not yet contained in SS we obtain an Irish Set with n+1n + 1 elements.

One possibility then is to start with an Irish Set of length 33 and add multiples of these three numbers to the set. One may pick prime numbers p<q<rp < q < r and form the Irish Set {pq,pr,qr}\{pq, pr, qr\} of cardinality 33. For example, using the primes 2,3,52, 3, 5 we obtain the set S={6,10,15}S = \{6, 10, 15\} which is Irish.

We can extend SS to a larger Irish Set by including as many positive integers of the form 6a,10b6a, 10b, and 15c15c as we wish. The requirement that all members of the set are smaller than 80008000 then leads to the conditions a1333a \le 1333, b<800b < 800, and c533c \le 533.

Because the lowest common multiple of any two of the three numbers 6,10,156, 10, 15 is equal to 3030, we multi-count all multiples of 3030 but no other number when we add 1333,7991333, 799 and 533533. Each multiple of 3030 appears three times. Since 266<8000/30<267266 < 8000/30 < 267, we have constructed an Irish set that contains exactly
1333+799+5332266=2133 1333 + 799 + 533 - 2 \cdot 266 = 2133
elements. We can now remove any 109109 members from this set to get a set that contains exactly 20242024 elements, all smaller than 80008000, such that no pair of members of this set is coprime. Is it still true that no prime number divides all integers in this set? This can easily be achieved by leaving 6,10,156, 10, 15 in the set. However, this is true in general, because after removing any 109109 members from this set, there will be at least one pair of consecutive multiples of 66 left in the set, and similarly for multiples of 1010 and 1515. Since gcd(6a,6(a+1),10b,10(b+1),15c,15(c+1))=gcd(6,10,15)=1\gcd(6a, 6(a+1), 10b, 10(b+1), 15c, 15(c+1)) = \gcd(6, 10, 15) = 1, we see that after removing any 109109 numbers we indeed get an Irish Set.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.