Let
\[
Q_n=\{0,1\}^n
\]
be the \(n\)-dimensional discrete cube, viewed as a graph in which two vertices are adjacent if they differ in exactly one coordinate.

For a subset \(A\subseteq Q_n\), let \(\partial_e A\) denote the set of edges with one endpoint in \(A\) and the other in \(Q_n\setminus A\).

Prove that for every \(A\subseteq Q_n\),
\[
|\partial_e A|\ge |A|\bigl(n-\log_2|A|\bigr).
\]

Let \(n\) be an odd positive integer, and let
\[
f:\{-1,1\}^n\to\{-1,1\}.
\]
Interpret \(x_i=1\) as voter \(i\) voting for candidate \(A\), and \(x_i=-1\) as voter \(i\) voting for candidate \(B\). The value \(f(x_1,\dots,x_n)\) is the choice.

Find all functions \(f\) satisfying the following properties:
1. Anonymity: for every permutation \(\sigma\in S_n\),
\[
f(x_1,\dots,x_n)=f(x_{\sigma(1)},\dots,x_{\sigma(n)}).
\]
2. Neutrality:
\[
f(-x_1,\dots,-x_n)=-f(x_1,\dots,x_n).
\]
3. Monotonicity: if \(x=(x_1,\dots,x_n)\) and \(y=(y_1,\dots,y_n)\) satisfy
\[
x_i\le y_i \qquad \text{for all } i=1,\dots,n,
\]
then
\[
f(x)\le f(y).
\]

Show that any set of d + 2 points in R^d can be partitioned into two sets whose convex hulls intersect.

Let \(P\) be a regular \(2n\)-gon. A perfect matching is a partition of vertex points into \(n\) unordered pairs; each pair represents a chord drawn inside \(P\). Two chords are said to “intersect” if they have a nonempty intersection.

Let \(X\) be the (random) number of intersection points (formed by intersecting chords) in a perfect matching chosen uniformly at random from the set of all possible matchings. Note that more than two chords can intersect at the same point, and in this case this intersection point is just counted once. Compute \(\lim_{n\rightarrow \infty} \frac{\mathbb E[X]}{n^2}\).