Probar una desigualdad particular entre dos sumas de techo

Question

Tenemos un número entero $N$ y $k$ enteros $n_1 \geq n_2 \geq \ldots \geq n_k$ . También tenemos una permutación aleatoria $\pi$ que permuta los índices de $[1, k]$ .

Me gustaría demostrar que tenemos la siguiente desigualdad para cualquier permutación aleatoria $\pi$ :

$$\lceil N/n_1 \rceil + \lceil N/(n_1n_2) \rceil + \cdots + \lceil N/(n_1n_2\ldots n_k) \rceil \leq \lceil N/n_{\pi(1)} \rceil + \lceil N/(n_{\pi(1)}n_{\pi(2)}) \rceil + \cdots + \lceil N/(n_{\pi(1)}n_{\pi(2)}\ldots n_{\pi(k)}) \rceil$$

¿Es obvio?

Muchas gracias.

Answer 1

Obsérvese que para cada permutación $\pi$ tenemos $n_1 \geq n_{\pi(1)}$ , $n_1n_2 \geq n_{\pi(1)}n_{\pi(2)}$ y así sucesivamente. De esto se deduce:

\begin{align} \lceil N/n_1 \rceil &\leq \lceil N/n_{\pi(1)}\rceil\\ \lceil N/(n_1n_2) \rceil &\leq \lceil N/(n_{\pi(1)}n_{\pi(2)})\rceil\\ &\vdots \\ \lceil N/(n_1n_2\ldots n_k) \rceil &\leq \lceil N/(n_{\pi(1)}n_{\pi(2)}\ldots n_{\pi(k)})\rceil\\ \end{align}

Sumando los lados izquierdo y derecho se obtiene la desigualdad deseada.