Monday, June 26, 2006

The typists

This is the first problem from Perelman's books I chose to write about. One thing you have to be aware of is that the solution provided by him is extraordinarily simple. For example, I thought of resorting to calculus for the problem below. The suggested approach left me feeling like a complete idiot. So here you go: are you up to it?

Two typists have to type up a report. One of them is faster, and would need 2 hours to type it. The other one is slower, and would need 3 hours instead. But if they share the work, they would be able to finish it sooner. What is the minimum time they need to do the work together?


John Dougan said...

This looks like a job for simultaneous equations!

typist 1: 2 hours for 1 paper
rate_1 := 1/2 paper an hour
t_1 = time taken by typist 1.

typist 2: 3 hours for 1 paper
rate_2 := 1/3 paper an hour.
t_2 = time taken by typist 2

Effort to type 1 paper is therefore:
(1/2)t_1 + (1/3)t_2 = 1

Assuming the work is perfectly divisible, the time each takes should be the same therefore:

t_1 = t_2

Substitute and solve:
(1/2)t_1 + (1/3)t_1 = 1
(3/6)t_1 + (2/6)t_1 = 1
(5/6)t_1 = 1
t_1 = 6/5

Therefore working together it should take (6/5) hours or 1 hour and 12 minutes

Anonymous said...

I'm not so much a math person and by guesstimation I came up with 1 hour 15 minutes. It probably pure luck, but I thought I would share this to see how far off track I was.

I picked an arbitrary report size that was evenly divisible by 2 and 3 which turned out to be 12. The first typist would take 1 hour to do 6 pages, 20 minutes to do 2 pages, and 10 minutes to do 1 page. The second typist would take 1 hour to do 4 pages, 30 minutes to do 2 pages, and 15 minutes to do 1 page.

After an hour 10 pages would be complete leaving only 2 pages left. Evenly distrubuting the last two pages you would have to wait on the second types for 15 minutes.

John Dougan said...

Successive approximation...excellent! The key insight is that in the optimal case both are taking the same amount of time to do their share of the work as there is no slack time.

Andres said...

What a nice surprise to find comments in the blog! This is great!

Indeed, as John says, the key is to keep both typists busy at the same time. The solution provided by Perelman goes along the lines of...

... clearly, the faster typist is 1.5 times faster than the slower typist. Therefore, so that both typists are busy all the time, the faster typist's share should be 1.5 times larger than the slower one. Therefore, if x represents the work allocation for the slower typist,

3x/2 + x = 1
5x/2 = 1
x = 2/5

So the slower typist needs to do 2/5 of the work, and the faster typist needs to do the remaining 3/5. But then, the faster typist would need 2 hours * 3/5 = 6/5 hours to finish, or 1 hour 12 minutes.

Andres said...

PS: to think that I had thought of using calculus for this... how shameful!