d2jsp
Log InRegister
d2jsp Forums > Off-Topic > General Chat > Homework Help > Discrete Math/probability Questions
Add Reply New Topic New Poll
Member
Posts: 19,894
Joined: Oct 28 2008
Gold: 1,317.96
Nov 9 2018 06:53pm
hey there, need help with the below questions, willing to pay


3. Suppose we have a piles of 10 pennies, a pile of 10 nickels, a pile of 10 dimes , a pile of 9 quarters and a pile of 8 half-dollar coins
a) How many ways to pick 8 coins from those five piles of coins?
b) How many ways to pick 9 coins from those five piles of coins?
c) How many ways to pick 10 coins from those five piles of coins?
d) How many ways to pick 11 coins from those five piles of coins?
e) How many ways to pick 11 coins from those five piles of coins which must consists of all five different value of coins?




4. The question is about 13-bit strings.
a) How many 13-bit strings that have no consecutive three 0’s in a row?


5. How many ways are there to pass out 20 candies (assume all the candy are identical the same) to six children? Base on the following condition:

a) No restriction.

b) Every child receives at least one candy.

c) None of child receives the same number of candies.
Member
Posts: 16,662
Joined: Nov 24 2007
Gold: 15,245.00
Trader: Trusted
Nov 11 2018 02:05pm
3a)

There is no restriction on the number of each kind of coin.

Suppose you have a word of 8+5-1 = 12 letters 'O' :
OOOOOOOOOOOO

Now decide where you place 5-1 = 4 letters 'X' :
OXOXOOOXOXOO

Letters 'X' are separators between all different kind of coins.
The above word means :
1 penny - 1 nickel - 3 dimes - 1 quarter - 2 half-dollars

Each one of those words corresponds to a distribution of coins, and each distribution of coins corresponds to one of those words.

The number of all different such words is the number of choices of 4 places among 12 : this is a binomial coefficient, equals to 12 x 11 x 10 x 9 / ( 4 x 3 x 2 x 1) = 495

3bcde)
I don't know how to solve that kind of problem in a general way. Let me know if this something of interest for you, I could try to find something.
Given your values, I would simply proceed by subtracting impossible distributions :

b ) 9 coins :
subtract 1 impossible distribution (9 half-dollars)
answer = binom(13,4) - 1

c) 10 coins :
subtract 6 impossible distributions ( 10 half-dollars, or 9 half-dollars and 1 random coin, or 10 quarters)
answer = binom(14,4) - 6

d) 11 coins :
subtract 23 impossible distributions (I let you do the list)
answer = binom(15,4) - 23

e) 11 coins with at least 1 of each.
This is the same problem as picking 6 coins from piles consisting in 9 pennies, 9 nickels, 9 dimes, 8 quarters, 7 half-dollars (hence, no restriction)
answer = binom(10,4)

4) Another very interesting problem.
Let n an integer, and Un the number of n-digits strings without 3 '0' in a row.
U0 = 1 (empty string) = 2^0
U1 = 2 = 2^1
U2 = 4 = 2^2
U3 = 8 - 1 = 7, because obviously, all the 2^3 = 8 strings of length 3 are good, except '000'.

Now, proceed by induction :

Consider a string of length n+3 with no '000' :
the finishing part can be :
100
X10
XX1

where X denotes, indifferently, 0 or 1.

if the finishing part is 100, then all the n first digits must form a random working string : there are U_n of such strings.
if the finishing part is X10, then all the (n+1) first digits must form a random working string : there are U_(n+1) of such strings.
if the finishing part is XX1, then all the (n+2) first digits must form a random working string : there are U_(n+2) of such strings.

Hence : U_(n+3) = U_(n+2) + U_(n+1) + U_n

It's enough to compute the answer : U_13 = 3136

If you want a formula with variable 'n', then you must first solve : X^3 - X^2 - X - 1 = 0

Let me know, in this case, I'll go deeper into it.

5)

a) This is the same problem as 3)
Each child is a different kind of coin :
child #1 is a penny
child #2 is a nickel
...
child #6 is $1 banknote

Would you decide to give 2 candies to child1, and 18 candies to child2 (and no candy to other children), then that's a pile of 2 pennies and 18 nickels.

Answer = binom(25,5) = 25 x 24 x 23 x 22 x 21 / ( 5 x 4 x 3 x 2 x 1 )

b ) Give them 1 candy, and now, make a distribution of 15 candies to 6 children.
Answer = binom(20,5)

c) The problem seems to me very different now.
You must find the number of partitions of 20 into a sum of ordered and different non negative integers.
Notice that 1 children must recieve no candy (because 1+2+3+4+5+6 > 20).
ie :
20 = 0 + 1 + 2 + 3 + 4 + 10
20 = 0 + 1 + 2 + 3 + 5 + 9
20 = 0 + 1 + 2 + 3 + 6 + 8
20 = 0 + 1 + 2 + 4 + 5 + 8
20 = 0 + 1 + 2 + 4 + 6 + 7
20 = 0 + 1 + 3 + 4 + 5 + 7

there are only 6 different possibilities to form 6 piles of candies without the same number of candies.

Now it's time to give 1 pile to each child : this is a permutation of a set of 6 items : 6 ! = 6 x 5 x 4 x 3 x 2 x 1 possibilities.

Answer = 6 x 6 !

This post was edited by feanur on Nov 11 2018 02:06pm
Go Back To Homework Help Topic List
Add Reply New Topic New Poll