1

A friend asked me this: Given n connected regions in space, and any pair of regions has no empty intersection, is it possible to draw a line through all of the regions?

stopwatchingmesleep
  • 73
  • @angryavian - to the extent that the triangle meets the precondition, we must consider a vertex to belong to both edges, in which case it is very possible to draw a line from a vertex to the opposing side thus touching all 3 edges. – antkam Dec 28 '19 at 03:54
  • @antkam Thanks for catching my mistake – angryavian Dec 28 '19 at 04:16

1 Answers1

1

HINT

Not only is a line through all regions possible, you can in fact choose any orientation you like and find a line of that orientation through all regions.

E.g. how about a line parallel to the $y$-axis? Such a line is defined by $x=c$ for some constant $c$. For region $A$, let $x(A)$ denote the set of $x$ values contained in the region, i.e.,

$$x(A) = \{x \in \mathbb{R} \mid \exists y: (x,y) \in A\}$$

So the line $x=c$ intersects $A$ iff $c \in x(A)$. This being a puzzle, I don't want to give the whole solution away, so...

  • Each region is connected. What does that say about $x(A)$?

  • Every pair of regions $A,B$ overlaps. What does that say about $x(A), x(B)$?

Can you finish from here?

antkam
  • 15,363
  • $x(A)$ and $x(B)$ has no empty intersection for all $A$ and $B$. Also, $x(A)$ and $x(B)$ are intervals of the form $(a_A,b_A),(a_B,b_B)$. So $a_i \leq b_i \forall i$. So max of all $a_i$ could be our $c$? – stopwatchingmesleep Dec 28 '19 at 13:13
  • Yes $c = \max a_i$ works. I love this puzzle. It sounds so complicated and general, and I found myself doodling overlapping blobs with weird shapes, but turns out to be almost a trick question with such a simple answer. (BTW technically the intervals are closed, i.e. $[a_A, b_A]$.) – antkam Dec 28 '19 at 15:41