Can the 'brick wall' (infinite in all directions) drawn at the picture be made of wires of length $1, 2, 3, \dots$ (each positive integral length occurs exactly once)? (Wires can be bent but should not overlap; size of a 'brick' is $1\times 2$). [asy][asy] unitsize(0.5 cm); for(int i = 1; i <= 9; ++i) { draw((0,i)--(10,i)); } for(int i = 0; i <= 4; ++i) { for(int j = 0; j <= 4; ++j) { draw((2*i + 1,2*j)--(2*i + 1,2*j + 1)); } } for(int i = 0; i <= 3; ++i) { for(int j = 0; j <= 4; ++j) { draw((2*i + 2,2*j + 1)--(2*i + 2,2*j + 2)); } } [/asy][/asy]
Problem
Source:
Tags: calculus, integration, combinatorics
Zimbalono
03.08.2012 15:48
Assume that all the short pieces of wire (shorter than 30 units, say) have been used up. Every T-junction requires the start of at least one new wire. So the circled region contains the ends of at least 16 wires, all too long to have both ends in the region. But no more than 10 wires can leave the region.
[asy][asy]
unitsize(0.5 cm);
for(int i = 1; i <= 9; ++i) {
draw((0,i)--(10,i));
}
for(int i = 0; i <= 4; ++i) {
for(int j = 0; j <= 4; ++j) {
draw((2*i + 1,2*j)--(2*i + 1,2*j + 1));
}
}
for(int i = 0; i <= 3; ++i) {
for(int j = 0; j <= 4; ++j) {
draw((2*i + 2,2*j + 1)--(2*i + 2,2*j + 2));
}
}
draw((2.5,4.5){up}..{right}(5.25,6.5));
draw((5.25,6.5){right}..{down}(7.5,4.5));
draw((2.5,4.5){down}..{right}(5.25,2.5));
draw((5.25,2.5){right}..{up}(7.5,4.5));
[/asy][/asy]
Kayak
09.06.2018 12:58
Please check my solution (I guess this uses the exact same idea as the above solution but produces a much sharp bound on the length of the wires. Also I think I my solution generalizes without much changes to some classes of periodic tiling in which the density of vertices with odd degree is nonzero)
I claim that it's impossible.
We use some commonly used asymptotic notations through the solution: for two functions $f(x), g(x)$, with $f(x), g(x) > 0$ for $x > 0$, we write
$f(x) = \Theta(g(x))$ if $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)}$ coverges to a positive nonzero constant.
$f(x) = \Omega(g(x))$ if $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)}$ is bounded below by some positive nonzero constant
$f(x) = O(g(x))$ if $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)}$ is bounded above by some positive nonzero constant
Let $A = \{a_1, a_2, a_3, \cdots \}$ with $a_1 \leq a_2 \leq a_3 \leq \cdots$ be a nondecreasing infinite sequence of positive integers of the total wire lengths. While in the question $a_n = n$, we infact prove it for all such sequences with $a_n = \Omega(n^{\epsilon})$ for some fixed positive real $\epsilon$ and all $n \geq 1$. Note that this also implies $\sum_{i=1}^{n} a_i = \Omega(n^{1+\epsilon})$.
Firstly note that the tiling in the questions with rectangles are basically tiling with hexagons (because pulling the rectangles in the middle through the longer side transforms into a hexagon), so we use hexagons and paths instead of wires because the proof is easier to write up. Define the distance between two hexagons as the number of hexagons between them in the shortest path going from one hexagon to the other. Fix a hexagon as the centre.
Assume for the sake of the contradiction, that it's infact possible. Then split the infinite honeycomb into edge disjoint nonoverlapping paths with lenghts from $A$.
Define $n$-honeycomb as the union of hexagons which are atmax distance $n$ from the centre. Note these asymptotic bounds, which are easily proved by writing down the values of them explicitly (by using recursion):
Number of vertices in the $n$-honeycomb = $\Theta(n^2)$
Number of edges in the $n$-honeycomb = $\Theta(n^2)$
Number of vertices in the boundary of the $n$-honeycomb = $\Theta(n)$
If a path starts inside the $n$-honeycomb and extends outside the $n$-honeycomb (The path may end outside the $n$-honeycomb or come back again inside it, but what matters is that it has a portion outside the $n$-honeycomb), then it must pass through atleast one boundary vertex of the $n$-honeycomb. Also note that a boundary vertex can allow only one path through go outside/come inside. Hence
$t_n \overset{\text{def}}{=}$ Number of paths with some porition inside the $n$-honeycomb and some portion outside the $n$-honeycomb $\leq$ Number of vertices in the boundary of the $n$-honeycomb = $\Theta(n)$. Hence, $t_n = O(n)$
Consider all $s_n$ paths which lies entirely inside the $n$-honeycomb. The sum of lengths of all these paths should not be more than the total numbe of edges inside the $n$-honeycomb, which is $\Theta(n^2)$. On the other hand, since $\{a_i\}$ is nondecreasing, the sum of lengths of these $s_n$ paths should be not less than $\sum_{i=1}^{s_n} a_i = \Omega(s_n^{1+\epsilon})$. Combining the previous two sentences and with some heavy abuse of notation, we see $\Theta(n^2) \geq \Omega(s_n^{1+\epsilon})$, so it's not hard to bound everything using the definition of the symbols and conclude that
$s_n = O(n^{\frac{2}{1+\epsilon}}) = O(n^{2-2\epsilon}) = O(n^{2-\epsilon})$
Combining the bound for $t_n$, we also get
$s_n+t_n = O(s_n+t_n) = O(\Theta(n) + O(n^{2-\epsilon})) = O(n^{2-\epsilon})$
Now, note the following easy but crucial claim:
Claim : For every vertex $v$, there's a path starting from/ending at $v$
Proof : This is easy. Assume not. Then every path which enters $v$ immidiately comes out from $v$, but this implies the degree of $v$ is even. But as the degree of each vertex is $3$, which is odd, this is impossible, so we're done.
, which implies (with double counting for the last inequality) that: $3 \times \text{Number of vertices in the n-honeycomb} \geq s_n+t_n \geq \frac{\text{Number of vertices in the n-honeycomb}}{2}$, hence
$s_n+t_n = \Theta(\text{Number of vertices in the n-honeycomb}) = \Theta(n^2)$
Now we have arrived a contradiction ! Since $n^2$ grows faster than $n^{2-\epsilon}$, for any function $f(n)$ we can't have $f(n) = \Theta(n^2)$ and $f(n) = O(n^{2-\epsilon}))$ simultaneously. But letting $f(n) = s_n+t_n$, this is a contradiction !