Let $ S$ be the set of all odd positive integers less than $ 30m$ which are not multiples of $ 5$, where $ m$ is a given positive integer. Find the smallest positive integer $ k$ such that each $ k$-element subset of $ S$ contains two distinct numbers, one of which divides the other.
Problem
Source:
Tags: floor function, combinatorics unsolved, combinatorics
kops723
19.04.2008 18:40
I'm pretty sure it can't be 2m+1... if m=1 just pick $ {3,7,11}$ or any other set of three primes.
I hate rating
19.04.2008 20:40
1. $ k\geq$ Number of primes in $ S$. 2. Let $ S(n)$ denote the set of all odd numbers less than $ n$ which are not the multiples of 5. We observe $ 30m-1$ is not divisible by any number less than 7(other than 1). $ k\geq |S|-\lfloor |S\big (\frac{30m-1}{7}\big )|\rfloor$
Albanian Eagle
19.04.2008 21:30
so sorry, its 8m+1. Same hint
easternlatincup
25.04.2008 11:15
And then?
Albanian Eagle
25.04.2008 12:04
first find how many numbers are not divisible by 2, 3 or 5. after that consider the chains $ C_a=\{a,3a, 9a, ...\}$ defined by these numbers. show that our set should not have two elements from the same chain. so what can we say about k in terms of the number of such chains?