MathDB

5

Part of 2022 Brazil Undergrad MO

Problems(1)

Product of density-like function is larger than 1/4

Source: Brazilian Undergrad Mathematics Olympiad 2022 P5

11/26/2022
Given X⊂NX \subset \mathbb{N}, define d(X)d(X) as the largest c∈[0,1]c \in [0, 1] such that for any a<ca < c and n0∈Nn_0\in \mathbb{N}, there exists m,r∈Nm, r \in \mathbb{N} with r≥n0r \geq n_0 and ∣X∩[m,m+r)∣r≥a\frac{\mid X \cap [m, m+r)\mid}{r} \geq a.
Let E,F⊂NE, F \subset \mathbb{N} such that d(E)d(F)>1/4d(E)d(F) > 1/4. Prove that for any prime pp and k∈Nk\in\mathbb{N}, there exists m∈E,n∈Fm \in E, n \in F such that m≡n(modpk)m\equiv n \pmod{p^k}