The Mathematicians' Picnic

This fairly innocuous looking problem has two major difficulties: the function we have to minimise is a sum of modulus functions; these aren't differentiable, so we can't use calculus, and they're not linear, so we can't use linear programming (except...see below). Also, the constraint is quite unusual.

Warning - long solution ahead! If there's a quicker way, please let me know.

The first thing to observe is that the sizes of the individual tables don't matter - only the gaps are important, so we can treat the tables themselves as having zero length.

Say we measure distances from the first table; let the initial position of the $i^\text{th}$ table be $P_i$ ; so $P_1=0$ , $P_2=12$ , $P_3=20$ , $P_4=25$ , $P_5=35$ , $P_6=41$ .

If table $i$ is moved $d_i$ feet to the right (a move to the left corresponding to a negative value), the function we need to minimise is $\sum_{i=1}^6 |d_i|$

If $Q_i=P_i+d_i$ denotes the final position of the $i^\text{th}$ table, then the constraint is that the $Q_i$ form an arithmetic progression; that is $Q_i=A+iD$ for some $A,D$ . Alternatively, we can write five constraints as $Q_{i+1}-Q_i=D$

---

Approach 1: linear programming

I mentioned above that the objective function is not linear. However, there is a very cunning trick we can use: instead of using the $d_i$ as variables, let table $i$ be moved $l_i$ feet to the left and $r_i$ feet to the right, with both these values non-negative. Then our objective function becomes $\sum_{i=1}^6 l_i+r_i$ The trick here is that by minimising this function, we force either $l_i$ or $r_i$ (or both) to be zero. There's no risk of linear programming returning, say, $l_i=5$ and $r_i=2$ because the overall effect is the same as $l_i=3$ , $r_i=0$ , but with a larger contribution to the objective function.

The constraints can be written as $l_i \ge 0$ , $r_i \ge 0$ , $D\ge 0$ and $P_{i+1}+r_{i+1}-l_{i+1}-\left(P_i+r_i-l_i\right)=D$

This is now completely linear, so we can use (say) the simplex algorithm to solve it; the result is a total distance moved of $8.25$ feet, giving the answer $\boxed{8250}$ .

---

Approach 2: parameter space

What does the set of all possible valid final arrangements look like? How can we parameterise it?

The final positions of the tables must be in arithmetic progression. Although we have $6$ tables, there are only $2$ degrees of freedom. For example, we could fully specify the final positions of the tables by giving the position of any one table, and the size of the gap between them. Or (as I'll do here), we can specify how much we move the two outermost tables; we know the remaining tables are spaced equally between them.

Let's say we move the first table a distance $x$ to the right, and the last table a distance $y$ to the right. If we decide we want to move them to the left, we just change the signs of these quantities as appropriate; if we want them to stay still, we set the distances to zero.

We can now visualise the parameter space as an $(x,y)$ coordinate system. For each point $(x,y)$ , we can work out the new positions of all the tables (knowing that they're equally spaced), and calculate how far each table has moved. The total of these distances moved is the function we want to minimise.

As an example, say we don't move the end tables at all; we just adjust the middle tables so that they're spaced evenly.

Total movement: $10$ (this is, incidentally, not bad, and almost certainly what I'd do in practice!)

We can define a function $f(x,y)$ to be the total movement of all the tables corresponding to the point $(x,y)$ of our parameter space. In this case, we have found that $f(0,0)=10$ .

What does this function look like? If we plotted it on the $z$ -axis above the $(x,y)$ parameter space, we would see a surface made up of sections of planes (sort of polyhedral, but the outer planes are not bounded). This is the equivalent of the familiar V-shaped plots of modulus functions in 2D.

With a bit of thought, we can see that (at least) one of the vertices of this polyhedral surface must be the lowest point (ie, the point that represents the optimal solution). It's possible that a whole edge, or a whole face of the surface is optimal, but by checking the vertices we guarantee finding the minimum value of the function.

The edges of the surface correspond to fixing a particular table (ie a zero contribution to the total movement from that table). The vertices - where the edges meet - correspond to fixing two tables.

So, with this intuition, we now know that the optimal solution will come from picking two tables to leave in place, and moving the others. With six tables in total, there are only $15$ pairs of tables to check; this is actually somewhat quicker than the simplex algorithm above.

Trying all possible pairs, we find the optimum occurs when we keep tables $2$ and $6$ in their original positions:

and again we have a total distance moved of $8.25$ feet.