Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
1  
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
1  
@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
show 3 more comments

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
"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
show 2 more comments

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.