11 cyclists in a race

Question

A team of $11$ cyclists begin a race. If each cyclist rides individually then their respective race times will be $10, 11, \ldots, 20$ minutes. However, if three cyclists with individual times $(a, b, c)$ ride as a triplet, they will finish the race in $(a+b+c)/3$ minutes - due to a clever energy preserving rotational strategy. What is the least amount of time needed for every cyclist to finish the race?

Answer 1

Via mixed integer linear programming with a binary decision variable for each of the $\binom{11}{1}+\binom{11}{3}=176$ possible teams, I have found that the minimum is

15 minutes and 20 seconds,

attainable via teams with times

 {10,16,19}, average 15
 {11,17,18}, average 15 + 1/3
 {12,14,20}, average 15 + 1/3
 {13}, average 13
 {15}, average 15

Here's an alternative optimal solution, with only one "slow" team:

 {10,17,18}, average 15
 {11,16,19}, average 15 + 1/3
 {12,13,20}, average 15
 {14}, average 14
 {15}, average 15

---

Here's the formulation I used. For each team $T$ (subset of cardinality $1$ or $3$), let $a_T$ be the average time and let binary decision variable $x_T$ indicate whether that team is used. Let decision variable $z$ represent $\max_T a_T x_T$. The problem is to minimize $z$ subject to linear constraints \begin{align} \sum_{T: c \in T} x_T &= 1 &&\text{for all cyclists $c$} \tag1\label1\\ a_T x_T &\le z &&\text{for all teams $T$} \tag2\label2 \end{align} Constraint \eqref{1} assigns each cyclist to exactly one team. Constraint \eqref{2} enforces the minimax objective.

Answer 2

Computer brute forcing seems somewhat excessive for puzzles like this ("axe to the head" is how my native language might describe it), so here's a (post-accept) no-computers solution to balance things out.

By the puzzle's definition, the completion time for a triplet is the average of the three individual times. This means there's a quantity that will always be preserved, regardless of grouping:

The average individual completion time of the entire bunch never changes.

That quantity is easily calculated to be 15 minutes, and it is of course a hard limit for the overall completion time, too.

Now, if a grouping exists so that the 15 min overall time is achievable, then every single group (of 1 or 3 persons) will have to complete the race at exactly 15 minutes: If any group were faster, then there would have to be another group running slower than 15 minutes in order to restore the global average of individual times.

However, there are 11 cyclists, so all the groups cannot run at exactly 15 minutes: there are at least two individual riders, and only one of them can be the guy that completes the race in exactly 15 minutes. The other individual guy must be either slower (dragging the total down by at least a minute) or faster (causing another group to be slower by at least 1/3 of a minute.)

To see if the minimal slowdown is achievable, it's easiest to put the 14 and 15 minute guys as the two individual riders, and then form groups totalling 45, 45, and 46 minutes from the rest of the guys. Turns out this is easy to do, for example like this:

 14 (14 minutes)
 15 (15 minutes)
 12, 13, and 20 (-> 45/3 = 15 minutes)
 11, 16, and 18 (-> 45/3 = 15 minutes)

..and we don't even have to check the final group of the three other guys to know they must finish in exactly

15 min 20s,

or else the overall average of individual completion times would have changed, which is impossible.

Answer 3

Assuming that

combinations must be exactly three cyclists, and must stay together for the entire race

then the best we can do is

17 minutes, because once we've sped up the ones who take 20 and 19 and 18 minutes, we can't form any more triplets.

Let's demonstrate that this is achievable:

(10, 11, 20) ride together and all finish in 41/3 = 13.6+ minutes.

(12, 13, 19) ride together and all finish in 44/3 = 14.6+ minutes.

(14, 15, 18) ride together and all finish in 47/3 = 15.6+ minutes.

16 and 17 ride individually.

Answer 4

The group will be fastest when they ride

in one group of 11. With most of the time or all the time the 3 fastest in front.

The worst time will be at most

13 minutes 40 seconds

Proof

We know that

there is a clever energy preserving rotational strategy that works for 3 cyclists with time a<b<c such that the slowest time c is reduced to (a+b+c)/3

and common knowledge dictates that

larger groups should be able to preserve the same or even more energy as a result of energy preserving rotational strategies.

Therefore

It must work at least as good for 11 cyclists.

We might go for the time by the top three cyclists

They could finish alone in 11 minutes.

But, we can not know

at which pace the slowest cyclists will be able to follow the pack.

Yet, we do know that they can finish in

at least in 13 minutes and 40 seconds, because the slowest cyclist is able to follow at that speed in a group of three, so certainly as well in a bigger group.