5 Questions...

[proff.hacker]

could you help me to find the solution of the following questions:

1- How many strings of 20 decimal digits are there that contain two 0s, four 1s, three 2s, one 3, two 4s, three 5s, two 7s, and three 9s?

2- How many solutions are there to the inquality:
x1 + x2 + x3 £ 11
Where x1, x2, and x3 are nonnegative integers? (Hint: Introduce an auxiliary variable x4 so that x1 + x2 + x3 +x4 = 11.)

3- How many positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal to 13?

4- How many ways are there to distribute five distinguishable objects into three indistinguishable boxes?

5- How many terms are there in the expansion of (x + y + z)^ 100?


thanks and regards

[[Digital-X-Treme]]

Maybe you should do your own homework once in a while... :):p

[proff.hacker]

OK [Digital-X-Treme]

I am trying to do my own :) but I like to get your answers to make sure that mine is correct


really I Like yours..

thanks

[[Digital-X-Treme]]

Ok, post up your answers first, then I will give some info...

[[Digital-X-Treme]]

Number 3. Using this code...'
'Coded by [Digital-X-Treme]
'Q. How many positive integers less than 1,000,000 have exactly
' one digit equal to 9 and have a sum of digits equal to 13?
'
Option Explicit

Private Sub Form_Load()

Dim i As Long
Dim lngCount As Long

For i = 1 To 999999
DoEvents
If (OneDigitEqualToNine(i) And SumOfDigitsEqualToThirteen(i)) Then
lngCount = lngCount + 1
End If
Next i

Debug.Print "There are " & lngCount & " numbers between 0 and 999999 that have one digit equal to 9 and a sum of digits equal to 13."

End Sub

Private Function OneDigitEqualToNine(ByVal Number As Long) As Boolean

Dim strNumber As String
Dim i As Integer
Dim j As Integer

strNumber = CStr(Number)
j = 0

For i = 1 To Len(strNumber)
If Mid(strNumber, i, 1) = "9" Then
j = j + 1
End If
Next i

If j = 1 Then
OneDigitEqualToNine = True
Else
OneDigitEqualToNine = False
End If

End Function

Private Function SumOfDigitsEqualToThirteen(ByVal Number As Long) As Boolean

Dim strNumber As String
Dim i As Integer
Dim j As Integer

strNumber = CStr(Number)
j = 0

For i = 1 To Len(strNumber)
j = j + CInt(Mid(strNumber, i, 1))
Next i

If j = 13 Then
SumOfDigitsEqualToThirteen = True
Else
SumOfDigitsEqualToThirteen = False
End If


End Function


...I got an answer of 420.

[DerFarm]

I get a different answer when I don't use code.

All numbers must have a 9 and only one 9. All numbers digits
must add to 13. This is equivalent to saying that all numeric
digits must add to 4 and there is also a 9. and must be no more
than 5 positions

Digits that add to 4 are: 1,3 3,1 2,2 and 4,0

4,0: 400000,40000,4000,400,40,4 are the only combinations.
There are, however 5 different combinations of one 9 in each.
6*5=30 instantiations of 4,0

2,2: Note that there are 5 possible positions where 2,2 have no
intervening 0, 4 where there is one intervening 0, 3 with 2, 2 with
3, 1 with 4. This exhausts the set because there is no
differentiation between the 2's (as opposed to backgammon
where the 2's are NOT equal). Of course, for every entry in the
set there are 4 possible entries for the 9. 15*4 = 60 entries for
2,2

1,3: 1 and 3 are analogus to 2,2 except that the entries are
doubled because 1,3 is not equal to 3,1. There are still 4
possible places for the 9. 1,3 has 15*4=60 3,1 has 14*4
entries = 120 entries.

I think the answer is 120 + 60 + 30 = 210.


*******************************
MY BAD!!! I left out 1,1,1,1 and 1,2,1

1,1,1,1: is the same as 2,2 (you consider the position of the 0's)
but there are only twice the number, not 4 times the number of
9's. 30 entries


1,2,1 is the same as 2,2 (consider only the 1,1) with 4 different
places for the 2 in each and 3 different places for the 9. Therefore:
15*4*3 = 180

New Answer: 180+120 + 60 + 30 + 30 =420

[proff.hacker]

the following answers are just a try
[Question 1]
No Answer :(

[Question 2]
x1+x2+x3+x4=11
C(4+11-1,11)=C(14,11)=C(14,3)=14*13*12/6

[Question 3]
No Answer :(

[Question 4]
5!/3!=20

[Question 5]
what I reached to is that when we have an expansion of this form
(x+y+z)^n
n=1, the number of terms are 3
n=2, the number of terms are 6(3+3)
n=3, the number of terms are 10(6+4)
n=4, the number of terms are 15(10+5)
n=5, the number of terms are 21(15+6)
but I cannot make a general rule for n


could you correct me and help me with the questions that I didn't solve.

[kedaman]

1- How many strings of 20 decimal digits are there that contain two 0s, four 1s, three 2s, one 3, two 4s, three 5s, two 7s, and three 9s?
20C2*18C4*14C3*11*10C2*8C3*5C2=about 59 trillion

[kedaman]

3- How many positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal to 13?
9*(8+8*7+8C2)=828

[DerFarm]

On number 1, observe that the problem is essentially the same
as #3.

Further note that the number of X,X combinations (2,2 or 4,4....)
can be found using the formula:


NumComb = sigma(R) where R runs from 1 to R-1


since there are exactly 20 objects being searched for there is no
reason to worry about the placement of the searched for items.
Thus, if you can find the number of possible placements for each
individual set of items (two 2's + four 1's, +...) you have the
number of individual numeric entities......I think.....maybe


Probably somewhat less than 52 trillion!:D

[kedaman]

5- How many terms are there in the expansion of (x + y + z)^ 100?
(2+N)C2

[kedaman]

Originally posted by DerFarm
On number 1, observe that the problem is essentially the same
as #3.

Further note that the number of X,X combinations (2,2 or 4,4....)
can be found using the formula:


NumComb = sigma(R) where R runs from 1 to R-1


since there are exactly 20 objects being searched for there is no
reason to worry about the placement of the searched for items.
Thus, if you can find the number of possible placements for each
individual set of items (two 2's + four 1's, +...) you have the
number of individual numeric entities......I think.....maybe


Probably somewhat less than 52 trillion!:D
Well not sure what you mean,
if you have
10
and
01
they would be different strings ok?

[kedaman]

NumComb = sigma(R) where R runs from 1 to R-1


The number of combinations of k elements in n is nCk=n!/(k!(n-k)!)

[DerFarm]

nCk = 20!/(2!(18!)
2432902008176640000/(2*6402373705728000) =
2432902008176640000/12804747411456000=

190

Now then sigma(19) = 190:eek:

Gee. Looks the same to me.

In this case there are 3 sets of 2's = 570.

for four 1's (using nCk) = 2432902008176640000/(4!*(16!)=
2432902008176640000/(24*20922789888000)=
2432902008176640000/502146957312000=4845

For the triplets you get:

2432902008176640000/6*355687428096000=
2432902008176640000/2134124568576000=1140


Since there are 3 of them: 1140*3 = 3420

Adding it all up:



Singles: 20
doubles: 570
triples: 3420
Quads: 4845
-----------------------
8855 distince numeric entities



I used http://www.cs.uml.edu/~ytran/factorial.html to figure the
factorials.

I used the MS calculator to perform the calculations. And I'm
convinced that there is a better way to do it. You can't do the
calculations required by hand in any reasonable amount of time.

by writing it all out and doing prodigious cancelling you end up with:

(3*19*10) + (17*3*19*5) + (3*3*19*20) + 20
570 + 4845 + 3402 + 20

should be right!

[kedaman]

Sumof (aka sigma) s=1 to n is n(n+1)/2, which happens to be nC2, but this only works for k=2
Your solution looks flawed to me:
1. Out of 20 available you will have 18 left after using 2
2. Similarly you can't multiply combinations of same amount
3. "a and b" is a*b not a+b
just some basic probability calculus :)
I use my Ti-83, quite handy. You'd rather not calculate the factorials separately in large combinations, because they will be quite huge, instead you could iterate n*(n-1)*..k

[DerFarm]

Sorry, K, but you CAN simplify factorials.

6! = 6*5*4*3*2*1

5! = 5*4*3*2*1

6!/5! = 6*(5!)/5! since 5!=5! you can simplify.

[kedaman]

yep, thats what i meant about iterating n*(n-1)*..k

[DerFarm]

Kinda hard to iterate with a pencil and a piece of paper. When I
learned probabilities, Ti's cost about $500 (US) and were rarer
than hen's teeth.

paper was cheap, student's time was cheaper, and you could
ALWAYS steal a pencil!:D

[kedaman]

well its better than typing out those ridiculous factorials ;)

[[Digital-X-Treme]]

Originally posted by kedaman
3- How many positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal to 13?
9*(8+8*7+8C2)=828

Why is that? I manually checked all numbers below 1000000 and came up with 420. DerFarm also arrived at this conclusion. COuld you elaborate on how you arrived at this answer?

[kedaman]

1. Out of 9 digits you have 9 combinations to place a 9
and
2. The rest in the sum is 4, and could be in these combinations:
a) 4 - 8 combinations or
b) 3,1 - 8 and 7 combinations or
c) 2,2 - 8C2 = 28 combinations
sums up to 92 combinations

all in all 9*92=828 combinations.
check your code for bugs.

[DerFarm]

ummmmm, Kedamon? What about 1,1,1,1 and 1,2,1?

Digital, I think your code sucks also, but only because it's totally
brute force, no finesse. You check every number between 0 and
999999

I've got some time, I'm going to try to do something with it....of
course, it might actually be the only way to do it! In which case,
I'm then one whose screwed up!

BTW, for quick and dirty, I agree that your code is best! Just not

[using a limp wrist and foo-foo accent]
Elegante
[/using a limp wrist and foo-foo accent]


:D :D

[kedaman]

lol thanks for pointing that out :)
9*(8+8*7+8C2+8C4+8*7C2)=2970

[proff.hacker]

so what's the final answer for my questions.

[DerFarm]

well, according to Digital and Me, the final answer for #3 is 420.
According to Kedamon its.....something else, he's not quite sure
yet!

[[Digital-X-Treme]]

The code i provided:[list=1]
Does not suck. (DerFarm :mad::p)
Proves the answer to question 3 by Exhaustion.
[/list=1]
The final answer for question 3 is 420.

[DavidHooper]

The answer to question 5 is actually 5151. almost there keda. :)

I haven't got time to do the others - I can't do them straight off ;)

[DerFarm]

Well, you're right about part of it, Digital...It's exhaustive!!

But it won't handle anything but base 10, it won't handle ranges,
and it won't allow for anything except one 9 and the rest adding
to 4.

Brutal....sledgehammer tactics.

[DavidHooper]

I can't read your inequality for question 2.

If it says x1 + x2 + x3 < 11 then the answer is 286
If it says x1 + x2 + x3 <= 11 then the answer is 364

[prog_tom]

I think the answer to question 5 is:

101

[DavidHooper]

Well you're wrong then. At the very least you could solve this quadratic:

[Question 5]
what I reached to is that when we have an expansion of this form
(x+y+z)^n
n=1, the number of terms are 3
n=2, the number of terms are 6(3+3)
n=3, the number of terms are 10(6+4)
n=4, the number of terms are 15(10+5)
n=5, the number of terms are 21(15+6)
but I cannot make a general rule for n

[thinktank2]

1) 1- How many strings of 20 decimal digits are there that contain two 0s, four 1s, three 2s, one 3, two 4s, three 5s, two 7s, and three 9s ?

What Kedaman did is correct !

Think about this way.. we consider 0s,1s,2s,... as groups

The 0 group has 2 members
The 1 group has 4 members
The 2 group has 3 members
The 3 group has 1 members
The 4 group has 2 members
The 5 group has 3 members
The 7 group has 2 members
The 9 group has 3 members

Now Consider I have two boxes, Box1 and Box2. Box2 is empty
Box1 contains these digits grouped together.
001111222344555779

Now If I pick 2 digits from the 20 digits and place it in box2.
There are 20C2 ways for all of the 0s group to be in box2.
= 20C2 = 20!/(2! * 18!)

Box1 now has 20 - 2 = 18 digits

If I pick 4 digits from the remaining 18 digits and place it in box2.
There are 18C4 ways for all of the 1's group to be in box2.
= 18C4 = 18!/(4! * 14!)

Box1 will then have 18 - 4 = 14 digits

The process is repeated till all the groups are in box2.
The number of ways each group ends up in box2 ..

0's ----- 20C2 = 20!/(2! * 18!)
1's ----- 18C4 = 18!/(4! * 14!)
2's ----- 14C3 = 14!/(3! * 11!)
3's ----- 11C1 = 11!/(1! * 10!)
4's ----- 10C2 = 10!/(2! * 8!)
5's ----- 8C3 = 8!/(3! * 5!)
7's ----- 5C2 = 5!/(2! * 3!)
9's ----- 3C3 = 3!/(3! * 0!)

I have picked these groups in an order. But they can be picked up in any order,
so there are 20C2 * 18C4 * 14C3* 11C1 * 10C2 * 8C3 * 5C2 * 3C3 ways.

= [ 20!/(2! * 18!) ] * [ 18!/(4! * 14!) ] * [ 14!/(3! * 11!) ] * [ 11!/(1! * 10!) ]
* [ 10!/(2! * 8!) ] * [ 8!/(3! * 5!) ] * [ 5!/(2! * 3!) ] * [ 3!/(3! * 0!) ]

{ Note the factorial in the denominator cancels the numerator of the next term. }

= 20! / (2! * 4! * 3! * 1! * 2! * 3! * 2! * 3!) ways

= 58663725120000 ways.

58663725120000 ways to arrange the digits in box2 and hence 58663725120000 different
20 digit strings.

In general, If out of N objects, A number of objects are of type1, B of type 2, C of ...etc
Such that A+B+C+.... = N Then the number of distinguishable permutations

= N! / (A! * B! * C! * ...) ---------> {Reference 1}

_________________________________________________________________________________________________

2- How many solutions are there to the inquality:
x1 + x2 + x3 £ 11 Where x1, x2, and x3 are nonnegative integers? (Hint: Introduce an auxiliary variable x4 so that x1 + x2 + x3 +x4 = 11.)

a)If the question is to find the number of solutions for x1 + x2 + x3 <= 11
then in Equation x1 + x2 + x3 + x4 = 11 , x4 is >= 0

let us take sample values for x1,x2,x3,x4 such that x1 + x2 + x3 + x4 = 11
say, x1 = 5, x2 = 2, x3 = 3 and x4 = 1 so that 5 + 2 + 3 + 1 = 11

Since x1,x2,x3 and x4 are all non negative Integers, We can encode this
to a string like, *****|**|***|*

The x1 is represented by 5 *'s, x2 by 2*'s, x3 by 3*'s and x4 by 1 *

The different variations of this string will represent the different values x1,x2,x3 and x4 can take such that x1 + x2 + x3 + x4 = 11

for example, ***|***|**|*** will denote x1 = 3, x2 = 3, x3 = 2 , x4 = 3

we can allow x4 to be zero(Since x4 >= 0), hence ****|****|***| is a valid variation.

To find out the number of distinguishable variations of this string, see {Reference 1}

Total length of the string = 14, Number of *'s = 11 and Number of |'s = 3
Therefore, Number of distinguishable variations of the string

= 14!/(11! * 3!) = 14 * 13 * 12 / 6 = 14 * 13 * 2 = 364

This implies, x1 + x2 + x3 + x4 = 11 has 364 solutions When x4 >= 0
that is to say, x1 + x2 + x3 <= 11 has 364 solutions.

In general, x1 + x2 + x3 + x4 + x5 + .....+ xn = y has
(y + [n-1])! / ( y! * [n-1]! ) number of solutions. ---------> {Reference 2}

b) If the Question is to find solutions for x1 + x2 + x3 < 11
Then it excludes all solutions of x1 + x2 + x3 = 11

From {Reference 2}, x1 + x2 + x3 = 11 has

(11 + [3-1])! / ( 11! * [3-1]!) = 13! / (11! * 2!) = 78 Solutions.

Therefore No. of solutions for x1 + x2 + x3 < 11

= ( No. of solutions for x1 + x2 + x3 <= 11 ) - (No. of solutions for x1 + x2 + x3 = 11)

= 364 - 78 = 286 solutions.

Conclusion :
a) x1 + x2 + x3 <= 11 has 364 solutions.
b) x1 + x2 + x3 < 11 has 286 solutions.
c) x1 + x2 + x3 = 11 has 78 solutions.
_________________________________________________________________________________________________

3- How many positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal to 13?

The range is 1 to 999999 (Maximum 6 digits)

Since exactly one of the digits should be 9 and the sum of the digits = 13, we can say that sum of the digits other than 9 should be equal (13 - 9) = 4

we represent 5 digits as x1,x2,x3,x4,x5 and keep the sixth digit as 9 such that
x1 + x2 + x3 + x4 + x5 = 4

The number of solutions for the above equation [see {Reference 2}]
= (4 + [5-1])! / ( 4! * [5-1]! ) = 8!/(4! * 4!) = 70

The number of solutions is the same when we keep the 5th,4th,3rd,2nd or the 1st digit to be 9 and the other digits to be variables.

So there are totally 70 * 6 = 420 solutions.
_________________________________________________________________________________________________

4 - How many ways are there to distribute five distinguishable objects into three indistinguishable boxes?

Let the 5 distinguishable objects be a,b,c,d and e

We can encode the information to a string like ab|cd|e which means
objects a and b are in box 1, objects c and d are in box 2 and object e is in box 3.

All variations of this String can represent what each box has.
example : a|ecb|d means box1 has a , box2 has e,c,b and box3 has d.

So, the number of distinguishable variations of the string (of length = 7 with 2 |'s)

= 7! / (2!) = 2520 [see {Reference 1}]
_________________________________________________________________________________________________

5- How many terms are there in the expansion of (x + y + z)^ 100?

we know that (x + y)^n can be expanded to (n+1) terms.

let u = (x + y), then (u + z)^100 can be expanded to

u^100 + 100C1 * u^99 * z + 100C2 * u^98 * z^2 + .........+ 100C99 * u * z^99 + z^100

u^100 = (x+y)^100 can be expanded to 101 terms
u^99 = (x+y)^99 can be expanded to 100 terms
u^98 = (x+y)^98 can be expanded to 99 terms
.....
.....
u^2 = (x+y)^2 can be expanded to 3 terms
u = (x+y) can be expanded to 2 terms
and z^100 is 1 term

Adding the number of terms...

101 + 100 + 99 + 98 + 97 + ..... + 3 + 2 + 1

Sum up to m integers counting from 1 is equal to = m(m+1)/2
which numerically equals to (m+1)C2
here m = n+1 = 101 ,
Therefore the number of terms in the expansion of (x+y+z)^n is

= (n+1)(n+2)/2 = (n+2)C2

Thus (x + y + z)^ 100 can be expanded to (101 * 102 / 2) terms = 5151 terms
_________________________________________________________________________________________________