Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2018 September 8

From Wikipedia, the free encyclopedia
Mathematics desk
< September 7 << Aug | September | Oct >> September 9 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


September 8

[edit]

Hyperrectangle contains most of the cube, but not its vertices

[edit]

Let , and let , such that .

Is there a hyperrectangle H satisfies:

1.

2.

In 2D I was able to find such a hyperrectangle, but how about 3D and higher dimensions? Is there such a hyperrecangle? — Preceding unsigned comment added by 2.53.39.115 (talk) 07:45, 8 September 2018 (UTC)[reply]

First, the algebra is a bit simpler if you change the interval from [0, 1] to [-1, 1], just scale and translate accordingly. That said, I'm pretty sure that for n=3 the answer is no for any p and q. It is sufficient to show that if a rectangular cuboid H contains points (p, ±1, ±1), (±1, p, ±1), (±1, ±1, p), with -1<p<1 then H contains one of (±1, ±1, ±1). To prove this, let H be defined by
Lu ≤ u1x+u2y+u3z ≤ Mu
Lv ≤ v1x+v2y+v3z ≤ Mv
Lw ≤ w1x+w2y+w3z ≤ Mw
where u = (u1, u2, u3), v = (v1, v2, v3), w = (w1, w2, w3) are mutually orthogonal, non-zero vectors. Let
U = {(sign(u1), sign(u2), sign(u3)), (-sign(u1), -sign(u2), -sign(u3))} if all the ui are nonzero,
and
U = ∅ otherwise.
Similarly define V and W. The sets U, V and W have at most 2 elements each, and {(±1, ±1, ±1)} has eight elements, so the difference {(±1, ±1, ±1)}\(U∪V∪W) is non-empty, say
s = (s1, s2, s3)
is an element. We have s is one of the vertices of the cube, and I claim that s satisfies each of the three inequalities above. I'll prove the first inequality with the other two being similar. There are two possibilities, either some ui=0, or there is i so si and ui have the same sign, and j so that sj and uj have opposite signs. In the first case, take i=1, i=2 and i=3 being similar. Then u1=0 and note that
(p, s2, s3) ∈ H,
so
Lu ≤ u1p+u2s2+u3s3 ≤ Mu.
But u1=0 so
u1p+u2s2+u3s3 = u1s1+u2s2+u3s3
and
Lu ≤ u1s1+u2s2+u3s3 ≤ Mu.
For the second case, suppose u1 and s1 have the same sign, and u2 and s2 have opposite signs, the remaining possibilities being similar. Note that
(p, s2, s3) ∈ H
so
Lu ≤ u1p+u2s2+u3s3.
Also |p| < 1 so
u1p ≤ |u1p| < |u1| = u1s1
and therefore
Lu ≤ u1s1+u2s2+u3s3.
Also note that
(s1, p, s3) ∈ H
so
u1s1+u2p+u3s3 ≤ Mu.
Again |p|<1 so
-u2p ≤ |u2p| < |u2| = -u2s2
and
u2p ≥ u2s2
and therefore
u1s1+u2u2+u3s3 ≤ Mu.
This proves both parts of the first inequality, and as noted the other inequalities are similarly true, therefore
(s1, s2, s3) ∈ H.
This argument is rather fiddly and there were a couple previous versions where I discovered fatal flaws while writing them up; hopefully this version is correct. Note that I don't seem to use anywhere that u, v and w are orthogonal, so it looks like it remains true for parallelepipeds in general. The same argument works for n>3, the crucial fact needed being 2n<2n. So n=2 is actually the exceptional case. --RDBury (talk) 09:17, 9 September 2018 (UTC)[reply]
Actually there is a much more general theorem provided you apply some machinery of convex polytopes. Namely:
If P is a bounded convex polytope, Q a convex polytope which contains at least one point from every edge of P, and Q has fewer faces than P has vertices, then Q contains a vertex of P.
Proof: Suppose not. Every vertex of P is then excluded by some face of Q, in other words for each vertex v of Q there is a face of P, defined by L(x)=0 say, so that L(x)≤0 for x in Q and L(v)>0. There are more vertices of P than faces of Q, so two of the vertices must be excluded by the same face. In other words there is a linear function L so that L(x)≤0 for x in Q, and vertices v and w of P so that L(v)>0 and L(w)>0. If v and w are connected by and edge e, then L(y)>0 for all y in e, but Q contains a point of every edge of P and we have a contradiction. If L(v) is not the maximum value of L on P then apply the simplex algorithm to obtain an adjacent vertex u with L(u)>L(v)>0. This implies a contradiction as before, so L(v)=M, the maximum value of L on P. Similarly, L(w)=M. Then P∩{x: L(x)=M} is a polytope with at least two vertices, and therefore has an edge, which in fact is also an edge of P, again leading to a contradiction. There is a contradiction in every case so the initial assumption is incorrect and the theorem is true.
In the present case P is the hypercube with 2n vertices, and Q is a parallelepiped with 2n<2n faces. The simplest case is that if a triangle Q contains a point from every edge of a convex quadrilateral P, then Q must contain a vertex of P. This might be proven with just high school geometry but it would be a challenge. --RDBury (talk) 23:18, 9 September 2018 (UTC)[reply]

I like this theorem very much! Thank you! 2.53.159.234 (talk) —Preceding undated comment added 06:04, 11 September 2018 (UTC)[reply]

Notice however that a hyperrectangle (or even just a 2D-plane) that touches each face but doesn't contain any vertex does exist: After changing the interval from [0, 1] to [-1, 1] as RDBury sugggested above, in order to touch every face of the cube, you just need to take some hyperrectangele that contains the points . Actually, these points are linearly depndent, so you just need to to contain the points .
Hope this helps. עברית (talk) 17:42, 15 September 2018 (UTC)[reply]