How To Solve A TOUGH Interview Question – Ways To Give 11 Coins To 3 People


100 thoughts on “How To Solve A TOUGH Interview Question – Ways To Give 11 Coins To 3 People

  1. problem 1 solution: 3^11 = 177147 ways

    problem 2 solution: so everyone gets at least 1 coin, we remove 3 coins, 3^8 = 6561

  2. What if we change the question a little bit.
    First let's keep : "each person has to get at least 1 coin."
    But then add : " each person has to get at most 7 coins."
    ?????????????

  3. But can't two people have 0 and the other guy gets 11? If so then there should be 169 ways to do it. Each slot can be on any of the 13 spaces. Slots can coincide on the same space. So it's 13*13 = 169.

  4. For those not understanding the video's solution, I think it is better to think of an analogous problem:
    1. How many ways can 3 non-negative integers sum to 11?
    2. How many ways can 3 positive integers sum to 11?

    For #1: Pretend we have 11 1's like this: 1 1 1 1 1 1 1 1 1 1 1

    By putting two dividers between 1's, we see that we can split the number of 1's that each person gets.
    Ex: 1 1 1 1 (divider) 1 1 1 1 1 (divider) 1 1 –> Translates to 4 + 5 + 2.

    If we put a divider before the first 1, the first integer = 0
    If we put a divider after the last 1, the last integer = 0
    In addition, we can have two consecutive dividers; the middle integer = 0

    Thus, the question becomes how many ways can we arrange 11 1's and 2 dividers.
    This is basically the same question: How many 13-letter unique words can be made with 11 A's and 2 B's?

    If you know Combinations: (11 + 2)! / (11! * 2!) = 13! / (11! 2!) = 13 * 12 / 2 = 156 / 2 = 78 ways

    If you don't know Combinations, think about it this way:

    You can arrange the 11 1's and 2 dividers in 13 * 12  * 11… * 3 * 2 * 1 ways. This works because the first letter can go anywhere in the 13 spaces for the word, the second letter will have 12 spaces then to choose from, followed by 11 for the third letter, etc.
    However, this includes repeats, as swapping two A's still give the same word.

    Just like two A's can be arranged 2 * 1 ways –> Second A, First A or First A, Second A:
    11 A's can be arranged 11 * 10 * 9… * 3 * 2 * 1 ways
    2 B's can be arranged 2 * 1 ways

    Since the above ways are repeats, we need to divide them from 13 * 12 * 11… 3 * 2 * 1 ways (Total Possibilities with repeats)

    You see that when we divide 13 * 12 * 11 (Total Possibilities including repeats)…. by 11 * 10 * 9 (Repeats for A's…), we can call 11 * 10 * 9… = x and 13 * 12 * 11… as 13 * 12 * x. Dividing them, you get (13 * 12 * x) / x = 13 * 12 = 156 ways.

    Now, we divide again by 2 * 1 (Repeat for B's…)  = 2.
    156 / 2 = 78 ways

    For #2: Again, Pretend we have 11 1's like this: 1 1 1 1 1 1 1 1 1 1 1

    Unlike the first question, we can't put a divider before the first 1 (First Integer MUST be positive), we can't put a divider after the last 1 (Last Integer MUST be positive), and we can't have two consecutive dividers (Middle Integer MUST be positive)

    Then, the only place the dividers can go is between the 1's, and not overlapping.
    We have 2 dividers and 10 spaces between the 11's.

    The first divider can go in any of the 10 spaces. The second divider can go in the remaining 9 spaces (Not OVERLAPPING)
    This gives 10 * 9 = 90 ways.

    However, the first divider and second divider can switch positions and still count as the same set.
    EX: 1 1 1 1 (1st divider) 1 1 1 1 1 (2nd divider) 11    &   1 1 1 1 (2nd divider) 1 1 1 1 1 (1st divider) 11  are BOTH STILL 4 + 5 + 2

    Therefore, we divide 90 ways / 2  = 45 ways

  5. THere is one way to split 11 coins between 3 people, its fair. Destroy all the coins, each person gets 1/3 of all the ash

  6. So basically you have 8 coins to give to three people and in the end everyone gets another one.
    And then we just use (10 2) which equals 45 and that's the number of ways.

    [WATCHES VIDEO]

    Exactly.

  7. I just gave blue 0 coins meaning there were 12 ways to distribute the coins between red and green. Then when Blue had 1 coin, there were 11 ways. So I added 12+11+10…+2+1 to get 78. For the extra condition, I subtracted 12 from 78, because that was when we gave blue 0 coins. Then I subtracted 1 because there's only 1 way to distribute the "remaining" coins when we give blue 11 coins (0 to red and green). Lastly, I subtracted 20, because 10 remaining ways to give blue coins * 2 remaining coin distributions (0 to red or 0 to green) = 20. 78-20-1-12= 45.

  8. Can someone explain to me why at around 3:38 N + r – 1 choose r – 1 Is equal to N + r – 1 choose N? Because if you plug in the values 11 identical items and r people it doesn’t work for N + r – 1 choose N

  9. Ok. if you give 0 to the first person, then there are 12 ways for the other 2. If you give 1, then there are 11. So it's 12+11+10+9…1 = 78. Done.

  10. What if I want to know the probability of person Green receiving 5 coins?
    (with randomization assumed)

  11. I assume that counting each of method I can see would take to long on interview ut at least the naswer would be correct

  12. I dont think it is right. Suppose we give 11 coins to 3 people one by one. At first, we have three option, we can we the coin to person 1 or person 2 or person 3.Then when we come again with second coin, we will again have 3 option and similarly so on. So the ans should be 3^11,because every time we come with a coin we will have three option untill a coins are finished.

  13. Part 1 solution is wrong. because the red divider can't be left to the blue one. The forumla you used count those options, therefore it is wrong.

  14. If each person has to get at least 1 coin… There are 135 ways to split them… I don't understand why 45?

  15. OOaaahaha, there are so many missing optional sterotypical stick figure side stories to this problem… like: who's making the money handed out here? Why aren't they visible? ..but the answer is…
    ..
    ..
    ..
    ..
    78

  16. Soon solving systems of equations will be considered TOUGH. Gah society simultaneously gets smarter and stupider every year.

  17. Pause the video give the problem a try..okay Let 11 coins be split 3 ways is there an equation this community college drop out could develop to represent the problem…let n = the number of combinations and on my paper in long and this just got too big. I am fuking cluless. If A gets 0 there are 11 possible combos and if A gets 1 there are (11-1) more and if A gets 2 there are 11 more until A gets 11 then there is just one more combo. Then do the same for B minus any over lap and again for C minus any overlap which there should be some equation for this I give I am a stupid man Somewhere around three hundred so what?

  18. I wish i understood the mathematical grammar, he writes out some stuff I can not follow but should be able to. What is the operation "choose" over. I am lost

  19. You can also graph it using a piecewise function or use the possible # of coins per person as "N" and use the (N^2+N)/2 For example, the range from 1 coin to 9 coins. You have 9 different options for one person. Thus, giving the equation (9^2+9)/2 = 45. OR if you use the first rule only. Its 0 coins to 11 coins. Thats 12 options. (12^2+12)/2 = 78. Hope someone finds this interesting. Peace!

  20. for i in range(0,12):
    for j in range(0,12-i):
    print(i,j,11-i-j)

    for i in range(1,12):
    for j in range(1,12-i-1):
    print(i,j,11-i-j)

  21. Tbh I think there’s an infinite amount of ways because you can split each individual coin an infinite amount of times. Of course this is a huge leap in logic, but hey! There’s always another option.

  22. You go with the lowest value: 1,1,9 (because there are two same number 1 and 1 there are 3 combinations for that, 1,2,8 (6 combinations) 1,3,7 (6 comb) 1,4,6 (6comb) 1,5,5 (3comb) for 1 in it there are 24.
    Now with 2,2,7 (3) 2,3,6 (6) 2,4,5 (6)== 15
    3,3,5 (3) 3,4,4 (3) ==6
    24+15+6=45

  23. After the first part of the problem, I thought the answer to the second part would be 72, since there are 6 ways in the first part where someone gets 0 coins. Have I missed something? Why does that not check out?

  24. Hi Presh.
    I always used to watch your videos. but I am commenting in any one of your videos for the first time as I feel like that unintentionally your math solve gone wrong.
    My solve gives the result not 78 but anything else. it is 81. May be you've missed something or I count something extra.

    My solve:
    At least 1 person will get 0 coin, the probable different conditions are as follows
    A B C
    1.0 0 11
    2.0 1 10
    3.0 2 9
    4.0 3 8
    5.0 4 7
    6.0 5 6
    so this are the conditions while at least one person will get no coin.
    every condition can be rearranged in 6 different ways for example condition no. 2
    A B C
    0 10 1
    0 1 10
    1 0 10
    1 10 0
    10 1 0
    10 0 1
    except condition no. 1 which only can be rearranged in 3 different ways two persons get same amount.

    Now we Will consider other conditions. now everyone will get at least 1 but nobody gets 0.
    A B C
    7. 1 1 9
    8. 1 2 8
    9. 1 3 7
    10.1 4 6
    11. 1 5 5
    In this case conditions like 7&11 can be rearranged in 3 different ways while others can be rearranged in 6 different ways.

    Now we will consider nobody gets 0 or 1 coin (as we already counted them) that means everyone gets at least 2 coins.
    A B C
    12. 2 2 7
    13. 2 3 6
    14. 2 4 5
    Now we will consider the case at least 3 coins for each
    A B C
    15. 3 3 5
    16. 3 4 4

    These are the total 16 distinct conditions are available.
    here, here 5 conditions (7,11,12,15&16) where two persons get same amount so these conditions can be rearranged in 3 different ways. for other 11 cases where 3 persons get different amounts can be rearranged in 6 different ways as I illustrated before with an example.
    so total ways= 5*3+ 11*6=15+66=81.

    if I make anything wrong in my calculations let me know via reply then I'll be grateful.
    waiting for your reply
    Azad

  25. This is permutations and combinations. learning nCr , nPr formulas by heart Will easily do the trick, nothing great. only rote learning like parrots.

  26. Just ended visualizing a divider at the start, then moved the second one to the end, and gradually working the first divider to the end.
    So we get 12+11+10+9+8…+2+1 equaling 13*8=78.

  27. Another way to do it. 12 glasses, with 11 coins as spacers between the glasses. In reserve you have less than 1/2 glass each of blue-tinted and red-tinted water. Pour blue water into any glass and give Person Blue all of the coins to the left of that glass. Pour red water into any glass not left of the blue water and give Person Red all of the coins between the red and blue glasses. (You have less than 1/2 glass each of blue and red water so that you can pour all of both into the same glass, making purple water, so that Person Red gets no coins.) Person Green takes all of the remaining coins, which are the ones to the right of the red (or purple) glass. How many combinations are possible? Well, there's 144 ways to allocate the water: 2 choices from among 12 glasses each, so, 12X12, which is 144. Of these 144 ways, 12 will consist of pouring both the blue water and the red water into the same glass. Subtracting, this means 132 ways will have the blue water and the red water in separate glasses. Of those 132, half will consist of having the blue as further left and the red as further right, and the reverse condition will be true of the other half. Only the ones in the first half give an acceptable result (since we can't give Person Red a NEGATIVE number of coins) while the other half's are not valid. So, there's 66 (1/2 of 132) VALID ways to put the two colors of water into TWO glasses. Add to these the 12 ways to put both colors in the same glass, and you get 78 combinations, which, according to this video, is the right answer. Now why did I use pouring colored water into glasses rather than 12 plates, with 1 coin between adjacent plates, and placing colored objects on the plates? It's because in the latter analogy one of the objects could be, on the plate, further left or further right of the other object, leading us to think that of the 12 combinations where both colors are on the same "node" half will be invalid because of left-right inversion. Not true, because in the placing of the objects in the 144 different ways the two possible "lies" of objects on the same plate are NOT additional permutations. By using water in glasses I ensure that when blue and red are at the same node, the left-right distinction is destroyed (as it needs to be) in a mixture of purple water where neither the blue nor the red has a leftness nor a rightness.

  28. If you vote Democrat, then EVERYONE can get 11 coins… 11 actual coins plus 22 additional coins you simply add to the national debt. This way everybody wins… (until the next generation who has to pay it all back with interest).

  29. The solutions given seem unnecessarily complicated. Each of the two dividers can be in one of 12 locations. So there are 144 possibilities. Twelve of those are unique (where both dividers are in the same location). That leaves 132 other possibilities, which occur in pairs (eg. first divider in location A, second in B, and vice-versa are the same), so that's 132/2 = 66 unique ways. 66+ 12 = 78. I don't see the justification – or the need – in the first method for using extra coin location for the dividers – especially since the graphic which introduces the dividers shows them (correctly) drawn between the coins!

  30. i think about it second time, (i find a good logic after first time) i solve it.

  31. write the combinations, in example: 0 1 10, look for all combinations; 0 1 10, 10 1 0, 1 10 0 , 0 10 1, 10 0 1, 1 0 10. All combinations for this series is 6. Write 6 for each combinations formed with different numbers. Write 3 for each combinations formed with to same numbers(in example: 2 2 7).And add all of them. it will be 78. and for give everyone atleast one coins; decrease 78 for every combination formed with 0 and this combination value (6 or 3).it will be 45.

  32. Jay-Z gets 6 coins, Beyonce gets 5 coins, I get 0 coins
    Beyomce gets 6 coins, Jay-Z gets 5 coins, I get 0 coins
    This is the basics of equality – so there are 2 answers in reality.

  33. So how would one put on upper limit with this system? I.e. say that any one person can’t have more than 5 coins.

  34. I did the second part in a different way.
    No. of ways in which each get at least 1 coin = 78 – no. of ways in which 1 or 2 people get 0 coins.
    So , first if we consider the first person gets 0 coins , then the 11 coins would be distributed over 2 remaining people which is 11C1 i.e. 11 ways. But , the same thing can be done with the second or third people getting 0 coins. So, the total no of ways =3*11= 33 ways.

    So, the required no. of ways =78-33= 45 ways. 🙂

  35. I think your first solution is wrong by 1. To divide 11 coins among 3 people assumes that at least 1 of them gets something. So placing the divider on the 1st and 2nd position is excluded.

  36. Isn't this supposed to be an easy question even for 15 year olds?

    I remember feeling happy to see such a question on the tests because things was the easiest question they could potentially give on our tests

  37. Well, the ideal answer the interviewer probably was after, would have been that the test person takes one extra coin out of his pocket and gives each person four coins, instead of starting to make complicated mathematical calculations that will not add up fairly anyway 😀

Leave a Reply

Your email address will not be published. Required fields are marked *