Hint

Let $T$ be the subset with size $\frac{CHN}{\ln{N}}$. Suppose for contradiction that one cannot find $H$ elements in $T$ satisfying the desired condition. For positive integer $d$, define $S_d = \{dp: p \leq \frac{N}{d} \textit{ is prime}\}.$ Then $|T \cap S_d| < H$ holds for every $d$. The union bound gives us $$ |T \cap (\cup_{1 \leq d \leq \frac{CN}{2\ln{N}}} S_d)| < \frac{CHN}{2 \ln{N}} \leq \frac{|T|}{2}.$$ On the other hand, let us count how many numbers $\leq N$ belong in none of these $S_d$. In fact, if $n \leq N$ and $n$ has a prime divisor $p \geq \frac{2\ln{N}}{C}$, then $n \in S_{\frac{n}{p}}$ and $d = \frac{n}{p} \leq \frac{CN}{2 \ln{N}}$. Hence, any $n \leq N$ that lives outside the union $\cup_{1 \leq d \leq \frac{CN}{2\ln{N}}} S_d$ must have the property that all its prime divisors are at most $\frac{2 \ln{N}}{C}$. The number of such primes is about $\frac{2 \ln{N}}{C \ln\ln{N}}$, and each exponent can take at most $\log_2{N}$ values. There are thus at most $$(\log_2{N})^{\frac{2 \ln{N}}{C \ln\ln{N}}} \approx N^{\frac{2}{C}} $$numbers $n$ that is not in any $S_d$ with $d \leq \frac{CHN}{2 \ln{N}}$. We obtain a contradiction since $N^{\frac{2}{C}} \ll \frac{|T|}{2}$.

toto1234567890 wrote:

Hint

Don't you mind to let me know how to use probabilistic method in this problem?

Surprisingly, $H$ is mostly irrelevant. Let $X_d=\{ dp| p \text{ prime} \} \cap [N]$. If $|A\cap X_d|\ge H$ we are done. Therefore, for all $d$, $|A\cap X_d| \le H-1$ Sum over all $d$ from $1$ to $\frac{CN}{\ln N}$, we get $A\cap [n]\backslash \cup_{j=1}^{CN/ln N} X_j \ge |A|-(H-1)CN/\ln N=\frac{CN}{\ln N}$ I claim for all sufficiently large $N$, $|[N]\backslash \cup_{j=1}^{2N/ln N} X_j| \le \frac{N}{\ln N}$ First, note all elements of $[n]\backslash \cup_{j=1}^{2N/ln N} X_j$ are divisible by primes at most $\ln N/2$ because if $p\mid t, p>\ln N/2$ then $\frac tp \le \frac Np < \frac{2N}{\ln N}$, contradiction. Therefore, $|[n]\backslash \cup_{j=1}^{2N/ln N} X_j| \le exp( \sum\limits_{p<\frac{\ln N}{2}}\log(\log_p(N)))$. By Prime Number Theorem, there exists at most $0.7\ln N/\ln \ln N$ primes at most $\frac{\ln N}{2}$. This means $exp( \sum\limits_{p<\frac{\ln N}{2}}\log(\log_p(N))) \le exp(0.7\ln N/\ln \ln N \cdot \ln(\log_2(N)))\le exp(0.71 \ln N)=N^{0.71}< CN/\ln N$

This is really difficult, only two contestants solved it in the test, and both of them used Prime number theorem. The idea is quite natural, for example, for a graph $G$ defined on set $[N]:=\{1,2,\dots N\}$, we color the edge $e=(i,j)$ with color $gcd(i,j)$, and wish to partition the vertex set $N$ into no more than $O\left(\frac{N}{logN}\right)$ subsets, such that the induced subgraph on every subset is a monochromatic clique, therefore one can clearly see that the statement in the problem is true due to Pigeonhole's theorem. However, after a long time struggling to find such a partition, I got almost nowhere, the main reason is that those "small" numbers are really annoying when you try to put them in a subset. Then with a good amount of thinking and observation, one could realize that if we can overlook some relatively "small" numbers, i.e. those number whose largest prime factor is less than a constant that depends only on $N$, say $C=C(N)$, we can easily partition the subgraph of $G$ on set $S$:= \{$ n\in [N]$ $\mid$ the maximum prime factor of n is no less than $C(N)$ \}. Now it is clear, pick $C=logN$, we can show that $S$ can be properly partitioned and $\mid [N] \backslash S\mid = o\left (\frac{N}{logN} \right)$, just like the solutions above.Done!!!

angiland wrote: Let $T$ be the subset with size $\frac{CHN}{\ln{N}}$. Suppose for contradiction that one cannot find $H$ elements in $T$ satisfying the desired condition. For positive integer $d$, define $S_d = \{dp: p \leq \frac{N}{d} \textit{ is prime}\}.$ Then $|T \cap S_d| < H$ holds for every $d$. The union bound gives us $$ |T \cap (\cup_{1 \leq d \leq \frac{CN}{2\ln{N}}} S_d)| < \frac{CHN}{2 \ln{N}} \leq \frac{|T|}{2}.$$ On the other hand, let us count how many numbers $\leq N$ belong in none of these $S_d$. In fact, if $n \leq N$ and $n$ has a prime divisor $p \geq \frac{2\ln{N}}{C}$, then $n \in S_{\frac{n}{p}}$ and $d = \frac{n}{p} \leq \frac{CN}{2 \ln{N}}$. Hence, any $n \leq N$ that lives outside the union $\cup_{1 \leq d \leq \frac{CN}{2\ln{N}}} S_d$ must have the property that all its prime divisors are at most $\frac{2 \ln{N}}{C}$. The number of such primes is about $\frac{2 \ln{N}}{C \ln\ln{N}}$, and each exponent can take at most $\log_2{N}$ values. There are thus at most $$(\log_2{N})^{\frac{2 \ln{N}}{C \ln\ln{N}}} \approx N^{\frac{2}{C}} $$numbers $n$ that is not in any $S_d$ with $d \leq \frac{CHN}{2 \ln{N}}$. We obtain a contradiction since $N^{\frac{2}{C}} \ll \frac{|T|}{2}$. Okay but can an angiland wrote: Let $T$ be the subset with size $\frac{CHN}{\ln{N}}$. Suppose for contradiction that one cannot find $H$ elements in $T$ satisfying the desired condition. For positive integer $d$, define $S_d = \{dp: p \leq \frac{N}{d} \textit{ is prime}\}.$ Then $|T \cap S_d| < H$ holds for every $d$. The union bound gives us $$ |T \cap (\cup_{1 \leq d \leq \frac{CN}{2\ln{N}}} S_d)| < \frac{CHN}{2 \ln{N}} \leq \frac{|T|}{2}.$$ On the other hand, let us count how many numbers $\leq N$ belong in none of these $S_d$. In fact, if $n \leq N$ and $n$ has a prime divisor $p \geq \frac{2\ln{N}}{C}$, then $n \in S_{\frac{n}{p}}$ and $d = \frac{n}{p} \leq \frac{CN}{2 \ln{N}}$. Hence, any $n \leq N$ that lives outside the union $\cup_{1 \leq d \leq \frac{CN}{2\ln{N}}} S_d$ must have the property that all its prime divisors are at most $\frac{2 \ln{N}}{C}$. The number of such primes is about $\frac{2 \ln{N}}{C \ln\ln{N}}$, and each exponent can take at most $\log_2{N}$ values. There are thus at most $$(\log_2{N})^{\frac{2 \ln{N}}{C \ln\ln{N}}} \approx N^{\frac{2}{C}} $$numbers $n$ that is not in any $S_d$ with $d \leq \frac{CHN}{2 \ln{N}}$. We obtain a contradiction since $N^{\frac{2}{C}} \ll \frac{|T|}{2}$. Can any one explain $p \geq \frac{2\ln{N}}{C}$ give us $p$ greater than 6??

Any answer please??

@above Simply from the hypothesis you have $N\geq e^{CH}$ and $H\geq 3$ : so $2ln(N) \geq 2 ln(e^{CH})=2CH \geq 6 C$

oty wrote: @above Simply from the hypothesis you have $N\geq e^{CH}$ and $H\geq 3$ : so $2ln(N) \geq 2 ln(e^{CH})=2CH \geq 6 C$ But in this problem must $p$ greater than 2?? It's not right?? Any answer

Any answer