Problemas de la función piso

Question

Hay dos partes de mi problema.

1. Dado $n$ y $x$, $\lfloor \frac nx \rfloor = q$, ¿cuál es el valor máximo posible de $x$ para que obtengamos el mismo valor de piso? es decir, $\lfloor \frac nx \rfloor = \lfloor \frac{n}{x'}\rfloor = q$, donde $x' \geq x $. Creo que $x' = \lfloor \frac nq \rfloor$ es la respuesta.
2. ¿Cuántos valores posibles (distintos) de q existen para todos los $x$ donde $1\leq x\leq n$?

Lo que pensé fue, ¿cuál es el valor máximo de $q$ que podemos obtener y también el valor mínimo de $q$? Entonces, la respuesta sería $max - min + 1$. Pero esto seguramente está mal porque podemos tener los mismos valores de piso para diferentes valores de x. Por ejemplo, para cualquier $x \geq \lfloor \frac n2\rfloor + 1$, $q = \lfloor \frac nx\rfloor = 1$. Así que el número máximo de valores de piso distintos es como máximo $1 + \lfloor \frac n2 \rfloor$. ¿Cómo puedo reducir el límite superior ya que he leído que hay como máximo $2\sqrt n$ valores distintos?

Answer 1

Según la definición de $\lfloor\cdot\rfloor$, tenemos

$$\biggl\lfloor \frac{n}{x}\biggr\rfloor = q \iff q \leqslant \frac{n}{x} < q+1$$

para $q\in \mathbb{Z}$. Dado que aquí estamos tratando con enteros positivos, el sentido de las desigualdades se mantiene al multiplicar por $x$ y dividir por $q$ o $q+1, por lo que tenemos

$$\biggl\lfloor \frac{n}{x}\biggr\rfloor = q \iff \frac{n}{q+1} < x \leqslant \frac{n}{q}.$$

Utilizando que también $x$ debe ser un entero, obtenemos

$$\biggl\lfloor \frac{n}{x}\biggr\rfloor = q \iff \biggl\lfloor \frac{n}{q+1}\biggr\rfloor < x \leqslant \biggl\lfloor\frac{n}{q}\biggr\rfloor.$$

Por lo tanto, para cada $q$ hay $\bigl\lfloor \frac{n}{q}\bigr\rfloor - \bigl\lfloor \frac{n}{q+1}\bigr\rfloor$ valores enteros $1 \leqslant x \leqslant n$ tal que $\bigl\lfloor \frac{n}{x}\bigr\rfloor = q$, y el máximo $x$ de este tipo es de hecho $\bigl\lfloor \frac{n}{q}\bigr\rfloor.

¿Cómo reduzco el límite superior si he leído que hay a lo sumo $2\sqrt{n}$ valores distintos?

Observa que para $x > \sqrt{n}$, tenemos $\frac{n}{x} < \sqrt{n}$ y por lo tanto $\bigl\lfloor \frac{n}{x}\bigr\rfloor \leqslant \lfloor \sqrt{n}\rfloor$. Por lo tanto, tenemos como máximo $\lfloor \sqrt{n}\rfloor$ valores distintos de $\bigl\lfloor \frac{n}{x}\bigr\rfloor$ para $1 \leqslant x \leqslant \lfloor \sqrt{n}\rfloor$, y los $\lfloor \sqrt{n}\rfloor$ valores $1 \leqslant q \leqslant \lfloor \sqrt{n}\rfloor$ para $\lfloor \sqrt{n}\rfloor + 1 \leqslant x \leqslant n$, lo que da como máximo $2\lfloor \sqrt{n}\rfloor$ valores distintos en total. De hecho, los valores de $\bigl\lfloor \frac{n}{x}\bigr\rfloor$ para $1 \leqslant x \leqslant \lfloor \sqrt{n}\rfloor$ son todos distintos, y todos los valores $1 \leqslant q \leqslant \lfloor \sqrt{n}\rfloor$ se alcanzan, por lo que hay exactamente $2\lfloor \sqrt{n}\rfloor$ valores diferentes, a menos que el valor $\lfloor \sqrt{n}\rfloor$ aparezca en ambos conjuntos - cuando $\bigl\lfloor \frac{n}{\lfloor \sqrt{n}\rfloor}\bigr\rfloor = \lfloor \sqrt{n}\rfloor$, o equivalentemente $n < \lfloor \sqrt{n}\rfloor\cdot (\lfloor \sqrt{n}\rfloor + 1)$ - en cuyo caso hay exactamente $2\lfloor \sqrt{n}\rfloor - 1$ valores distintos.