To see that this is possible, consider a tetrahedron ABCD inside a tetrahedron A'B'C'D', where all these points are very close to being on a straight line and, furthermore, where A,B,A',B' and C' are all very close together and so are C,D and D' (though they are far from the first set). If the distance between the two sets of points is approximately a, then the sum of the sides of ABCD is approximately 4a, while the sum of the sides of A'B'C'D' is approximately 3a.
To prove that this is also the upper bound, consider the sum of the lengths of the sides of these tetrahedra, when projected onto an arbitrary line. In the single-dimensional tetrahedron case, it is easy to show that the inside tetrahedron never has more than 4/3 the side-sum of the outside tetrahedron. Because it is true in every case, it is also true for the expected case, when choosing a line in a random, uniformly chosen direction (over the uniform measure on the sphere). This expectation, however, is proportional to the side-sum of the three-dimensional tetrahedron (a fact that can be ascertained easily by seeing that for a single straight line, this statistic is invariant to rotations or translations, from which it follows also for the sum of several straight lines).
Q.E.D.
The extension to higher dimensions is trivial. Readers may also contemplate what would happen if the n-dimensional post-office were to charge by the sum of the k-dimensional surfaces of the simplex.
As promised, some references:
This riddle has previously appeared in
this
French-language riddle site.
Its solutions direct to a paper in Mathematics magazine, Vol 73, No. 3,
June 2000. This, in turn, refers to "Macalester Problem of the week", No. 834,
as well as to "Crux Mathematicorum", December 1996. Further attributions can
be found there
(Problem 2099).
I further thank Claudio Baiocchi for undertaking this extensive literature review, to make sure all credit goes to where it is due.