wu :: forums « wu :: forums - Extremal combinatorial problem » Welcome, Guest. Please Login or Register. May 16th, 2024, 11:00pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    putnam exam (pure math) (Moderators: Eigenray, Grimbal, Icarus, william wu, SMQ, towr)    Extremal combinatorial problem « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Extremal combinatorial problem  (Read 1364 times) anonymous Guest Extremal combinatorial problem   « on: Apr 9th, 2003, 8:38am » Quote Modify Remove 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}. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board