9

Suppose a mysterious adversary has captured me and challenged me to the following topological game. We fix some finite set, say, $X = \{1, 2, 3, \ldots, n\}$, and my adversary secretly constructs a topology $T$ on $X$. My job is to determine $T$ by asking my opponent, as many times as I wish, for the boundary $\partial S$ in $T$ of any subset $S \subset X$, but for every answer I receive, a portion of my anatomy is forcibly removed. I cannot answer until I am absolutely sure of $T$ (no guessing!), and I will be freed as soon as I answer correctly.

Question: What strategy should I use to maximize the number of body parts I expect to walk away with?

The case $n=1$ is trivial, as there is only one topology on a singleton. In the case $n=2$, my strategy is particularly simple: I ask for the boundary of $\{1\}$. There are four possible boundaries, each uniquely determining $T$:

  • If $\partial \{1\} = \emptyset$, then $T$ is the discrete topology on $X$.
  • If $\partial \{1\} = X$, then $T$ is the indiscrete topology on $X$.
  • If $\partial \{1\} = \{1\}$, then $T = \{\emptyset, \{2\}, X\}$.
  • If $\partial \{1\} = \{2\}$, then $T = \{\emptyset, \{1\}, X\}$.

In any case, I lose just one body part. I have determined via computer search that for $n=3$, it suffices to check $$ \{1\}, \{1,3\}, \{3\} $$ and for $n=4$, $$ \{1\}, \{1,2,4\}, \{1,3,4\}, \{4\} $$ though I am not sure if these are optimal, and I do not know if the pattern generalizes.

David Zhang
  • 8,835
  • Why is it necessary to cast this problem in such a such a horrific form? – John Bentin Dec 16 '14 at 13:15
  • 2
    @JohnBentin The problem reminds me distinctly of the word-guessing game "hangman," which is set in a similarly gory fashion. I can edit out the references if the style is inappropriate. – David Zhang Dec 16 '14 at 13:29
  • No, no, the form is OK. According to Stephen Barr, “Procrustes did a lot of cutting. Also stretching, for which reason he described himself as the first topologist”. I am also highly inspired to scientific work. This is a good old Eastern style of stimulation. For instance, Arthur Osborn told: “For the first five years of his life Ganapati was dumb and ... seemed anything but a promising child. Then he was cured, it seems, by branding with a red-hot iron, and immediately began to display his marvellous ability”. – Alex Ravsky Dec 16 '14 at 17:30

1 Answers1

7

I have two news for you.

The first news is good. You will lose at most $n$ body parts. Indeed, to describe a topology on the set $X$ it suffices to describe $\overline{S}$ for every subset $S$ of $X$. But, since the set $S$ is finite, $\overline{S}=\cup_{x\in S}\overline{\{x\}}$, and $\overline{\{x\}}=\{x\}\cup \partial\{x\}$ for each $x\in X$.

The second news is bad. Suppose that you need at least 3 questions to determine a topology on a 3-element set and at least 4 questions to determine a topology on a 4-element set. If $n\ge 6$ then the adversary can partition $n$-element set $X$ into a disjoint union of 3- or 4- element sets $X_i$, define a topology $T_i$ on each $X_i$ independently, and define on the set $X$ a topology $T$ of a topological sum $\bigoplus (X_i, T_i)$.

Alex Ravsky
  • 90,434