# An easy-to-state elusive combinatorial problem

Let $a_1,a_2 \in \mathbb{Q}:a_1≥1,a_2≥1$. What should be the minimum value of $x\in\mathbb{R}$: $n∈[1,x]$ to ensure that $4k−3≤na_1≤4k−1$ such that $k∈N$ and $4l−3≤na_2≤4l−1$ such that $l∈N$ for all $a_1, a_2$?

Numerical computations suggest the answer to this is $3$ but I'm out of ideas how to prove this formally.

-
I don't think your question make's sense in its current form. Let a_1=a_2=4. Then 12 does not satisfy your inequalities, so 3 does not "ensure" what you are asking. – Stephen Sturgeon Jun 26 '13 at 19:00
In the case $a_1=a_2=4$ we select $n=\frac{5}{4}$ and that would render both $a_1, a_2 \in [5,7]$. The question is that no matter what $a_1$ and $a_2$ you go for, I can always find an $1\le n\le 3$ such that $4k−3≤na_1≤4k−1$ and $4l−3≤na_2≤4l−1$ where $k,l \in \mathbb{N}$. – Maaz-ul-Haq Jun 26 '13 at 19:06
Cases where $n=3^-$ is necessary include $b_1 \in (9/10,15/14), b_2 = 3/2^+$ or $a_1 \in (9/5,15/7), a_2 = 3^+$. – Douglas Zare Jun 26 '13 at 20:15
I have some problems with parsing this question. Could you please add "for all" and "there exists" quantifiers to your question so that it becomes unambiguous? – Maarten Derickx Jun 27 '13 at 10:06
@Maarten: I think he means to find min x st for all a1, a2, exists k, l, n. – domotorp Jun 27 '13 at 16:39

The bound is $3$. For readability, I'll change $(a_1, a_2)$ to $(x,y)$. Without loss of generality, $x \geq y$. We break into cases.

Case 1 (the main case): $y \geq 7/3$. In this case, there exists an integer $\ell$ such that $y \leq 4 \ell-3 < 4 \ell-1 \leq 3y$. As $r$ ranges from $(4 \ell-3)/y$ to $(4 \ell-1)/y$, the value of $rx$ increases by $2 (x/y) \geq 2$. Therefore, for some $r$ in this range, $rx$ must lie in an interval of the form $(4m-3,4m-1)$. For this $r$, we have $r \in [1,3]$ and $(rx, ry)$ of the desired form.

So, from now on, assume $y \leq 7/3$. Since this means $1 \leq y \leq 3$, if $4 \ell-3 \leq x \leq 4 \ell - 1$, we are done. So we may also assume that $4m-1 \leq x \leq 4m+1$ for some integer $m$.

Case 2: $y \leq 3x/(4m+1)$. In this case, take $r = (4m+1)/x$ to achieve $rx=4m+1$ and $ry \leq 3$. Note that $1 \leq r \leq 4m+1/4m-1 \leq 5/3 < 3$.

Note that, if $m \geq 2$, then $3x/(4m+1) \geq 3 (4m-1)/(4m+1) \geq 7/3$. So Cases $1$ and $2$ together cover all possible values for $y$ if $m \geq 2$. We are thus left to deal with $m=1$.

More precisely, we are left to deal with the triangle $T$ bounded by $x \geq 3$, $y \leq 7/3$ and $y \geq (3/5) x$. The vertices of $T$ are at $(3,9/5)$, $(3,7/3)$ and $(35/9, 7/3)$. It is easy to check that, for any point in this triangle, we can rescale it by a factor of $\leq 3$ to land in the square $[9,11] \times [5,7]$.

The equality is tight on $\{ 3 \} \times (9/5, 7/3)$ and on the mirror image $(9/5, 7/3) \times \{ 3 \}$, as suggested by Doug Zare.

-
"It is easy to check that, any point in this triangle, we can rescale it by a factor of $\leq 3$ to land in the square $[9,11]\times[5,7]$." Or precisely this? – Maaz-ul-Haq Jun 28 '13 at 0:57
I am actually interested in a general version of this problem where you have $a_1, a_2, a_3,... a_{\lambda-2} \in \mathbb{N}$ such that $a_i\geq 1$ for all $1\leq i\leq \lambda-2$ and it is conjectured that the bound is $x=\lambda-1$ such that $n\in[1,x]$ to ensure that all $a_i$ are contained within $\lambda-2$-dimensional hypercubes generated by $[\lambda (m-1)+1,\lambda m -1]$ in all dimensions. It would be quite a task to solve this in general as apparently the problem increases in difficulty as you increase the dimensions. – Maaz-ul-Haq Jun 28 '13 at 1:20
Out of curiosity, where does this problem come from? – David Speyer Jun 28 '13 at 1:28
It was inspired by the View Obstruction paper by Cusick, though this one is on a completely different route, more like scaling n-cubes to cover the entire totally positive orthant of $\mathbb{R}^n$. – Maaz-ul-Haq Jun 28 '13 at 1:32
Can Case $1$ and $2$ with $m\ne 1$ be given an inductive flavor to cover for all dimensions? Or do more cases arise when you have an increment in dimensions? – Maaz-ul-Haq Jun 30 '13 at 1:36

I can't comment on the question, so I will suggest an approach here. Resize the targets (partial checkerboards in R^2) by dividing by n, and stop when the union of the resizings covers the plane (or enough of it). Hint: don't expect a maximum for n.

Now I notice n is an arbitrary real, and not an integer. I believe there is an upper bound for n, simply because the squares block all lines of sight from the origin. 3 is looking reasonable as a bound now.

Now that I have drawn a picture of squares in a plane, it is evident to me that a number near 21/5 is the bound, as any ray from the origin through a point with coordinates greater than 1 must intersect a square at the next largest permissible coordinate in the "slower" direction which will happen before n is 5 and usually much sooner. I think a pair near (1, 5/3) will be close to the extreme case.

I see I have taken the wrong squares (-1 to +1 mod 4). The analysis to the posted problem is similar, but the constants change. I leave the details to others.

-
How do you calculate unions continuously with $n\in\mathbb{R}$? Geometrically you reckon? – Maaz-ul-Haq Jun 26 '13 at 19:01
You can imagine a union of a parameterized set of squares. Imagine drawing with a square shaped pen tip in a paint program, for example. – The Masked Avenger Jun 26 '13 at 20:25
And you'd have to keep track of all the infinitely many squares in the checkerboard? Seems implausible. – Maaz-ul-Haq Jun 26 '13 at 20:32