Question

50 identical tasks need to be assigned to 10 different processors. The processors are numbered 1 through 10.

1.

How many ways are there to distribute the tasks if processor number 1 must receive exactly 5 tasks?

2.

How many ways are there to distribute the tasks if each processor must be assigned at least one task?

Answer 1

We have this situation in mathematical terms:

x1 + x2 + x3 + ........ + x10 = 50 , such that x1,x2,......x10 0

The main concept to be used here is that if we want to distribute n identical things to r different places then number of ways of distributing without any restrictions is (n+r-1)C(r-1). This method is known as the partition method or beggars method.

1. How many ways are there to distribute the tasks if processor number 1 must receive exactly 5 tasks?

x1 + x2 + x3 + ........ + x10 = 50

First, let's give five tasks to processor 1. => x1 = 5

Now we don't want x1 to have more tasks, hence we can omit x1 from the equation and remaining tasks are now 45.

So situation is

x2 + x3 + ........ + x10 = 45 without any restrictions.

So number of ways = (45+9-1)C(9-1) = 53C8

2. How many ways are there to distribute the tasks if each processor must be assigned at least one task?

x1 + x2 + x3 + ........ + x10 = 50

Let's give one task to each processor => x1 = x2 = x3 = .... = x10 = 1

Now we have remaining tasks = 40.

So the situation is now

x1 + x2 + x3 + ........ + x10 = 40 without any restriction

So number of ways = (40+10-1)C(10-1) = 49C9