Cn/lnn bound for S

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Cn/lnn bound for S

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 March 谜之竞赛-2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

827 posts

#1 h Yesterday at 8:24 AM

Y by

Prove that there exists an constant $C,$ such that for all integer $n\ge 2$ and a subset $S$ of $[n],$ satisfy $a\mid\tbinom ab$ for all $a,b\in S,$ $a>b,$ then $|S|\le \frac{Cn}{\ln n}.$

Created by Yuxing Ye

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

520 posts

#2 h Yesterday at 11:36 AM

Y by

Very nice and hard problem in my opinion. Let $pA_p$ be the set of elements $s \in S$ that $p \mid s$ . It is clear that $pA_p \subset [n]$ so every element of $A_p$ is less than $n/p$ . Let $p_i$ be the $i$ th prime, and there are $k$ primes not exceeding $n$ .

Assume that $(x+1)p^t - 1 > n \ge xp^t-1$ for some $1 \le x \le p-1$ . Then for any $a \in A_p$ , we have that $a$ is in the form of $\overline{a_{t-1} \cdots a_0}_{(p)}$ in base $p$ . For any $a, b \in A_p$ , we have $p \mid \tbinom{a}{b}$ . From Lucas Thm, we have that when $a = \overline{a_{t-1} \cdots a_0}_{(p)}$ and $b = \overline{b_{t-1} \cdots b_0}_{(p)}$ , there exists a nonnegative integer $i$ that $a_i < b_i$ . We define a poset $P$ of nonnegative integers less than $(x+1)p^t - 1 = \overline{x (p-1) \cdots (p-1)}_{(p)}$ , where $a \preceq b$ is equivalent to $a_i \ge b_i$ for all $i$ , we have that $A_p$ is a antichain.

From de brujin's, we have that the maximal length antichain is the set of elements with middle rank, where rank of $a = \overline{a_{t-1} \cdots a_0}_{(p)}$ is $\sum a_i$ . Therefore, $|A_p|$ is at most the number of solutions to the following equation where $a_i$ are integers in the range $[0, p-1]$ , and $a_{t-1} \le x$ .
$\dfrac{p-1}{2}(t-1) + \left \lfloor \dfrac{x}{2} \right \rfloor = a_{t-1} + a_{t-2} + \cdots + a_0$ When the tuple $(a_{t-1}, a_{t-2}, \cdots, a_{1})$ is fixed, there is at most one solution of $a_0$ , so there are at most $(x+1)p^{t-2}$ solutions to this equation. This cannot exceed $\dfrac{2n}{p^2}$ . Therefore, we can get that $|A_p| \le \dfrac{2n}{p^2}$ .

Now, we bound the sum of $1/p^2$ , to obtain the bound of $|S|$ . Let $c$ be some nonnegative constant under $k$ so that $p_c \ge \dfrac{\log n}{\sqrt{ \log \log n }}$ . Also, let $d$ be the minimum possible number that $p_d \ge \log n$ .
$\sum_{c \le i \le k} \dfrac{1}{p_i^2} \le \sum_{c \le i \le d} \dfrac{1}{p_c^2}+ \sum_{d \le i \le k}{\left( \dfrac{1}{p_i} - \dfrac{1}{p_{i+1}} \right)} \le \dfrac{1}{p_c^2} \pi(\log n) + \dfrac{1}{p_d} \le \dfrac{\log \log n}{(\log n)^2} \pi(\log n) + \dfrac{1}{\log n}$ $\sum_{c \le i \le k} |A_{p_i}| = \mathcal{O} \left( \dfrac{n}{\log n} \right)$ from $\pi(x) = \mathcal{O} \left( \dfrac{x}{\log x} \right)$ . (this can be proved in an elementary way, we don't need to use PNT).

Now, we count the number of integers so that all prime factors are less than $\log n$ . All exponents of such primes are less than $\log_2 n$ , so we have that the total number $N$ of those numbers in $[n]$ is at most $(\log_2 n + 1)^{\pi(p_c)}$ . Taking logarithms, we have that $\log N \le \pi(p_c)\log (\log_2 n + 1)$ . However, this is at most $\log n - \log \log n + C_1$ for some $C_1$ , since $\pi(p_c) = \mathcal{O} \left( \dfrac{\log n}{(\log \log n)^{3/2}} \right)$ . Therefore, $|S| \le N + \sum_{c \le i \le k}|A_{p_i}| = \mathcal{O} \left( \dfrac{n}{\log n} \right)$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a