hi this is PR toer today's puzzle is
something you might see on a technical
interview question imagine you have
three people and 11 identical coins how
many ways are there to split 11 coins to
three
people only the total number of coins to
each person matters so you might give
five coins to Blue six coins to red and
no coins to
Green part two of the question how many
ways are there if each person has to get
at least one coin
now 560 would not be a solution because
we have to give green at least one coin
so we might give green one red five and
blue
five give these problems a try and when
you're ready keep watching a video for
the
solutions we'll start out by solving the
number of ways you can split 11 coins to
three
people we'll use a trick which is to
place two dividers between the coins
we'll color one divider blue and another
divider red the number of coins to the
left of the blue divider will be the
number of coins that blue gets the
number of coins between the dividers
will be the number of coins that red
gets and the number of coins to the
right of the red divider will be the
number of coin that greens gets so if I
place the dividers in the following
positions there are three coins to the
left of the blue divider that go to Blue
there are six coins in between the
divider that's how many red gets and
they're two coins to the right of the
red divider which go to
green we can change the positions of
these dividers if I move the blue
divider over now blue is getting five
coins red is getting four coins and
green is getting two
coins I can change the positions again
if I move the blue divider all the way
over to the left now there are no coins
to the left of the blue divider so blue
is getting zero coins in between the
dividers is seven coins that go to Red
and to the right of the red divider is
four coins that go to
green imagine I shift the dividers over
like this now blue is getting six coins
the two dividers are next to each other
there are no coins so that means red
gets no coins and green gets the
remaining five coins I'll let you figure
out how to have a division where green
gets zero coins but basically we can
count the number of ways to split 11
coins to three identical people by
figuring out the number of ways we can
place these two
dividers so imagine we have 11 + 2 which
which is 13 total slots we're going to
place the dividers in two of these slots
and the coins in the remaining slots so
we want to pick two of the spots for the
dividers and then we place the remaining
slots we fill them with the
coins so we can count the number of ways
to split 11 coins to three people by
counting the number of ways that we can
pick the two dividers in 13
slots that's the number of ways you can
choose two elements from 13 which is the
binomial coefficient 13 choose two which
ends up being 78 so that's part one
answer is that you can have 78 ways to
split 11 coins to three
people let's generalize this let's
assume we have n identical items that we
want to divide to R
people as we did before we basically
want to use rus1
dividers we're going to need to draw out
n plus rus1 Slots of which we're going
to pick rus1 dividers so it's the number
of ways that we can choose R-1 elements
from n +
R-1 which will be n + r -1 choose R -1
which is equivalently n + r -1 choose
n there's another way you can think
about this solution imagine the
algebraic equation X1 + X2 all the way
up to XR R variables being equal to n
and we want to find the number of non-
negative integer Solutions
this is exactly partitioning n into our
different
spaces so this also gives you the amount
of distinct in non- negative integer
solutions to this equation you can
interpret each term XI as the amount
that person I
gets so now let's proceed to the next
question which is to do the same split
except each person has to get at least
one
coin now we don't actually have to start
over what we're going to do is a trick
where we start out by giving one coin to
each person so now we know each person
has at least one coins now we want to
divide up the remaining eight coins to
the three people and we can do that by
dividing the eight coins using our two
divider
method so we want to divide in the same
exact way but we're just going to add
I'll just do one example to show you how
this works imagine I put the dividers
here there's one coin to the left of the
blue divider but blue already has one
coin coin so blue ends up with two coins
now in between the divider there are six
coins but then we're going to add the
one that red already has to the right of
the red divider is one coin we add on
the one that green already has to get
two so we can find all ways to split 11
coins to three people where each person
gets at least one by giving each person
one coin and then using our two divider
method on the eight coins remaining so
let's go through this
solution we start out by giving one coin
each so that means they're 11 minus 3
which is eight coins we then have to
solve the problem of dividing those
eight coins into three people so we're
going to have 8 + 2 which is 10 Slots of
which we're going to pick the two spots
for the divisor the
dividers as we just solved this will be
the number of ways to choose two
elements from 10 which is 10 choose two
which becomes
45 we can generalize this let's imagine
we want to split n identical coins to R
people so that each person gets at least
one
coin we start out by giving one coin to
each of the r people so they n minus R
Coins remaining then we want to divide
the N minus R Coins to R
people we've already solved this before
you use rus1 divisors for a total of n
minus1
spots so this becomes the number of ways
to choose rus1 elements from n minus1
which is nus 1 choose
rus1 algebraically if you have the
solution X1 + X2 all the way up to XR
equaling xn equaling n we now can solve
for the number of positive integer
Solutions using n minus1 choose R minus
one and in this case we again interpret
XI as the amount that person I
gets thanks for watching this video
please subscribe to my channel I make
videos on math and Game Theory you can
catch me on my blog mind your decisions
which you can follow on Facebook Google+
and patreon you can catch me on social
media at prowalker and if you like this
video please check out my books there
are links in the video description