How to solve inequality equation with ceil operator product

Question

I am trying to solve this inequality for $x$:

$$ \left \lceil{\frac{c_1}{x}}\right \rceil \cdot \left \lceil{\frac{c_2}{x}}\right \rceil \leq N $$

With: $c_1, c_2, x, N \in \mathbb{N}$ and $c_1, c_2, N$ being just constants.

I could make my system work with a solution assuming that $ x \leq c_1, c_2 $ but I would like ot have a general solution if someone can help me. The context behind this equation is how to split an image of $[H,W]=[c_1, c_2]$ in square patches of size $[H_{patch}, W_{patch}]=[x,x]$.

What I have tried yet:

• Solve the equation for the lower bound of each inequality: I does not work.

$$\frac{c_1c_2}{x^2} \leq N \rightarrow \sqrt{\frac{c_1c_2}{N}} \leq x$$

• Solve the equation for the upper bound: I am stuck getting x out of this expression.

$$ (\frac{c_1}{x^2}+1) \cdot (\frac{c_1}{x^2}+1) =\frac{c_1c_2}{x^2} + \frac{c_1}{x} + \frac{c_2}{x} + 1\leq N$$

Forgive my possible mistakes, I am not a mathematician. Thank you for your help in advance.

Answer 1

As discussed in the comments, you need a minimum value for $x$, let's call it $x_{min}$. This is what you mean by lower bound for $x$. I think I also understand what did you mean by upper bound: a "safe" value of $x$ for which the relation is definitely true but could be improved. Let's call it $x_{safe}$.

Your attempt by having $x \leq c_1, c_2$ is just the other way round: $x \geq c_1, c_2$, or as I prefer to denote $x_{safe} = max(c_1, c_2)$. But this is far from $x_{min}$ in cases $N \neq 1$, and you just need to do trial-and-error by brute-force or something to get $x_{min}$ from $x_{safe}$.

First of all, let's make it clear, that if $N = 1$, then $x_{min} = max(c_1, c_2)$.

Secondly, when $N \neq 1$, I can show you how to get $x_{safe}$ closer to $x_{min}$. I can not tell you how to get $x_{min}$ with a formula. You still need to get $x_{min}$ from $x_{safe}$ if you really need the minimum value. To see how it is improving, let $c_1 = 10, c_2 = 4$.

For this, let's look at your attempt on lower bound:

$$\sqrt{\frac{c_1c_2}{N}} \leq x$$

• If $N = 8$, then $x \geq 2.23... \Rightarrow x = 3 \Rightarrow \left \lceil{\frac{c_1}{x}}\right \rceil \cdot \left \lceil{\frac{c_2}{x}}\right \rceil = 8$, correct.
• If $N = 7$, then $x \geq 2.39... \Rightarrow x = 3 \Rightarrow \left \lceil{\frac{c_1}{x}}\right \rceil \cdot \left \lceil{\frac{c_2}{x}}\right \rceil = 8$, not correct. Using $x = 4 \Rightarrow \left \lceil{\frac{c_1}{x}}\right \rceil \cdot \left \lceil{\frac{c_2}{x}}\right \rceil = 6$, it is now correct.
  This attempt does not give you $x_{safe}$. You need to increase $x$ until it is OK. Or go with $x_{safe} = max(c_1, c_2) = 10$, which is far.

This can be improved.

Let $\alpha \in \mathbb{R}$. We can have a value for $\alpha$ so that if we only had $\lceil{\frac{c_1}{x}} \rceil \leq N$, $\lceil{\frac{c_1}{\alpha}} \rceil = \frac{c_1}{\alpha} = N \Rightarrow \alpha = \frac{c_1}{N}$, and as we need an integer for $x$, we have $x \geq \alpha \Rightarrow x = \lceil{\alpha} \rceil \Rightarrow \lceil{\frac{c_1}{x}} \rceil \leq \lceil{\frac{c_1}{\alpha}} \rceil = N$.

But we have 2 ceiled expressions. So let's examine if $c_1 = c_2 \Rightarrow {\lceil{\frac{c_1}{x}} \rceil}^2 \leq N$:
let:

$$\frac{c_1}{\alpha} = \sqrt{N} \Rightarrow \alpha = \frac{c_1}{\sqrt{N}}$$

From this:

$$x \geq \alpha \Rightarrow x = \lceil{\alpha} \rceil \Rightarrow x = \lceil{\frac{c_1}{\sqrt{N}}} \rceil \Rightarrow \frac{c_1}{x} = \frac{c_1}{\lceil{\frac{c_1}{\sqrt{N}}} \rceil} \leq {\frac{c_1}{\frac{c_1}{\sqrt{N}}}} = \sqrt{N}$$

So we have $\frac{c_1}{x} \leq \sqrt{N}$, but this does not guarantee $\lceil{\frac{c_1}{x}} \rceil \leq \sqrt{N}$, so still need to adjust to have $x_{safe}$.

$$x = \lceil{\frac{c_1}{\sqrt{N} - 1}} \rceil \Rightarrow \frac{c_1}{x} = \frac{c_1}{\lceil{\frac{c_1}{\sqrt{N} - 1}} \rceil} \leq {\frac{c_1}{\frac{c_1}{\sqrt{N} - 1}}} = \sqrt{N} - 1$$

So we have $\frac{c_1}{x} \leq \sqrt{N} - 1 \Rightarrow \lceil{\frac{c_1}{x}} \rceil \leq \lceil{\sqrt{N} - 1} \rceil < \sqrt{N}$. Now this is OK if $c_1 = c_2$, so one more adjustment, and we have:

$$x_{safe} = \lceil{\frac{max(c_1, c_2)}{\sqrt{N} - 1}} \rceil$$

Because if $c_i = max(c_1, c_2) \Rightarrow \lceil{\frac{c_i}{x_{safe}}} \rceil < \sqrt{N}$ from the above and therefore:

$$c_j \leq c_i \Rightarrow \lceil{\frac{c_j}{x_{safe}}} \rceil \leq \lceil{\frac{c_i}{x_{safe}}} \rceil \Rightarrow \left \lceil{\frac{c_1}{x_{safe}}}\right \rceil \cdot \left \lceil{\frac{c_2}{x_{safe}}}\right \rceil < N$$

If $N = 7$, then $x \geq 6.07... \Rightarrow x = 7 \Rightarrow \left \lceil{\frac{c_1}{x}}\right \rceil \cdot \left \lceil{\frac{c_2}{x}}\right \rceil = 2$, correct. Closer to 4 than 10, but in general I can not show how close it would be. But it is for sure:

$$\lceil{\frac{max(c_1, c_2)}{\sqrt{N} - 1}} \rceil \leq max(c_1, c_2), \sqrt{N} - 1 > 1 \Rightarrow N > 4$$

I leave you to investigate $1 < N \leq 4$

So if you need $x_{min}$ you either use your lower bound formula and keep increasing until its sufficient, or use this upper bound and keep decreasing.

Answer 2

Hint: first, let's consider the equation: $$ \left\lceil \frac{c}{x} \right\rceil = k \text{,} $$ where $c,k,x \in \mathbb{N}$. This is equivalent to the following inequality $$ k-1 < \frac{c}{x} \leq k \text{.} $$ If $k = 1$ then $x \geq c$. For $k>1$ we obtain $$ \frac{c}{k} \leq x < \frac{c}{k-1} $$ and since we're interested only in natural solutions, we have $$ x \in \left[ \tfrac{c}{k},\; \tfrac{c}{k-1} \right) \cap \mathbb{N} = \left\lbrace \left\lceil \tfrac{c}{k} \right\rceil,\; \left\lceil \tfrac{c}{k} \right\rceil + 1,\; \ldots,\; \left\lceil \tfrac{c}{k-1} \right\rceil - 1 \right\rbrace \text{.} $$

Now, to solve your problem you need to sum up the solutions of $$ \left\lbrace \begin{array}{l} \left\lceil \frac{c_1}{x} \right\rceil = k_1 \\ \left\lceil \frac{c_2}{x} \right\rceil = k_2 \\ \end{array} \right. $$ for all pairs $k_1,k_2\in\mathbb{N}$ such that $k_1 \cdot k_2 \leq N$.

Answer 3

As my previous answer is quite long, I continue here with your attempt for the upper bound.
Let $k \in \mathbb{N}$, we have $\lceil{\frac{k}{x}} \rceil \leq \frac{k}{x} + 1 \Rightarrow (\frac{c_1}{x} + 1)(\frac{c_2}{x} + 1) \leq \lceil{\frac{c_1}{x} + 1} \rceil \lceil{\frac{c_2}{x} + 1} \rceil \leq N$
$(\frac{c_1}{x} + 1)(\frac{c_2}{x} + 1) \leq N$
$\frac{c_1c_2}{x^2} + \frac{c_1}{x} + \frac{c_2}{x} + 1 \leq N$
$c_1c_2 + c_1 x + c_2 x + x^2 \leq Nx^2$
$0 \leq (N - 1)x^2 - (c_1 + c_2)x - c_1c_2$
This is a quadratic for $x$, so using the quadratic formula we have
$x_{1, 2} = \frac{c_1 + c_2 \pm \sqrt{(c_1 + c_2)^2 + 4(N - 1)c_1c_2}}{2(N - 1)}, N \neq 1$,
If we subtract the square root, we have a negative numerator therefore a negative $x$, this means that we can only use addition, and that $0$ always falls between the two zeroes and at $x = 0$ the original quadratic is negative therefore between the two zeroes $\forall x$ the statement is false, so we have
$x \geq \frac{c_1 + c_2 + \sqrt{(c_1 + c_2)^2 + 4(N - 1)c_1c_2}}{2(N - 1)}, N \neq 1$.
Let us use $c_1 = 10, c_2 = 4$ again.
If $N = 8$, $x \geq 3.59... \Rightarrow x = 4$, this is correct, but as we have seen in the previous answer, $x = 3$ is the minimum value.
If $N = 7$, $x \geq 4 \Rightarrow x = 4$, this is correct, and as we have seen in the previous answer, it is the minimum value.
Again, I can not show if this is the method that always give the closest value to the minimum for $x$, but possibly it is.