Advance P-4(BOMC-2)

Discussion on Bangladesh National Math Camp
sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:
Advance P-4(BOMC-2)

Unread post by sourav das » Sat Mar 31, 2012 8:52 pm

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.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Advance P-4(BOMC-2)

Unread post by *Mahi* » Sat Mar 31, 2012 11:41 pm

Isn't it quite bruteforce?
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:

Re: Advance P-4(BOMC-2)

Unread post by sourav das » Sat Mar 31, 2012 11:59 pm

I don't think so. A small effective trick really kills the problem
First intuition
Pigeon hole principle
Trick
Every $n$ has a prime factor less or equal $\sqrt {n}$
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Advance P-4(BOMC-2)

Unread post by *Mahi* » Sun Apr 01, 2012 12:04 am

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.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Niloy Da Fermat
Posts:33
Joined:Wed Mar 21, 2012 11:48 am

Re: Advance P-4(BOMC-2)

Unread post by Niloy Da Fermat » Sun Apr 01, 2012 3:18 pm

is there any tricky solution?i did tedious job like
finding out all primes from $ 1 $ to $ 210 $
the answer is
$ 26 $
kame......hame.......haa!!!!
আব্দুল্লাহ আল মুনইম (নিলয়)
সরকারি কেসি কলেজ, ঝিনাইদহ

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Advance P-4(BOMC-2)

Unread post by *Mahi* » Sun Apr 01, 2012 3:25 pm

@Niloy-
I don't think so. I think that was the least tedious way of solving this problem.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Post Reply