6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Jun 26, 2013 at 19:00
  • $\begingroup$ 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}$. $\endgroup$ Jun 26, 2013 at 19:06
  • 1
    $\begingroup$ 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^+$. $\endgroup$ Jun 26, 2013 at 20:15
  • 1
    $\begingroup$ 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? $\endgroup$ Jun 27, 2013 at 10:06
  • 1
    $\begingroup$ @Maarten: I think he means to find min x st for all a1, a2, exists k, l, n. $\endgroup$
    – domotorp
    Jun 27, 2013 at 16:39

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ "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? $\endgroup$ Jun 28, 2013 at 0:57
  • $\begingroup$ 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. $\endgroup$ Jun 28, 2013 at 1:20
  • $\begingroup$ Out of curiosity, where does this problem come from? $\endgroup$ Jun 28, 2013 at 1:28
  • $\begingroup$ 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$. $\endgroup$ Jun 28, 2013 at 1:32
  • $\begingroup$ 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? $\endgroup$ Jun 30, 2013 at 1:36
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ How do you calculate unions continuously with $n\in\mathbb{R}$? Geometrically you reckon? $\endgroup$ Jun 26, 2013 at 19:01
  • $\begingroup$ 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. $\endgroup$ Jun 26, 2013 at 20:25
  • $\begingroup$ And you'd have to keep track of all the infinitely many squares in the checkerboard? Seems implausible. $\endgroup$ Jun 26, 2013 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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