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, B, ..., 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?