Sunday, October 01, 2006


Let S = {1,2,...,n}. Define T_k to be a subset of S such that if i belongs to T_k, k*i does not belong to T_k. What is the largest size of T_k? It was (is) an exercise in some Discrete Math textbook to show that T_3 = 3n/4. The upper bound is a simple recursive construction giving T(n)= T(n/9)+ 2n/3; the lower bound will argue that any other "largest set" can be converted to the one given by this recursive construction without decreasing its size.

Say we extend this to look at subset T_{k,l} of S such that if i belongs to T_{k,l} then k*i and l*i do not belong to T_{k,l}, what is the largest size of T_{k,l}? In particular, T_{3,5} is a simple start.

Humiliation: I was a TA for a discrete math course a long time ago when a student
asked me about T_3. I approached it without much respect since it was an undergrad HW problem and guessed silly things like n/2, 2n/3 etc before slowly seeing that one could do better. Ultimately, I had to stand in the front of the board and scratch it out before the smug student.


Post a Comment

<< Home