Invertir la igualdad que contiene la operación de tomar la parte entera

Question

Recientemente se me presentó la siguiente igualdad $$n = \left[\frac{w}{2d+a}\right]\cdot \left[\frac{h}{2d+b}\right]$$ donde todas las variables participantes son enteros no negativos, y $[\ldots]$ es la operación de tomar la parte entera (por ejemplo $[6.789]=6$ ). El problema es expresar $d$ es decir, resolver esta igualdad para $d$ y obtener una solución en forma de $f(a,b,w,h,n)\leq d\leq F(a,b,w,h,n)$ o alguna forma simular que permita determinar el rango de valores de $d$ por valores dados de $a,b,w,h,n$ en tiempo constante, algorítmicamente hablando.

Sin duda, si no fuera por estos corchetes, el problema sería pan comido: $$n = \frac{w}{2d+a}\cdot \frac{h}{2d+b} = \frac{wh}{(2d+a)(2d+b)}=\frac{wh}{4d^2+2d(a+b)+ab}$$ $$4d^2+2d(a+b)+ab-\frac{wh}{n} = 0$$ $$d = -\frac{1}{4}(a+b)\pm\frac{1}{4}\sqrt{(a+b)^2-4ab+\frac{4hw}{n}}$$ Pero desgraciadamente $[x][y]\neq [xy]$ . ¿Hay alguna manera de tratar la operación con enteros?

P.D. En el problema original bastaría con encontrar el mayor $d$ .

---

Siguiendo la sugerencia de la respuesta de David Kleiman, tengamos $\left[\frac{w}{2d+a}\right] = \frac{w}{2d+a} - r_1$ y $\left[\frac{h}{2d+b}\right] = \frac{h}{2d+b} - r_2$ , donde $r_i\in [0, 1)$ . Además, deja que $q = 2d$ para mayor comodidad. Ahora la igualdad toma forma: $$n = \left(\frac{w}{q+a} - r_1\right)\cdot \left(\frac{h}{q+b} - r_2\right)$$ Ahora vamos a bastardear esta hermosa fórmula a lo grande eliminando paréntesis, liquidando fracciones y reuniendo coeficientes de las potencias de $q$ :

$$q^2(n-r_1r_2)+q((n-r_1r_2)(a+b)+r_1h+r_2w)+abn-wh+r_1ha+r_2wb-r_1r_2ab=0$$

Parecía conveniente introducir denotaciones $m=n-r_1r_2$ y $c=a+b$ Así que..:

$$q^2m+q(mc+r_1h+r_2w)+abn-wh+r_1ha+r_2wb-r_1r_2ab=0$$

Resolviendo la ecuación cuádrica para $q$ y eligiendo el signo positivo obtenemos: $$q = \frac{-(mc+r_1h+r_2w)+\sqrt{D}}{2m},$$ donde $$D = (mc+r_1h+r_2w)^2-4m(abn-wh+r_1ha+r_2wb-r_1r_2ab).$$ Juntando todo esto tenemos: $$q = \frac{-((n-r_1r_2)(a+b)+r_1h+r_2w)}{2(n-r_1r_2)}+\frac{\sqrt{((n-r_1r_2)(a+b)+r_1h+r_2w)^2-4(n-r_1r_2)(abn-wh+r_1ha+r_2wb-r_1r_2ab)}}{2(n-r_1r_2)}$$ Entonces... ¿cómo maximizarlo?

Answer 1

No estoy seguro de que esto sea lo que buscas, pero puedes escribir $[x] = x - r$ donde $0 \leq r < 1$ . Puede hacerlo para ambos factores (con $r_1$ y $r_2$ digamos), y luego resolver para $d$ utilizando la fórmula cuadrática. Entonces se puede maximizar (minimizar) $d$ en función de $r_1$ y $r_2$ .

Probablemente será un cálculo muy tedioso, pero al tener un dominio acotado, la función alcanzará su máximo y su mínimo.