×

# INLO36 - Editorial

Author: RAVIT SINGH MALIK
Editorialist: RAVIT SINGH MALIK

MEDIUM

COMBINATORICS

# PROBLEM:

Find the number of ways to distribute $N$ ladoos among the $M$ soldiers such that each soldier gets at least 2 ladoos.

# EXPLANATION:

First Find the number of ways in which $N$ identical objects can be divided into $R$ groups where each group can have any number of objects including $0$ ?
Consider the $N$ identical objects as $N$ '0's that you want to group. Now, you want to divide them into $R$ groups with empty groups included. You can do this by placing $(R - 1)$ dividers among the $N$ items(remember, 1 divider makes 2 groups and so $(R - 1)$ would make R groups). Assume the dividers are '1's. So now, you have $N$ '0's and $R-1$ '1'. All you have to do now is count the number of unique permutations of them. Each permutation of this set of 1's and 0's would represent unique grouping of the n identical items. The first group would contain all the 0's till the 1st '1' appears, the next group will have all the 0's until the next '1' appears and so on.

It is easy to see how that would be equal to $(N + R - 1)! / (N!)*(R - 1)!$. The numerator $(N + R - 1)!$ calculates the number of permutations of $N + R - 1$ objects as if they were not identical(unique). We divide by $(N!)$ and $(R - 1)!$ because we have $'N'$ identical '0's and $(R - 1)$ identical '1's.

This also happens to be equal to $(n+r-1)C(r-1)$.

NOW In question you have to find number of ways to distribute $N$ ladoos among the $M$ soldiers such that each soldier gets at least 2 ladoos.

so, firstly gave 2 ladoos to each $M$ soldiers
now we left with => $N = N - 2 \times M$ ladoos.
now the question has became to find Find the number of ways in which $N$ identical objects can be divided into $M$ groups where each group can have any number of objects including $0$ ?

so the answer is $(N+M-1)C(M-1)$.

FOR example :
Find the number of ways to distribute $11$ ladoos among the $5$ soldiers such that each soldier gets at least 2 ladoos.
so,
$N$ = $11-2 \times 5$ = $1$
$(N+M-1)C(M-1)$ = $(1+5-1)C(5-1) = 5$ . . which is the required answer.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

# RELATED PROBLEMS:

346
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,677
×2,592
×888
×22
×1

question asked: 10 Oct '16, 23:38

question was seen: 577 times

last updated: 02 Jan '17, 19:52