Let $n$ be a positive integer and let $f_{1}(x), \ldots, f_{n}(x)$ be affine functions from $\mathbb{R}$ to $\mathbb{R}$ such that, amongst the $n$ graphs of these functions, no two are parallel and no three are concurrent. Let $S$ be the set of all convex functions $g(x)$ from $\mathbb{R}$ to $\mathbb{R}$ such that for each $x \in \mathbb{R}$, there exists $i$ such that $g(x)=f_{i}(x)$.

Determine the largest and smallest possible values of $|S|$ in terms of $n$.
(A function $f(x)$ is affine if it is of the form $f(x)=a x+b$ for some $a, b \in \mathbb{R}$. A function $g(x)$ is convex if $g(\lambda x+(1-\lambda) y) \leq \lambda g(x)+(1-\lambda) g(y)$ for all $x, y \in \mathbb{R}$ and $0 \leq \lambda \leq 1$.)
We will prove that largest possible value of $|S|$ is $2^{n}-1$ and the smallest possible value is $\frac{n(n+1)}{2}$.

Suppose $g \in S$. For $i=1,2, \ldots, n$, let $X_{i}=\left\{x \in \mathbb{R}: g(x)=f_{i}(x)\right\}$. We will first note the following.

Claim: If $\left|X_{i}\right| \geq 3$, then $X_{i}$ is an interval.
This claim follows since if $af_{i}(y)$ for all $i \in T$. Since convex functions are continuous, there exists an open neighbourhood $U$ of $y$ such that for all $z \in U, g(z)>f_{i}(z)$ for all $z \in U$. For each $z \in U$, there must exist $j$ with $f_{j}(z)=g(z)$. Since the set of possible $j$ is finite and $U$ is infinite, there exists $j$ such that $f_{j}(z)=g(z)$ for at least three $z \in U$. But therefore $j \in T$ which implies $g(z)>f_{j}(z)$, a contradiction. This completes the proof of (1).

Since $T$ is nonempty, there are at most $2^{n}-1$ possible subsets $T$ of $\{1,2, \ldots, n\}$. This upper bound can be achieved, for example we can take the graphs of $f_{1}, \ldots, f_{n}$ to be $n$ distinct tangents of the graph $y=x^{2}$. In this case every subset $T$ gives a distinct function because for every $i$, there exists some $x$ such that $f_{i}(x)=\max _{j} f_{j}(x)$.

For the lower bound, since no two lines are parallel, all functions $f_{i}$ with $1 \leq i \leq n$ and $\max \left(f_{i}, f_{j}\right)$ with $1 \leq i<j \leq n$ are pairwise distinct elements of $S$. So there are at least $n+\frac{n(n-1)}{2}=\frac{n(n+1)}{2}$ such functions. To achieve this lower bound, we can take $n$ distinct tangents of the graph $y=-x^{2}$. If we order the functions in increasing gradients, then it is easy to show that $f_{j}<\max \left(f_{i}, f_{k}\right)$ for $i<j<k$, so there are no other elements of $S$.