wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Extremal combinatorial problem
        
(Message started by: anonymous on Apr 9^th, 2003, 8:38am)

Title: Extremal combinatorial problem
Post by anonymous on Apr 9^th, 2003, 8:38am

Let S be a subset of {1,2,...,100} such that

(i) for all a,b in S such that a!=b, there exist c in S such that gcd(a,c)=gcd(b,c)=1

(ii) for all a,b in S such that a!=b, there exist d in S such that d!=a,b and gcd(a,d)>1, gcd(b,d)>1

Find the maximum possible size of S.

PS: If I'm not mistaken the answer is 72. Here is a construction for |S|=72:

S = {2,3,5,7,11} + {all composite numbers <= 100} - {30,60,90,42,84,66,70}.