Posted on 14 December 2016 - 09:54 PM
ok @AlbertEinstein I have a few problems that may stump even you.1. In a race with 30 runners where 8 trophies will be given to the top 8 runners (the trophies are distinct: first place, second place, etc), how many ways can this be done?
2. How many ternary strings of length 4 have at least 2 ones?
3. How many permutations are there of the word "repetition"?
4. Prove that the sum of the degrees of the vertices of any finite graph is even.
5. Consider the sequence 01110100 as being arranged in a circular pattern. Notice that every
one of the eight possible binary triples: 000, 001, 011, . . . , 111 appear exactly once in the
circular list. Can you construct a similar list of length 16 where all the four binary digit
patterns appear exactly once each? Of length 32 where all five binary digit patterns appear exactly once?
6. Show that any graph where the degree of every vertex is even has an Eulerian cycle. Show
that if there are exactly two vertices a and b of odd degree, there is an Eulerian path from a
to b. Show that if there are more than two vertices of odd degree, it is impossible to construct
an Eulerian path.
Good luck :)
Posted on 14 December 2016 - 10:23 PM
O_oPosted on 14 December 2016 - 10:27 PM
https://www.google.com/Posted on 14 December 2016 - 10:41 PM
Automatically DeletedPosted on 14 December 2016 - 11:27 PM
Is the answer to the first one 2.35989936x10^11?Posted on 15 December 2016 - 08:55 AM
Nice discrete math class.Posted on 15 December 2016 - 09:42 AM
AlbertEinstein wrote
Thats not the answer ;)
Posted on 15 December 2016 - 09:47 AM
Are these just questions or homework?Posted on 15 December 2016 - 09:49 AM
Radioactivebeans wrote
Questions
Last edited on 15 December 2016 - 10:04 AM by Radioactivebeans
Purpkey wrote
Radioactivebeans wrote...
Questions
Is the first one 23598993600?
And third one 1058400?
Posted on 15 December 2016 - 10:05 AM
Radioactivebeans wrote
Purpkey wrote...
Is the first one 23598993600?
And third one 1058400?
Your right on the first one wrong on the third
Last edited on 15 December 2016 - 10:18 AM by Radioactivebeans
Purpkey wrote
Radioactivebeans wrote...
Your right on the first one wrong on the third
I have a little hard time comprehending as I don't study maths in English can it be for example a 2 digit word?
Posted on 15 December 2016 - 10:25 AM
Radioactivebeans wrote
Purpkey wrote...
I have a little hard time comprehending as I don't study maths in English can it be for example a 2 digit letter?
It can not actually be a two digit letter, for example if you take the letters A B C D and find out how man permutations there are with them there are 60. Repetition has more letters than the simple 4 so it would essentially be a higher number. Repition has actually 10 letters so the equation would have to be 10P10 and we have two o's and two I's so it would be (2*2). The next step is (9*8*7*6*5*4*3*2*1) (2*2) = (9*8*7*6*5)/(2*2) since other numbers cancel out. Then you would have 27,360. Then multiply it by ten since thats the number of letters within the words to get 273,600. You would then divide by 4 to get 68,400. That is the answer
Last edited on 15 December 2016 - 10:35 AM by Radioactivebeans
Purpkey wrote
Radioactivebeans wrote...
It can not actually be a two digit letter, for example if you take the letters A B C D and find out how man permutations there are with them there are 60. Repetition has more letters than the simple 4 so it would essentially be a higher number. Repition has actually 10 letters so the equation would have to be 10P10 and we have two o's and two I's so it would be (2*2). The next step is (9*8*7*6*5*4*3*2*1) (2*2) = (9*8*7*6*5)/(2*2) since other numbers cancel out. Then you would have 27,360. Then multiply it by ten since thats the number of letters within the words to get 273,600. You would then divide by 4 to get 68,400. That is the answer
There are 2es
Posted on 15 December 2016 - 10:38 AM
Radioactivebeans wrote
Purpkey wrote...
There are 2es
My mistake, let me correct that. The actual answer is 138,600.
Posted on 15 December 2016 - 10:52 AM
Lampbork wrote
Nope, Radioactive beans got it
Posted on 15 December 2016 - 01:35 PM
Purpkey wrote
AlbertEinstein wrote...
Thats not the answer ;)
Smug little UHC host boy
Posted on 15 December 2016 - 02:17 PM
SuperNeil64 wrote
Purpkey wrote...
Smug little UHC host boy
;D
Posted on 15 December 2016 - 02:31 PM
1. Should just be (30*29*28*27*26*25*24*23) = 235989936000.2. Ternary strings are strings of numbers where each number is either 0, 1, or 2. With length four, you should have 3^4, or 81, total strings. This is gonna get a bit hairy, so I'll write everything out as clearly as possible.
One third, or 27 strings, will start with 1. Of those, 9 will have another 1 immediately after, fulfilling the requirement. Of the 18 that don't, 6 will have a 1 as the third number, and of the 12 who don't, 4 will have it as the fourth. So out of the 27, 19 will fulfill your requirement.
Looking for an even easier way to say this? Out of the strings starting with 1, the odds that they won't have a single additional 1 in the string is (2/3)^3, or 8/27, which conveniently says 8 of the 27 strings won't fulfill the requirement. 19+8=27, which chelps double check my answer.
Now, for the other 54 strings. Of these, another third, 18, will have 1 as the second number. Of those, 6 will have 1 as the third, and of those who don't, 4 will have it as the fourth. This is again verifiable by doing (2/3)^2*18=(4/9)*18=8. and 18-8=6+4=10.
For the final 36 strings which have a 0 or a 2 in both the first and and second slots, only the ones with 1 in both the third and fourth slots can fulfill the requirements, at a chance of 1/9, giving four total strings. We can even write out these strings: 0011, 0211, 2011, 2211.
For the final answer, 19+10+4= 33 total strings.
3. Repetition has 10 letters. This would mean it would have 10! permutations, but it also has 3 sets of double letters, meaning any sets with the same double letters would be indistinguishable, so you divide by 2!^3=8. This comes out to 10*9*7*6*5*4*3*2, or a clean 453600. Your answer for this above is incorrect.
4. Not entirely sure what you're asking here (and I really don't want to do a formal proof on here). But if I'm understanding what you're saying correctly, this is a direct extension of what I did in problem 6 - essentially, for a graph to be finite, you need to have either entirely even vertices or two odd vertices which sum to an even total - but I don't know enough graph theory to be sure of what you mean, or how the situation with a single odd vertex plays out.
5. I'm sure its possible, but I don't really see the point in finding the exact string.
6. This is mainly common sense (and I don't feel like doing a formal proof once again) - but basically, with vertices of even degrees, you enter and exit each vertex the same number of times, creating a Eulerian cycle. If you have vertices with an odd degree, you leave or enter them once more than you do the other. This means you have to designate one as your starting point and the other (if you have two) as your ending point. If you have more than two, you can't designate additional starting/ending points, and you will either "get stuck" in one or never reach it the final time.
Purpkey wrote
Lampbork wrote...
Nope, Radioactive beans got it
This answer is correct, but simply in scientific notation.
Posted on 15 December 2016 - 02:58 PM
Unwise wrote
2. Ternary strings are strings of numbers where each number is either 0, 1, or 2. With length four, you should have 3^4, or 81, total strings. This is gonna get a bit hairy, so I'll write everything out as clearly as possible.
One third, or 27 strings, will start with 1. Of those, 9 will have another 1 immediately after, fulfilling the requirement. Of the 18 that don't, 6 will have a 1 as the third number, and of the 12 who don't, 4 will have it as the fourth. So out of the 27, 19 will fulfill your requirement.
Looking for an even easier way to say this? Out of the strings starting with 1, the odds that they won't have a single additional 1 in the string is (2/3)^3, or 8/27, which conveniently says 8 of the 27 strings won't fulfill the requirement. 19+8=27, which chelps double check my answer.
Now, for the other 54 strings. Of these, another third, 18, will have 1 as the second number. Of those, 6 will have 1 as the third, and of those who don't, 4 will have it as the fourth. This is again verifiable by doing (2/3)^2*18=(4/9)*18=8. and 18-8=6+4=10.
For the final 36 strings which have a 0 or a 2 in both the first and and second slots, only the ones with 1 in both the third and fourth slots can fulfill the requirements, at a chance of 1/9, giving four total strings. We can even write out these strings: 0011, 0211, 2011, 2211.
For the final answer, 19+10+4= 33 total strings.
3. Repetition has 10 letters. This would mean it would have 10! permutations, but it also has 3 sets of double letters, meaning any sets with the same double letters would be indistinguishable, so you divide by 2!^3=8. This comes out to 10*9*7*6*5*4*3*2, or a clean 453600. Your answer for this above is incorrect.
4. Not entirely sure what you're asking here (and I really don't want to do a formal proof on here). But if I'm understanding what you're saying correctly, this is a direct extension of what I did in problem 6 - essentially, for a graph to be finite, you need to have either entirely even vertices or two odd vertices which sum to an even total - but I don't know enough graph theory to be sure of what you mean, or how the situation with a single odd vertex plays out.
5. I'm sure its possible, but I don't really see the point in finding the exact string.
6. This is mainly common sense (and I don't feel like doing a formal proof once again) - but basically, with vertices of even degrees, you enter and exit each vertex the same number of times, creating a Eulerian cycle. If you have vertices with an odd degree, you leave or enter them once more than you do the other. This means you have to designate one as your starting point and the other (if you have two) as your ending point. If you have more than two, you can't designate additional starting/ending points, and you will either "get stuck" in one or never reach it the final time.
Purpkey wrote...
This answer is correct, but simply in scientific notation.