UNO High School Problem of the Week Competition
Problem 6
A company has 4 employees that can perform a certain task. We know that one of the employees can do this task in 3 hours,
another in 4 hours, a third in 5 hours, and finally the last one in 6 hours.
Given that each employee must perform 2 jobs while working in a group of 2 people and that no
group can be repeated, how should the company assign the groups so that it takes the shortest amount of time to complete all of the jobs. The longest?
Solution
If a person who can complete a given task in t1 hours works with a person who can complete the same task in t2 hours, then the total time
when working together is t3 hours.
Since the 1st person can complete the entire task in t1 hours, then in one hour they can complete 1/(t1) of the task. The same can be said of the 2nd person
and the total time.
Next add the individual hourly rates. This has to be equal to the combined hourly rate, or 1/(t3). Thus we obtain the following:
1/(t1) + 1/(t2) = 1/(t3)
Now if we perform some minor algebra, we get that eq(1), which we will use later:
1/(t1) + 1/(t2) = 1/(t3) ==> (t2)/(t1*t2) + (t1)/(t1*t2) = 1/(t3) ==> (t1 + t2)/(t1*t2) = 1/(t3) ==> t3 = (t1*t2)/(t1+t2) (1)
Of the four employees, there are only 6 combinations of two working together. (AB, AC, AD, BC, BD, CD)
Where employee A is the one who can complete the task in 3 hours, B in 4, C in 5, and finally D in 6.
By applying eq(1) to get of the above groups, we get the following:
A and B = 12/7 hours (1 hour, 43 mins)
A and C = 15/8 hours (1 hour, 53 mins)
A and D = 2 hours (2 hours, 0 mins)
B and C = 20/9 hours (2 hours, 13 mins)
B and D = 24/10 hours (2 hours, 24 mins)
C and D = 30/11 hours (2 hours, 44 mins)
Based upon the above groupings, there are only 3 possible ways to split the 4 employees into 2 groups with each employee only being in one group.
AB and CD (Group 1)
AC and BD (Group 2)
AD and BC (Group 3)
Of these 3 groupings, we are only worried about the group taking the longer time. Because if one group finishes early, they would have to wait for
the other group to finish before redistributing.
So longer time of AB and CD is that of CD, (2 hours, 44 mins). Longer time of AC and BD is that of BD, (2 hours, 24 mins). Finally longer time of
AD and BC is that of BC, (2 hours, 13 mins).
Of these, the group of BC is the fastest, BD is in the middle, and CD is the longest.
The groups labeled above only count for one of the jobs that each employee needs to do, so in order to get both jobs done, the company needs assign groups
1 & 2
1 & 3
2 & 3
If Group 1 does their jobs, redistribute to Group 2, then the total time is that of CD and BD, or (5 hours, 8 mins).
If Group 1 does their jobs, redistribute to Group 3, then the total time is that of CD and BC, or (4 hours, 57 mins).
If Group 2 does their jobs, redistribute to Group 3, then the total time is that of BD and BC, or (4 hours, 37 mins).
So the fastest pairing is to do Groups 2 & 3. AC and BD, AD and BC.
So the slowest pairing is to do Groups 1 & 2. AB and CD, AC and BD.