Just a question inspired by the olympics. Say we are to select a medley team from 4 swimmers and wish to minimise our total time for the race. For example say the pb's for each style and person are:
\begin{array}{|c|c|c|c|c|} \hline & \text { Free } & \text { Back } & \text { Butterfly } & \text { Breast } \\ \hline \text { A } & 20 & 20 & 20 & 10 \\ \hline \text { B } & 11 & 300 & 300 & 300 \\ \hline \text { C } & 10 & 200 & 200 & 200 \\ \hline \text { D } & 1 & 2 & 3 & 4\\ \hline \end{array}
Then the min time is $11+200+3+10=224$ seconds.
What is a bit surprising here is that we get the best total time utilising the third-best freestyler, the third-best backstroker, the best butterflyer and the second-best breaststroker. So only one choice of best swimmer is being made. Two questions:
Is there a distribution of the 16 times where NO best swimmer is used?
Is there an algorithm to find the min choice?
Of course everyone must swim exactly one style.
I suppose a more mathematical statement: Let A be a square $n\times n$ matrix with positive entries. We select n entries so that each of the n entries sits on a unique row and column. Let Z be the minimal possible sum of these n entries.
- Is it true that at least one of the chosen minimizing entries must also be the minimum for its column?
- How is Z found?
Many thanks to whoever fixed my table!
