Maximum average Euclidean distance between $n$ points in $[-1,1]^n$ For my research I have designed a metric that is based on the average Euclidean distance between $n$ points in the $n$-dimensional hypercube $[-1,1]^n$. However, I have a hard time finding the maximal average Euclidean distance between $n$ points in $[-1,1]^n$. 
I need this maximum to normalize my metric between $0$ and $1$ . Please help! 
 A: Here's the first few $n$ with the maximum average distance $m$ over all corner configurations, and a configuration which realizes it.  I've changed the interval from $[-1,1]$ to $[0,1]$ to make it easier to read.
\begin{align}
n=2, & \ m=\sqrt{2}\simeq 1.414 & (0,0)\\
     &          & (1,1)\\
n=3, & \ m=\sqrt{2}\simeq 1.414 & (0,0,1)\\
     &          & (0,1,0)\\
     &          & (1,0,0)\\
n=4, & \ m=\frac{\sqrt{2}+2\sqrt{3}}{3}\simeq 1.626 & (0,0,0,0)\\
& & (0,0,1,1)\\
& & (1,1,0,1)\\
& & (1,1,1,0)\\
n=5, & \ m=\frac{\sqrt{2}+3\sqrt{3}+\sqrt{4}}{5}\simeq 1.722 & (0,0,0,0,0) \\
& & (0,0,0,1,1)\\
& & (0,1,1,0,0)\\
& & (1,0,1,0,1)\\
& & (1,1,0,1,0)\\
\end{align}
This suggests that choosing all coordinates independently and randomly may get an average close to the maximum, and for large $n$ that average is roughly
$$\left(1-\frac{1}{8n}\right)\sqrt{\frac{n}{2}}.$$
A: Not what you are asking for, but I wanted to point out that the problem is very easy if you work with squared distances. Formulate the problem as the following optimization problem:
\begin{align}
\max \quad & \sum_{i\neq j} \| x_i- x_j\|_2^2 \\
s.t. \quad & x_i(k) \in \{-1,1\},
\end{align}
where $x_i\in \mathbb{R}^n$. If the solution is at the corners, the set of maximizers is non convex (consider permutations). 
Observe that $ \| x_i- x_j\|_2^2=\sum_{k=1}^n (x_i(k)-x_j(k))^2= \sum_{k=1}^n x_i(k)^2+x_j(k)^2 -2 x_i(k) x_j(k)$. For the corner points, we have $x_i(k)^2=1$, thus the problem becomes
\begin{align}
z=\min \quad & \sum_k\sum_{i\neq j} x_i(k) x_j(k) \\
s.t. \quad & x_i(k) \in \{-1,1\},
\end{align}
where the optimal objective of the former problem is $n^2(n-1)-2z$.
The latter problem decouples over $k$. For each $k$, we solve
\begin{align}
\min \quad & \sum_{i\neq j} x_i(k) x_j(k) \\
s.t. \quad & x_i(k) \in \{-1,1\},
\end{align}
This basically is a max-cut problem for an n-node complete graph. Suppose n is even, the optimal solution is achieved by setting half of $x_i(k)$ to $+1$ other half to $-1$. Corresponding objective value is $2\frac{(n/2) ((n/2)-1)}{2}-(n/2)^2=-n/2$.
Thus, $z=-n^2/2$. And the optimal objective of the original problem is $n^3$. Average of these squared distances is $n^2$.
