A geometrical problem
I guess the following problem is kind of classical, but it is funny anyway.
This time I won't provide any hints untill someone tries to solve the problem (even with an incorrect/totally wrong answer).
***
Problem:
Let [tex]$R$[/tex] be a rectangle in the plane and [tex]$\{R_n\}_{n\in \{ 1,\ldots ,N\}}$[/tex] be a finite collection of smaller rectangles s.t.:
1. for all [tex]$n=1,\ldots ,N$[/tex], [tex]$R_n\subseteq R$[/tex];
2. [tex]$\bigcup_{n=1}^N R_n=R$[/tex].
Prove that the following holds:
[tex]$\text{Each } R_n \text{ has at least one side of integer length} \quad \Rightarrow \quad R \text{ has at least one side of integer length}$[/tex].
This time I won't provide any hints untill someone tries to solve the problem (even with an incorrect/totally wrong answer).
***
Problem:
Let [tex]$R$[/tex] be a rectangle in the plane and [tex]$\{R_n\}_{n\in \{ 1,\ldots ,N\}}$[/tex] be a finite collection of smaller rectangles s.t.:
1. for all [tex]$n=1,\ldots ,N$[/tex], [tex]$R_n\subseteq R$[/tex];
2. [tex]$\bigcup_{n=1}^N R_n=R$[/tex].
Prove that the following holds:
[tex]$\text{Each } R_n \text{ has at least one side of integer length} \quad \Rightarrow \quad R \text{ has at least one side of integer length}$[/tex].
Risposte
"gugo82":
Problem:
Let [tex]$R$[/tex] be a rectangle in the plane and [tex]$\{R_n\}_{n\in \{ 1,\ldots ,N\}}$[/tex] be a finite collection of smaller rectangles s.t.:
1. for all [tex]$n=1,\ldots ,N$[/tex], [tex]$R_n\subseteq R$[/tex];
2. [tex]$\bigcup_{n=1}^N R_n=R$[/tex].
Prove that the following holds:
[tex]$\text{Each } R_n \text{ has at least one side of integer length} \quad \Rightarrow \quad R \text{ has at least one side of integer length}$[/tex].
"gugo82":
As suggested in the hint, we consider a [tex]$1$[/tex]-periodic function [tex]$\varphi$[/tex] with zero mean value over a period: for example, one can take:
- a sinusoid, [tex]$\varphi (t)=\varphi_1(t):=\sin 2k\ \pi t$[/tex] ([tex]$k\in \mathbb{N}$[/tex]), or
- a square wave, [tex]$\varphi (t)=\varphi_2(t):= \sum_{n=-\infty}^{+\infty} \chi_{[n, n+\tfrac{1}{2}[} (t)-\chi_{[n+\tfrac{1}{2} ,n+1[} (t)$[/tex], or
- a complex exponential, [tex]$\varphi(t)=\varphi_3 (t):=e^{2\pi t \text{i}}$[/tex].
Now, we set [tex]$f(x,y):=\varphi (x)\ \varphi (y)$[/tex] and realize that a sufficient condition for the integral of [tex]$f$[/tex] over a rectangle [tex]$I:=[a,b]\times [c,d]$[/tex] to be zero is that the length of at least one of the sides of [tex]$I$[/tex] is a positive integer: in fact one has:
[tex]$\iint_I f(x,y)\ \text{d} x\text{d} y =\int_a^b \varphi(x)\ \text{d}x \cdot \int_c^d \varphi (y)\ \text{d} y$[/tex]
and the claim follows from the mean value property of [tex]$\varphi$[/tex].
At this stage we can compute the integral of [tex]$f$[/tex] over [tex]$R$[/tex] using additivity, the hypothesis on the covering [tex]$\{ R_n\}_{n\in \{ 1,\ldots ,N\}}$[/tex] and the aforesaid sufficient condition:
[tex]$\iint_R f(x,y)\ \text{d} x\ \text{d} y =\sum_{n=1}^N \iint_{R_n} f(x,y)\ \text{d} x\ \text{d} y $[/tex]
[tex]$=\sum_{n=1}^N 0$[/tex]
[tex]$=0$[/tex];
on the other hand, if we let [tex]$R=[\alpha ,\beta]\times [\gamma, \delta]$[/tex], then:
[tex]$\iint_R f(x,y)\ \text{d} x\ \text{d} y = \int_\alpha^\beta \varphi (t)\ \text{d}t \cdot \int_\gamma^\delta \varphi (t)\ \text{d} t$[/tex].
Hence:
[tex]$\int_\alpha^\beta \varphi (t)\ \text{d}t \cdot \int_\gamma^\delta \varphi (t)\ \text{d} t =0$[/tex]
so that at least one of the factor in the LHS has to vanish by the zero-product property:
(*) [tex]$\int_\alpha^\beta \varphi (t)\ \text{d}t =0 \quad \text{or} \quad \int_\gamma^\delta \varphi (t)\ \text{d} t=0$[/tex].
Now we'd like to infer the thesis from one of the latter relations, but it is not possible indeed!
In fact (*) doesn't imply that [tex]$\beta-\alpha$[/tex] or [tex]$\delta -\gamma$[/tex] are positive integer, for the previous sufficient condition isn't a necessary one in the general case.
But we're too close to give up... Let's think about how we can overcome this last difficulty.
At this stage we have only one "degree of freedom", i.e. choosing [tex]$\varphi$[/tex] in a suitable manner.
The unique possible way to overcome our difficulty is to replace the previous sufficient condition with a necessary and sufficient condition for the integral [tex]$\int_a^b \varphi(t)\ \text{d} t$[/tex] to vanish, hence we have to choose [tex]$\varphi$[/tex] in such a way that the following stronger condition holds:
(A) [tex]$\int_a^b \varphi (t)\ \text{d} t =0 \quad \text{iff} \quad b-a \in \mathbb{N}$[/tex];
but this is actually possible if we choose [tex]$\varphi =\varphi_2$[/tex] or [tex]$\varphi =\varphi_3$[/tex] or [tex]$\varphi =\varphi_1$[/tex] with [tex]$k=1$[/tex] (check it!), so we can win!
Taking e.g. [tex]$\varphi =\varphi_2$[/tex], the zero-product property and condition (A) imply that [tex]$R$[/tex] has at least one side of integer length, which was the claim. [tex]$\square$[/tex]
***
The function [tex]$f$[/tex] obtained by choosing [tex]$\varphi=\varphi_2$[/tex] can be interpreted in a nice intuitive way.
In fact, we can divide the whole coordinate plane into squares of length [tex]$\frac{1}{2}$[/tex] as an infinite chessboard, i.e. alternating black and white squares; let's say that whites [tex]$W_{n,m}$[/tex] are the ones having left-lower vertex in [tex]$(\tfrac{n}{2},\tfrac{m}{2})$[/tex] with [tex]$n,m$[/tex] sharing the same parity, and the blacks [tex]$B_{n,m}$[/tex] having left-lower vertex in [tex]$(\tfrac{n}{2},\tfrac{m}{2})$[/tex] where [tex]$n,m$[/tex] have different parity.
If we associate the number [tex]$1$[/tex] to each [tex]$W_{n,m}$[/tex] and the number [tex]$-1$[/tex] to each [tex]$B_{n,m}$[/tex], then [tex]$f(x,y)=\sum_{n,m=-\infty}^{+\infty} \chi_{W_{n,m}}(x,y) -\chi_{B_{n,m}}(x,y)$[/tex].
Condition [tex]$\iint_I f(x,y)\ \text{d} x\ \text{d} y=0$[/tex] then ammounts to say that white and black areas contained in the rectangle [tex]$I$[/tex] are equal, and condition (A) ensures that this happens if and only if [tex]$R$[/tex] has at least a side of integer length.
From this intuitive point of view, the solution of the problem is quite obvious: by hypothesis, in each [tex]$R_n$[/tex] the black and white areas are the same, hence this fact holds in the whole of [tex]$R$[/tex]; therefore [tex]$R$[/tex] has to have a side of integer lenght.
[asvg]xmin=-3; xmax=3; ymin=-3; ymax=3;
noaxes();
fill="black";
rect([-3.5,-3.5],[-3,-3]); rect([-3,-3],[-2.5,-2.5]); rect([-2.5,-2.5],[-2,-2]); rect([-2,-2],[-1.5,-1.5]); rect([-1.5,-1.5],[-1,-1]); rect([-1,-1],[-0.5,-0.5]); rect([-0.5,-0.5],[0,0]); rect([0,0],[0.5,0.5]); rect([0.5,0.5],[1,1]); rect([1,1],[1.5,1.5]); rect([1.5,1.5],[2,2]); rect([2,2],[2.5,2.5]); rect([2.5,2.5],[3,3]); rect([3,3],[3.5,3.5]);
rect([-2.5,-3.5],[-2,-3]); rect([-2,-3],[-1.5,-2.5]); rect([-1.5,-2.5],[-1,-2]); rect([-1,-2],[-0.5,-1.5]); rect([-0.5,-1.5],[-0,-1]); rect([-0,-1],[0.5,-0.5]); rect([0.5,-0.5],[1,0]); rect([1,0],[1.5,0.5]); rect([1.5,0.5],[2,1]); rect([2,1],[2.5,1.5]); rect([2.5,1.5],[3,2]); rect([3,2],[3.5,2.5]);
rect([-1.5,-3.5],[-1,-3]); rect([-1,-3],[-0.5,-2.5]); rect([-0.5,-2.5],[-0,-2]); rect([-0,-2],[0.5,-1.5]); rect([0.5,-1.5],[1,-1]); rect([1,-1],[1.5,-0.5]); rect([1.5,-0.5],[2,0]); rect([2,0],[2.5,0.5]); rect([2.5,0.5],[3,1]); rect([3,1],[3.5,1.5]);
rect([-0.5,-3.5],[0,-3]); rect([0,-3],[0.5,-2.5]); rect([0.5,-2.5],[1,-2]); rect([1,-2],[1.5,-1.5]); rect([1.5,-1.5],[2,-1]); rect([2,-1],[2.5,-0.5]); rect([2.5,-0.5],[3,0]); rect([3,0],[3.5,0.5]);
rect([0.5,-3.5],[1,-3]); rect([1,-3],[1.5,-2.5]); rect([1.5,-2.5],[2,-2]); rect([2,-2],[2.5,-1.5]); rect([2.5,-1.5],[3,-1]); rect([3,-1],[3.5,-0.5]);
rect([1.5,-3.5],[2,-3]); rect([2,-3],[2.5,-2.5]); rect([2.5,-2.5],[3,-2]); rect([3,-2],[3.5,-1.5]);
rect([2.5,-3.5],[3,-3]); rect([3,-3],[3.5,-2.5]);
rect([3.5,-3.5],[4,-3]);
rect([-3.5,-2.5],[-3,-2]); rect([-3,-2],[-2.5,-1.5]); rect([-2.5,-1.5],[-2,-1]); rect([-2,-1],[-1.5,-0.5]); rect([-1.5,-0.5],[-1,0]); rect([-1,0],[-0.5,0.5]); rect([-0.5,0.5],[0,1]); rect([0,1],[0.5,1.5]); rect([0.5,1.5],[1,2]); rect([1,2],[1.5,2.5]); rect([1.5,2.5],[2,3]); rect([2,3],[2.5,3.5]); rect([2.5,3.5],[3,4]); rect([3,4],[3.5,4.5]);
rect([-3.5,-1.5],[-3,-1]); rect([-3,-1],[-2.5,-0.5]); rect([-2.5,-0.5],[-2,0]); rect([-2,0],[-1.5,0.5]); rect([-1.5,0.5],[-1,1]); rect([-1,1],[-0.5,1.5]); rect([-0.5,1.5],[0,2]); rect([0,2],[0.5,2.5]); rect([0.5,2.5],[1,3]); rect([1,3],[1.5,3.5]); rect([1.5,3.5],[2,4]);
rect([-3.5,-0.5],[-3,0]); rect([-3,0],[-2.5,0.5]); rect([-2.5,0.5],[-2,1]); rect([-2,1],[-1.5,1.5]); rect([-1.5,1.5],[-1,2]); rect([-1,2],[-0.5,2.5]); rect([-0.5,2.5],[0,3]); rect([0,3],[0.5,3.5]); rect([0.5,3.5],[1,4]);
rect([-3.5,0.5],[-3,1]); rect([-3,1],[-2.5,1.5]); rect([-2.5,1.5],[-2,2]); rect([-2,2],[-1.5,2.5]); rect([-1.5,2.5],[-1,3]); rect([-1,3],[-0.5,3.5]); rect([-0.5,3.5],[0,4]);
rect([-3.5,1.5],[-3,2]); rect([-3,2],[-2.5,2.5]); rect([-2.5,2.5],[-2,3]); rect([-2,3],[-1.5,3.5]); rect([-1.5,3.5],[-1,4]);
rect([-3.5,2.5],[-3,3]); rect([-3,3],[-2.5,3.5]); rect([-2.5,3.5],[-2,4]);
rect([-3.5,3.5],[-3,4]);
fill="none"; stroke="red"; strokewidth=3; rect([-2.35,-2],[2.65,2.75]);[/asvg]
Considering that nobody seems to be working on this problem (except blackbishop, who told me he's kinda stuck after my counterexample), I'd like to post a solution.
So, if someone is currently working on this problem and doesn't want to read a solution before posting his try, just let me know; otherwise tomorrow I'll post the solution I know.
So, if someone is currently working on this problem and doesn't want to read a solution before posting his try, just let me know; otherwise tomorrow I'll post the solution I know.
@blackbishop13: Your conjecture is false if the decomposition is infinite.
In fact, let [tex]$R=[0,b]\times [0,h]$[/tex] and [tex]$(b_n),(h_n)$[/tex] two positive sequences s.t. [tex]$\sum_{n=1}^{+\infty} b_n=b, \sum_{n=1}^{+\infty} h_n=h$[/tex] (for example [tex]$b_n=\tfrac{b}{2^n}, h_n=\tfrac{b}{2^n}$[/tex]); one can build an infinite decomposition of [tex]$R$[/tex] in the following manner:
[tex]$R_1=[0,b]\times [0,h_1]$[/tex]
[tex]$R_2=[b-b_1,b]\times [h_1,h]$[/tex]
[tex]$R_3=[0,b-b_1]\times [h_1,h_1+h_2]$[/tex]
[tex]$R_4=[b-b_1-b_2,b-b_1]\times [h_1+h_2,h]$[/tex]
[tex]$R_5=[0,b-b_1-b_2]\times [h_1+h_2,h_1+h_2+h_3]$[/tex]
[tex]$R_6=[b-b_1-b_2-b_3,b-b_1-b_2] \times [h_1+h_2+h_3,h]$[/tex]...
and, in general:
[tex]$R_{2m}=\left[ b-\sum_{n=1}^m b_n, b-\sum_{n=1}^{m-1} b_n\right] \times \left[ \sum_{n=1}^m h_n,h\right]$[/tex]
[tex]$R_{2m+1}=\left[ 0,b-\sum_{n=1}^m b_n\right] \times \left[ \sum_{n=1}^m h_n,\sum_{n=1}^{m+1} h_n\right]$[/tex]
(use the convention [tex]$\sum_{n=1}^0 \ldots =0$[/tex]). The idea of the construction is, say, to draw a fishbone (see the following picture).
[asvg]xmin=0;xmax=7;ymin=-1;ymax=6;
noaxes();
rect([0,0],[7,5]);
line([0,1],[7,1]); line([6,1],[6,5]); line([0,2],[6,2]); line([5,2],[5,5]); line([0,2.5],[5,2.5]); line([4.5,2.5],[4.5,5]);
text([3.5,0.5],"R1"); text([6.5,3],"R2"); text([3,1.5],"R3"); text([5.5,3.5],"R4"); text([2.5,2.25],"R5"); text([4.75,3.75],"R6");[/asvg]
In this way the sequence [tex]$(R_N)$[/tex] covers [tex]$R$[/tex] (with the exception of the point [tex]$(0,h)$[/tex], but it is not a real problem for how I think to use this construction...).
But, quite surprisingly, your conjecture is false for each [tex]$N\geq 5$[/tex] even in the hypotesis of the problem (i.e. the finiteness of the covering).
For example, in the case [tex]$N=5$[/tex] one can decompose [tex]$R$[/tex] in the way shown in the next figure:
[asvg]xmin=0;xmax=7;ymin=-1;ymax=6;
noaxes();
rect([0,0],[7,5]);
line([0,1],[6,1]); line([6,0],[6,4]); line([7,4],[1,4]); line([1,5],[1,1]);[/asvg]
and, for greater [tex]$N$[/tex], one can add [tex]$N-5$[/tex] rectangles putting them in a fishbone shape as seen in the first counterexample (see next picture for the case [tex]$N=7$[/tex]).
[asvg]xmin=0;xmax=9;ymin=-2;ymax=7;
noaxes();
rect([0,0],[9,6]);
line([0,1],[6,1]); line([6,0],[6,4]); line([7,4],[1,4]); line([1,5],[1,1]); line([7,0],[7,5]); line([0,5],[9,5]);[/asvg]
The pictures show that there actually exist finite coverings [tex]$\{ R_1,\ldots ,R_N\}$[/tex] of any rectangle [tex]$R$[/tex] s.t. none of the couples [tex]$R_i,R_j$[/tex] with [tex]$i\neq j \in \{ 1,\ldots ,N\}$[/tex] have two sides in common.
In fact, let [tex]$R=[0,b]\times [0,h]$[/tex] and [tex]$(b_n),(h_n)$[/tex] two positive sequences s.t. [tex]$\sum_{n=1}^{+\infty} b_n=b, \sum_{n=1}^{+\infty} h_n=h$[/tex] (for example [tex]$b_n=\tfrac{b}{2^n}, h_n=\tfrac{b}{2^n}$[/tex]); one can build an infinite decomposition of [tex]$R$[/tex] in the following manner:
[tex]$R_1=[0,b]\times [0,h_1]$[/tex]
[tex]$R_2=[b-b_1,b]\times [h_1,h]$[/tex]
[tex]$R_3=[0,b-b_1]\times [h_1,h_1+h_2]$[/tex]
[tex]$R_4=[b-b_1-b_2,b-b_1]\times [h_1+h_2,h]$[/tex]
[tex]$R_5=[0,b-b_1-b_2]\times [h_1+h_2,h_1+h_2+h_3]$[/tex]
[tex]$R_6=[b-b_1-b_2-b_3,b-b_1-b_2] \times [h_1+h_2+h_3,h]$[/tex]...
and, in general:
[tex]$R_{2m}=\left[ b-\sum_{n=1}^m b_n, b-\sum_{n=1}^{m-1} b_n\right] \times \left[ \sum_{n=1}^m h_n,h\right]$[/tex]
[tex]$R_{2m+1}=\left[ 0,b-\sum_{n=1}^m b_n\right] \times \left[ \sum_{n=1}^m h_n,\sum_{n=1}^{m+1} h_n\right]$[/tex]
(use the convention [tex]$\sum_{n=1}^0 \ldots =0$[/tex]). The idea of the construction is, say, to draw a fishbone (see the following picture).
[asvg]xmin=0;xmax=7;ymin=-1;ymax=6;
noaxes();
rect([0,0],[7,5]);
line([0,1],[7,1]); line([6,1],[6,5]); line([0,2],[6,2]); line([5,2],[5,5]); line([0,2.5],[5,2.5]); line([4.5,2.5],[4.5,5]);
text([3.5,0.5],"R1"); text([6.5,3],"R2"); text([3,1.5],"R3"); text([5.5,3.5],"R4"); text([2.5,2.25],"R5"); text([4.75,3.75],"R6");[/asvg]
In this way the sequence [tex]$(R_N)$[/tex] covers [tex]$R$[/tex] (with the exception of the point [tex]$(0,h)$[/tex], but it is not a real problem for how I think to use this construction...).
But, quite surprisingly, your conjecture is false for each [tex]$N\geq 5$[/tex] even in the hypotesis of the problem (i.e. the finiteness of the covering).
For example, in the case [tex]$N=5$[/tex] one can decompose [tex]$R$[/tex] in the way shown in the next figure:
[asvg]xmin=0;xmax=7;ymin=-1;ymax=6;
noaxes();
rect([0,0],[7,5]);
line([0,1],[6,1]); line([6,0],[6,4]); line([7,4],[1,4]); line([1,5],[1,1]);[/asvg]
and, for greater [tex]$N$[/tex], one can add [tex]$N-5$[/tex] rectangles putting them in a fishbone shape as seen in the first counterexample (see next picture for the case [tex]$N=7$[/tex]).
[asvg]xmin=0;xmax=9;ymin=-2;ymax=7;
noaxes();
rect([0,0],[9,6]);
line([0,1],[6,1]); line([6,0],[6,4]); line([7,4],[1,4]); line([1,5],[1,1]); line([7,0],[7,5]); line([0,5],[9,5]);[/asvg]
The pictures show that there actually exist finite coverings [tex]$\{ R_1,\ldots ,R_N\}$[/tex] of any rectangle [tex]$R$[/tex] s.t. none of the couples [tex]$R_i,R_j$[/tex] with [tex]$i\neq j \in \{ 1,\ldots ,N\}$[/tex] have two sides in common.
Actually I don't know how to prove your conjecture on the existence of two smaller rectangles with an integer side in common; so I would provide a different (and more analytic) kind of...
English note: "funny" is something that makes people laugh.
a problem should be described as "enjoyable" for instance.
About the problem: i have an incomplete demonstration, but I think I reached a good point.
I think we could prove it by induction on $N$, the number of small rectangles.
$N=1$ done.
it is not necesary now, but it's useful to consider $N=2$: the only way is to divide $R$ in $R_1,R_2$ which have a side in common.
the proof is evident: if the common side is of integer lenght, done. if else (note that the only other possiblity is that each of the $R_i$ has the not-common side of integer lenght), the sum of integers is integer, done.
$N \Rightarrow N+1$
Let $R$ be divided in $N+1$ rectangles, then if two of the $R_i$ have a side in common, let them be $R_a$ and $R_b$, we create a new set of $R_j$ where we simply substitute $R_a$ and $R_b$ with the "fusion" of them, $R_c$.
$R_j$ are $N$ rectangles and they respect the other hypotesis, since we proved that if we fuse two rectangles with one integer side, we obtain a rectangle with one integer side. Then we use the unductive hypotesis, and we have won.
the missing part is to show that this is the only possibility: since $N$ is finite, there exist at least two rectangles with a side in common.
a problem should be described as "enjoyable" for instance.
About the problem: i have an incomplete demonstration, but I think I reached a good point.
I think we could prove it by induction on $N$, the number of small rectangles.
$N=1$ done.
it is not necesary now, but it's useful to consider $N=2$: the only way is to divide $R$ in $R_1,R_2$ which have a side in common.
the proof is evident: if the common side is of integer lenght, done. if else (note that the only other possiblity is that each of the $R_i$ has the not-common side of integer lenght), the sum of integers is integer, done.
$N \Rightarrow N+1$
Let $R$ be divided in $N+1$ rectangles, then if two of the $R_i$ have a side in common, let them be $R_a$ and $R_b$, we create a new set of $R_j$ where we simply substitute $R_a$ and $R_b$ with the "fusion" of them, $R_c$.
$R_j$ are $N$ rectangles and they respect the other hypotesis, since we proved that if we fuse two rectangles with one integer side, we obtain a rectangle with one integer side. Then we use the unductive hypotesis, and we have won.
the missing part is to show that this is the only possibility: since $N$ is finite, there exist at least two rectangles with a side in common.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo