3
$\begingroup$

A square of side one contains two squares of sides $a$ and $b$ having non-overlapping interiors. How to prove the inequality $a+b≤1$ with Mathematica? The same question in three dimensions and higher dimensions.

Here is my attempt. The squares are defined as ra = RotationTransform[ Rectangle[{c1 - a/2, c2 - a/2}, {c1 + a/2, c2 + a/2}], \[Theta]1] and rb = RotationTransform[ Rectangle[{d1 - b/2, d2 - b/2}, {d1 + b/2, d2 + b/2}], \[Theta]2]. Then I'd like to Maximize or NMaximize the objective function a+b over a,b,c1,c2,d1,d2, , \[Theta]2, but I face the problems with the restrictions: how to write down these are subsets of Rectangle[] and the non-overlapping of the square interiors in WL.

Addition. I am working with it. As I understand now , it should be something like ra[a_?NumericQ,b_?NumericQ,c1_?NumericQ,c2_?NumericQ,d1_?NumericQ,d2_?NumericQ,\[Theta]1_?NumericQ] := Rotate[ Rectangle[{c1 - a/2, c2 - a/2}, {c1 + a/2, c2 + a/2}], \[Theta]1] etc.

$\endgroup$
2
  • 1
    $\begingroup$ It seems that rb = RotationTransform[ Rectangle[{d1 - b/2, d2 - b/2}, {d1 + a/2, d2 + a/2}], \[Theta]2] should be rb = RotationTransform[ Rectangle[{d1 - b/2, d2 - b/2}, {d1 + b/2, d2 + b/2}], \[Theta]2] $\endgroup$
    – cvgmt
    Oct 29, 2022 at 1:10
  • 1
    $\begingroup$ @cvgmt: Thank you. Fixed. $\endgroup$
    – user64494
    Oct 29, 2022 at 4:52

2 Answers 2

4
$\begingroup$

Here is a computer assisted proof. I do not know how to make it fully automatic.

Lemma A square of unit length inside the first quadrant with center in $[0,1]\times[0,1]$ contains the point (1,1).

∎ Without loss of generality consider a square that touches the $x$- and $y$-axes such as shown below. Let the angle be $\phi$ as defined in the figure.

w = 10 Degree;
SquareC = {1/2 (Sin[w] + 1), 1/2 (Sin[w] + 1)};
SquareTopLeft = {0, Cos[w]};
SquareBottomLeft = {Sin[w], 0};
SquareTopRight = {Cos[w], Cos[w] + Sin[w]};
SquareBottomRight = {Cos[w] + Sin[w], Sin[w]};
Origin = {0, 0};
Graphics[{LightBlue, Rectangle[],
  LightRed, Opacity[0.5], 
  Translate[Rotate[Rectangle[], w], {1/2 Sin[w], 1/2 Sin[w]}],
  Opacity[1], Red, PointSize[Large], Point[SquareC],
  Black, Point[{1, 1}],
  InfiniteLine[{SquareTopRight, SquareBottomRight}], 
  Text["(1,1)", {0.95, 0.95}], Gray, 
  Point[{SquareTopRight, SquareBottomRight}],
  Blue, InfiniteLine[{SquareBottomLeft, SquareBottomRight}],
  InfiniteLine[{Origin, SquareBottomLeft}], 
  Circle[Origin, 0.8, {-0.2 w, 1.2 w}],
  Text["\[Phi]", {0.85, 0.05}]
  }]

enter image description here

The equation of the line passing through its two corners reads $$ (y-\sin\phi)=-\frac{\cos\phi}{\sin\phi}(x-\sin\phi-\cos\phi). $$ Let us substitute $x=1$ and verify that $y>1$ (if this is true for all angles $\phi$ the $(1,1)$ point is always covered by the square):

Reduce[(Sin[f]^2 - Cos[f] (1 - Cos[f] - Sin[f]))/Sin[f] >= 1 && Pi/2 > f > 0]

$$0<\phi<\frac{\pi }{2}.$$

This is the only place where MA was needed. In the remaining part, MA is only used to illustrate the proof. ∎

∎ Now the remaining proof consists of four steps. Let us conduct the proof for each fixed size of a bigger square $k=a$. In view of the lemma above, for $k=1/2$ we have $a+b\le 1$ for otherwise $(1/2,1/2)$ would be covered by both squares.

I. Let $k>1/2$ and larger square A with size $a=k$ be in the left-bottom corner without loss of generality. Dark blue area denotes the possible position of its center. Light blue background denotes the considered unit square. The center of the second square B with size $b>1-k$ cannot be located in the red area for otherwise two squares will cover the $(k, k)$ point.

k = 0.6;
Graphics[{LightBlue, Rectangle[],
  Blue, Rectangle[{0, 0}, {k, k}],
  EdgeForm[Directive[Red]], LightRed, Rectangle[{k, k}, {1, 1}],
  Black, Text[Style["A|a=k>1/2", 36], {k/2, k/2}]}]

enter image description here Step I: center of B cannot lie in the top-right square

II. By the same argument two other red squares cannot hold the center of B with size $b>1-k$. Thus, there are only 2 possibilities left. One of them is depicted and marked as green. It is sufficient to consider only one, the other one can be treated analogously.

k = 0.6;
Graphics[{LightBlue, Rectangle[],
  Blue, Rectangle[{0, 0}, {k, k}],
  LightRed, EdgeForm[Directive[Red]], Rectangle[{k, k}, {1, 1}], 
  Rectangle[{1, 2 k - 1}, {k, k}], Rectangle[{2 k - 1, 1}, {k, k}], 
  EdgeForm[Green],
  LightGreen, Rectangle[{k, 0}, {1, 2 k - 1}],
  Black, Text[Style["A|a=k>1/2", 36], {k/2, k/2}], 
  Text[Style["B|b>1-k", 36], {(1 + k)/2, (2 k - 1)/2}]}]

enter image description here Step II: two more areas can be eliminated

III. If the center of B lies in the green area, the center of A cannot lie in the top left square (red).

k = 0.6;
Graphics[{LightBlue, Rectangle[],
  EdgeForm[Green], LightGreen, Rectangle[{k, 0}, {1, 1 - k}],
  LightRed, EdgeForm[Directive[Red]], Rectangle[{0, 1 - k}, {k, 1}],
  Black, Text[Style["B|b>1-k", 36], {(1 + k)/2, (1 - k)/2}]}]

enter image description here Step III: reverse the argument, eliminate an area for A

IV. The only configuration which supports $a+b > 1$ is shown below:

k = 0.6;
Graphics[{LightBlue, Rectangle[],
  EdgeForm[Green], LightGreen, Rectangle[{0, 0}, {k, 1 - k}], 
  Rectangle[{k, 0}, {1, 1 - k}],
  Black, Text[Style["A|a\[LessEqual]1-k", 36], {k/2, (1 - k)/2}], 
  Text[Style["B|b>1-k", 36], {(1 + k)/2, (1 - k)/2}],
  Red, Text[Style["Contradiction", 21], {1/2, 1/2}]}]

enter image description here Step IV: Both centers must lie in the lower part of the unit square.

However, it contradicts the initial assumption. Thus $$ a+b \le 1 $$ as requested. ∎

$\endgroup$
5
  • $\begingroup$ The first place I don't understand is " Without loss of generality consider a square that touches the $x$- and $y$-axes such as shown below". Thank you anyway. $\endgroup$
    – user64494
    Oct 29, 2022 at 4:52
  • $\begingroup$ @user64494 if a unit square with center in $[0,1]\times[0,1]$ can be found such that it does not cover $(1,1)$ and does not touch $x$, $y$-axes then we can translate it (first along $x$ and then along $y$) so that it touches axes. By this process $(1,1)$ will still remain uncovered. Thus, if a square violates the Lemma, it would be possible to find it among squares that touch $x$, $y$-axes. $\endgroup$
    – yarchik
    Oct 29, 2022 at 6:48
  • $\begingroup$ Sorry, this is not serious. I'll be waiting for reach-in-content answers. I also think about it. $\endgroup$
    – user64494
    Oct 29, 2022 at 6:52
  • $\begingroup$ @user64494 Why is it not serious? Of course, it is not a numerical minimization proof as you requested. But even if it is possible, I doubt that such a numerical proof would be seriously accepted by mathematical community. The only known to me numerical proof of this kind is the Tomas Hales proof of the Kepler conjecture. Here, since a simple proof (in 2D) can be given, I doubt that there is a need for numerical minimization. For higher dimensions the question might still be open, I don't know. $\endgroup$
    – yarchik
    Oct 29, 2022 at 18:47
  • $\begingroup$ @user64494 I actually have a shorter proof of your inequality in 2D. It is based on the same idea, relies on the covering property of the (1,1) point, but replaces steps II-IV with some other considerations. Are you interested? $\endgroup$
    – yarchik
    Nov 7, 2022 at 13:18
1
$\begingroup$

Too long for a comment. Here is my attempt to anser the question. First, we define two squares by

ra[a_?NumericQ, c1_?NumericQ, c2_?NumericQ, \[Theta]1_?NumericQ] := 
RegionConvert[ TransformedRegion[Rectangle[{c1 - a/2, c2 - a/2}, {c1 + a/2, c2 + a/2}],
RotationTransform[\[Theta]1]], "Implicit"];
rb[b_?NumericQ, d1_?NumericQ, d2_?NumericQ, \[Theta]2_?NumericQ] := 
RegionConvert[ TransformedRegion[Rectangle[{d1 - b/2, d2 - b/2}, {d1 + b/2, d2 + b/2}],
RotationTransform[\[Theta]2]], "Implicit"];

Second, we write down the condition of non-overlapping the squares as

RegionMeasure[RegionIntersection[ra[a, c1, c2,\[Theta]1],rb[b, d1, d2, \[Theta]2]], 2] == 0

and the the conditions that the squares are subsets of the unit square as all 8 vertices belong to the unit square, for example, (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[1]] <= 1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[2]] <= 1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[1]] >= 0 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[2]] >= 0 etc.

Now i try an approximate solution of the problem, allowing a small intersection, with low accuracy and precision.

NMaximize[{a + b,   RegionMeasure[ RegionIntersection[ra[a, c1, c2, \[Theta]1], 
  rb[b, d1, d2, \[Theta]2]], 2] <= 0.01 && a > 0 && b > 0 && 
  c1 >= 0 && c2 >= 0 && d1 >= 0 && d2 >= 0 && c1 <= 1 && c2 <= 1 && 
  d1 <= 1 && d2 <= 1 && a <= 1 &&  b <= 1 && \[Theta]1 >= 0 && \[Theta]1 <= Pi/2 && 
\[Theta]2 >=  0 && \[Theta]2 <=  Pi/2 &&
(RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[1]] <=
 1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[2]] >= 
0 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[1]] <= 
1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 - a/2})[[2]] >= 
0 && (RotationMatrix[\[Theta]1] . {c1 - a/2, c2 - a/2})[[1]] <= 
1 && (RotationMatrix[\[Theta]1] . {c1 - a/2, c2 - a/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]1] . {c1 - a/2, c2 - a/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]1] . {c1 - a/2, c2 - a/2})[[2]] >= 
0 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[1]] <= 
1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]1] . {c1 + a/2, c2 + a/2})[[2]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 + b/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 + b/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 + b/2})[[2]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 - b/2})[[1]] <= 
1 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 - b/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 - b/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 - b/2})[[2]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 - b/2, d2 - b/2})[[1]] <= 
1 && (RotationMatrix[\[Theta]2] . {d1 - b/2, d2 - b/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]2] . {d1 - b/2, d2 - b/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 - b/2, d2 - b/2})[[2]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 + b/2})[[1]] <= 
1 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 + b/2})[[2]] <= 
1 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 + b/2})[[1]] >= 
0 && (RotationMatrix[\[Theta]2] . {d1 + b/2, d2 + b/2})[[2]] >= 
0}, {a, b, c1, c2, d1, d2, \[Theta]1, \[Theta]2}, 
 AccuracyGoal -> 3, PrecisionGoal -> 3, Method -> {"RandomSearch", 
"SearchPoints" -> 10,   
 "InitialPoints" -> {{1/10, 1/10, 1/4, 3/8, 1/4, 7/8, 0,  Pi/6}, 
{1/10, 1/10, 1/4, 3/8, 1/2, 7/8, 0, 0}}}]

Unfortunately, executing it, I obtain an error

RegionMeasure::reg: RegionIntersection[ra[a,c1,c2,[Theta]1],rb[b,d1,d2,[Theta]2]] is not a correctly specified region.

which I don't understand since

Region[RegionIntersection[ra[1/4, 0, 0, 0], rb[1/4, 1/8, 0, Pi/4]]]

results in

enter image description here

Additionally, after that message the code is running without any result for hours.

Constructive suggestions are welcome.

Edit. Typos in the definition of rb: b instead of a and \[Theta]2 instead of [Theta]1` .

$\endgroup$

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.