Who can fly?

Logic Level 3

You are a swim coach, and you would like to put together the fastest relay you can for the 200 Medley Relay (Where you race four swimmers, each racing 50 yards in a different stroke).

Here are their times:

Swimmer	50 Fly	50 Back	50 Breast	50 Free
Ryan	0:34	0:36	0:37	0:27
Maya	0:39	0:50	0:38	0:32
Hana	0:40	0:42	0:49	0:36
Jaycie	0:41	0:45	0:44	0:35

Who should swim Fly?

Image credit: https://clipartfest.com

Jaycie Maya Hana Ryan

3 solutions

Wesley Zumino
Aug 19, 2017

This type of problem is known as an assignment problem , a well-studied problem in the field of combinatorial optimization. There are many efficient (polynomial-time) algorithms for solving it. A paper-and-pencil approach is the Hungarian Algorithm - for example, see here and here . This was the solution approach used here.

A summary of the Hungarian algorithm is as follows:

Step 0. Form the $m \times m$ cost matrix. For each row, subtract the minimum element in the row from all elements in the row. For each column, subtract the minimum element in the column from all elements in the column.

Step 1. Draw the minimum number of horizontal and vertical lines to cover all zeros in the matrix. If the number of lines $= m$ , an optimal (least cost) assignment is available. Otherwise, continue.

Step2. Find the minimum uncovered element. Subtract this element from each uncovered element. Add this element to each twice-covered element. (Equivalently, subtract the minimum from all uncovered rows and then add it to all covered columns.) Go to Step 1.

This is illustrated in the figures below for the current problem (for exposition purposes, in more detail than is usually needed).

Ah, this is an interesting approach, Wesley... Thanks for posting! :)

Geoff Pilling - 3 years, 9 months ago

Geoff, something I felt was missing from the solution I posted applying the Hungarian Alg was why it was a solution. So I constructed a Note to try to address that informally, if you are interested.

Wesley Zumino - 3 years, 9 months ago

Thanks, Wesley... I'll take a look!

Geoff Pilling - 3 years, 9 months ago

Geoff Pilling
May 15, 2017

Although Jaycie has the slowest fly time, she should still swim fly.

Here are all the combinations (in the order Fly, Back, Breast, Free), and the respective times:

RMHJ 168
RMJH 164
RHMJ 149
RHJM 152
RJMH 153
RJHM 160
MRHJ 159
MRJH 155
MHRJ 153
MHJR 152
MJRH 157
MJHR 160
HRMJ 149
HRJM 152
HMRJ 162
HMJR 161
HJRM 154
HJMR 150
JRMH 151
JRHM 158
JMRH 164
JMHR 167
JHRM 152
JHMR 148

Clearly the fastest one is the last one, so the swimmers should be assigned:

$\boxed{Jaycie}$ - Fly
Hana - Back
Maya - Breast
Ryan - Free

If anyone has a better algorithm than this brute force approach I'd love to hear it! :0)

Fun problem. I rewrote the grid with Ryan's times as the baseline:

$0.00 \quad 0.00 \quad 0.00 \quad 0.00$

$0.05 \quad 0.14 \quad 0.01 \quad 0.05$

$0.06 \quad 0.06 \quad 0.12 \quad 0.09$

$0.07 \quad 0.09 \quad 0.07 \quad 0.08$

The diagonal from bottom left to top right then sticks out as the best option.

Brian Charlesworth - 4 years ago

Ah, nice approach... I wonder if there is a quick algorithm for this.

Or, lets suppose you had the times for 10 swimmers instead of 4, and you had to pick the fastest total relay time. (i.e. pick four swimmers, and the events for each)

Geoff Pilling - 4 years ago

That's a realistic problem for any swim team coach at any level. My solution method wouldn't work as well if Ryan's times weren't the best in all of the strokes, but one could still see things more clearly in a grid where the best time in each stroke acts as the baseline $0.00$ than in the original grid. Where there is a wide spread in times you would want to rule out all but the best 2 or 3 times, but where the spread is small you could keep more swimmers in mind. In any event, your follow-up question would be more of a Computer Science than Logic question, I suspect.

Brian Charlesworth - 4 years ago

@Brian Charlesworth – Yeah, I suspect you are right... This might be about as far as we can go with eyeballing it.

Even as a computer science problem, I wonder if there may be a way to quickly zero in on the solution, instead of just looking at every combination.

i.e. Suppose there are 1,000,000 swimmers. Can we very quickly eliminate all but say 16 (or fewer?), and then brute force the final 16 or so? Something along the lines of "Well, Ryan has the fastest free time, so if he is not doing any other stroke, he will for sure do free. So, Ryan is definitely in the relay..."

Geoff Pilling - 4 years ago

@Geoff Pilling – Well, there are only 4 strokes, even with 1,000,000 swimmers. So, we can look at a single stroke, and pick the top 4 swimmers for each stroke. If these are all separate swimmers, we're done. If they are not, then for each instance where a swimmer has 2 events that they are best at, add a swimmer to that event. Continue this process. Now, consider someone who is the 5th best at an event (but not so good at the others). He will not be in that event, because at least 1 of the other 4 swimmers will not be competing. Therefore, we have at most 16 swimmers to consider. I haven't put much thought into simplifying this, but for this problem, as you can see, searching through the 1,000,000 swimmers will take much longer than checking all 4! = 24 combinations.

Alex Li - 4 years ago

@Alex Li – Yup... I agree! I think reducing it to 16 (The four best in each stroke) and then looking at the possible combinations, is likely the way to go!

Geoff Pilling - 4 years ago

@Geoff Pilling – That seems like the practical approach. With, say 25 swimmers, take the top 6 times in each stroke. If someone is in only one of these lists but has the top time (or a close second to someone who shows up in multiple lists) then plug that person into that leg. With those who are in several lists there is then some flexibility to slot them in to different legs depending on the differentials with the other good swimmers for a given leg. This doesn't guarantee the best time on paper but it would no doubt be close.

With 1,000,000 swimmers, it might be an idea to use two filters: (i) take the averages over all strokes for each swimmer and take the best 20 or so "overall" swimmers, and (ii) take the best 5 or so times in each leg in case there are any swimmers who are crazy good at one stroke but lousy at the others, (and hence might be missed by filter (i)). Say this second filter introduces an extra 5 swimmers. Then use the process outlined in the first paragraph to narrow down the 25 swimmers to form the team, (along with alternates in case of injury).

Brian Charlesworth - 4 years ago

@Geoff Pilling This is an assignment problem. There are many polynomial-time algorithms for solving it. A paper-and-pencil approach is the Hungarian Algorithm - see here and here . That is what I used to solve it - just took 5 steps in a spreadsheet (which are good for the quick copy&paste and error-free calcs on the matrices). Perhaps I'll post it when I get some time.

Wesley Zumino - 3 years, 10 months ago

That would be cool, Wesley... I'd like to take a look at the solution! :)

Geoff Pilling - 3 years, 10 months ago

Ok Geoff, I'll write it up and post it. Please be patient... Wes

Wesley Zumino - 3 years, 10 months ago

Ok Geoff, solution is posted. Thanks for your patience. It's a busy time. Wes

Wesley Zumino - 3 years, 9 months ago

Saya Suka
May 3, 2019

Let's have.
Stroke : rankings and TD.....TD3rd-1st/4th-2nd/4th-1st, with TD as time difference.

Fly. : r.5.m.1.h.1.j.....6/2/7.
Back : r.6.h.3.j.5.m.....9/8/14.
Breast : r.1.m.6.j.5.h.....7/11/12.
Free. : r.5.m.3.j.1.h.....8/4/9.

R is the best swimmer in all 4 strokes, but we'll choose wisely for him later. M is overall second, but we see that M is worst in back in the worst way possible, with 14s in TD compared to R (the biggest gap), so M will be doing something else than that. Since M's and R's performance is very, very close in breast with one sec TD, M --> Breast. H's best stroke is Back, so that'd be for her since she's practically useless in all the others. Now we only need to compare for free and fly, for R and J. Since we have r.7.j for fly and r.8.j for free, then R doing Free and J doing Fly is the best bet, saving one precious second.

Who can fly?

3 solutions

0 pending reports