miracle_jr's blog

By miracle_jr, history, 5 weeks ago, In English

Hi, I was reading the editorial of the Half Sequence problem from recent cookoff. One of the statements has been left for readers to prove and I am unable to prove it. The statement is as follows.

"Observe that any single number less then 1e9 can be made up of atmost 9 distinct prime numbers. This means that if GCD([B[0], B[1], ..., B[N]) = 1, where N >= 9 then there must exist atleast one subset of length at most 9 whose elements have GCD=1. (Proof left as an exercise)"

I have trouble understanding the last line. Why must there exist that subset?

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Each single number made up of at most 9 distinct prime numbers does not infer if GCD([B[0], B[1], ..., B[N]) = 1, where N >= 9 then there must exist at least one subset of length at most 9 whose elements have GCD = 1. For example, let $$$a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$$$, $$$p = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29$$$, and for each $$$i$$$, $$$b_i = \frac{p}{a}$$$. The GCD of $$$b_1, b_2, \dots, b_{10}$$$ is $$$1$$$, each $$$b_i$$$ is a product of $$$9$$$ distinct prime numbers, but GCD of any $$$9$$$ of $$$b_i$$$'s is greater than $$$1$$$.

It is easy to prove that there must exist at least one subset of length at most 10 whose elements have GCD = 1: starting with any given number, then repeatedly do the following process: choose a number to add to the current subset, such that it can eliminate at least one prime factor of the current GCD. Since this process can be done at most $$$9$$$ times, the resulting subset should have a size no larger than $$$10$$$.

However, the conclusion in your statement is still correct, it is because the given numbers are less than $$$10^9$$$. That means, if all subsets of size $$$9$$$ have GCD greater than $$$1$$$, then each number should have exact $$$9$$$ different prime factors. Moreover, since they are coprime, then at least one of them does not have prime factor $$$2$$$. This number should be at least $$$3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 = 3234846615$$$.