Page 1 of 1
Advance P-4(BOMC-2)
Posted: Sat Mar 31, 2012 8:52 pm
by sourav das
Set $S$ = {$105, 106, . . . , 210$}. Determine the minimum value of $n$ such that any $n$-element subset $T$ of $S$ contains at least two non-relatively prime elements.
Re: Advance P-4(BOMC-2)
Posted: Sat Mar 31, 2012 11:41 pm
by *Mahi*
Isn't it quite bruteforce?
Re: Advance P-4(BOMC-2)
Posted: Sat Mar 31, 2012 11:59 pm
by sourav das
I don't think so. A small effective trick really kills the problem
First intuition
Trick
Re: Advance P-4(BOMC-2)
Posted: Sun Apr 01, 2012 12:04 am
by *Mahi*
Nevermind, but that seemed trivial to me, even then (maybe because I'm too lazy) it seemed to me that finding the final set was bruteforce.
Re: Advance P-4(BOMC-2)
Posted: Sun Apr 01, 2012 3:18 pm
by Niloy Da Fermat
is there any tricky solution?i did tedious job like
the answer is
Re: Advance P-4(BOMC-2)
Posted: Sun Apr 01, 2012 3:25 pm
by *Mahi*
@Niloy-
I don't think so. I think that was the least tedious way of solving this problem.