4
$\begingroup$

Consider any $n$-simplex, $n \geq 2$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ in the simplex. The question: is $x_0$ in at least $n$ balls?

Some notes. The question cannot be strengthened by claiming, for example, that there is vertex $i=i(x_0)$ such that $x_0$ is in all balls $B_{ij},j \neq i$. Also, it is not true for $n+1$ balls (there are counterexamples for both cases if $n=3$).

Just in case, $x_0$ is in ball $B_{ij}$ if and only if $\angle x_ix_0x_j \geq \pi/2$, or equivalently, vertices $x_i$ and $x_j$ are on opposite sides of the hyperplane $H_i$ that contains $x_0$ and is orthogonal to the line through $x_i$ and $x_0$ (and similarly for $H_j$).

Also, this question is a stronger version of that question (thanks to zeb for solving it).

Any help is much appreciated. Thank you.

$\endgroup$
  • $\begingroup$ You might provide a link to your previous question which was nicely solved by zeb, and whose solution inspired this one. It would be a courtesy if you mention that this current question (and a similar one) also appeared there. I would like to hear more on why the statement can't be strengthened to finding i(x_0). $\endgroup$ – The Masked Avenger Aug 26 '13 at 17:51
  • $\begingroup$ Thanks, TMA, I updated the question. Just in case, in the discussion of the other question, there were suggestions on how to strengthen it (I really appreciate all of them), but none of them is identical. Regarding the non-existence of $i(x_0)$, you mean it is better to provide a counterexample here? $\endgroup$ – Max Aug 26 '13 at 18:15
  • $\begingroup$ I would like to see a counterexample for n=3, please. All my examples have almost all the simplex covered by balls sharing a vertex. $\endgroup$ – The Masked Avenger Aug 26 '13 at 18:28
  • $\begingroup$ The counterexample for $n=3$ is: vertices are $(1,0,0), (0,2,0.3), (0,0,1), (2,3,5), x_0 = (0.414, 0.649, 0.831)$. It is the Fermat point, so it is in the simplex. It is not in balls $B_{13}, B_{24}$ (the angles are smaller than $\pi / 2$), so for any $i$, there is a ball that does not contain $x_0$. $\endgroup$ – Max Aug 26 '13 at 18:38
  • $\begingroup$ Thanks for the example, I see now how to make one. This suggests an idea for n > 3. Pick a hamiltonian cycle on the simplex. Perhaps one can find a point in the simplex that guarantees half the balls associated with the cycle contain that point (or not). Use this along with a partial decomposition into cycles to resolve the question. $\endgroup$ – The Masked Avenger Aug 26 '13 at 19:27
4
$\begingroup$

Yes, because a connected graph ($i\sim j$ iff $\angle x_ix_0x_j$ is more than $\frac\pi 2$) with $n+1$ vertices has at least $n$ edges. The graph is connected because (assuming WLOG that $x_0=0$ is strictly inside the simplex) there exists a linear combination $\sum_j y_j=0$ where $y_j=c_jx_j$, $c_j>0$. If there are two not connected components, just compute the scalar product of the corresponding sums in two ways: one using the edge definition and one using the fact that the sums are just the opposites of each other.

I do like AoPS style questions, but, honestly, they belong there, not here!

$\endgroup$
  • $\begingroup$ Beautiful! Many-many thanks. Sorry for a trivial question, but where can I ask such type of questions? I am not a professional mathematician, and this question has appeared as a technical issue in my (applied) area. $\endgroup$ – Max Aug 27 '13 at 2:27
  • $\begingroup$ It is not trivial, just fairly standard (if you know the proof of Helly's theorem and such). Try MathStackExchange or Artofproblemsolving first next time. If you fail there, then come here :) $\endgroup$ – fedja Aug 27 '13 at 2:50
  • $\begingroup$ Thank you. By the "trivial question", I meant the one about where to post such questions, not the question itself :). I know the proof of Helly's theorem (via Radon's theorem). In fact, I thought about using Helly's theorem, but not the arguments in its proof. Anyway, thanks a lot again. $\endgroup$ – Max Aug 27 '13 at 3:12
  • $\begingroup$ Can you use this to determine where "the least coverage" is? In particular, can we say the points in the simplex are covered by an average of $o(n^2)$ spheres? Or is the average at most O(n)? $\endgroup$ – The Masked Avenger Aug 27 '13 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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