Let's discuss Mathematics
- Thread starter ParadigmShifter
- Start date
No, at least not directly. That might help indirectly, but I don't know how to use it at the moment for this question. After reading your suggestion, I actually tried to compute with the probability mass function formula, but then recalled I don't have a k=0 case for the binomial distribution. With 7 tribes "n" would equal 7, but then k=number of techs which can't equal any more than 4, when we need cases {0, ..., 7} if n=7. A similar mathematical example is:
Throw a die 7 times. What's the probability that only two of the six numerals on the die appear in the set of 7 throws?
I have a bit better idea now as to how to compute this, but I don't feel sure that I've gotten on the right track here.
This is a game inspired question. I had a space-race game where my 7 opponents only drew 2 of the 4 modern age techs, which I believe rather unlucky. But, I don't really know the probability of that happening, so I don't know if I just have some bias here.
Throw a die 7 times. What's the probability that only two of the six numerals on the die appear in the set of 7 throws?
I have a bit better idea now as to how to compute this, but I don't feel sure that I've gotten on the right track here.
Spoiler :
This is a game inspired question. I had a space-race game where my 7 opponents only drew 2 of the 4 modern age techs, which I believe rather unlucky. But, I don't really know the probability of that happening, so I don't know if I just have some bias here.
It just basic probability theory, combinations & permutations.
The chance of a particular permutation is 0.25^7, there are 4^7 = 16384 possible permutations.
Then just count it up.
Number of ways for all 7 to have tech A = 1, and same for them all to have techs B, C, D. So number of ways for all 7 to produce just one tech is 4/16384
Number of ways for only techs A & B to be covered is a bit trickier. There's 1 A & 6 B's (7 ways), 2 A's & 5 B's (7C2 = 21), 3 & 4 (7C3 = 35), ... 6 & 1 (7C6 = 7) Add that up, and there's 126 ways to get a particular 2 techs. There's 6 combinations of 2 techs, so that's a 756/16384 chance.
Number of ways for 3 techs is going to be just like that for 2, except more of a pain to count. So I'm going to be tricky and use what we worked out already. The number of ways to NOT get tech A is 3^7 = 2187. But of those ways, 3 of them had just one tech, and 6 x 126 = 756 had just two techs. That leaves 1428 ways to have all of techs B, C, D represented. Same deal for leaving out the other 3 techs, so there's 4 x 1428 = 5712 ways to have 3 techs total.
That's 6472 ways covered, which means the other 9912 ways will give you all 4 techs.
So, for 7 tribes drawing from 4 techs, the chances are:
1 tech: 4/16384 = 0.024 %
2 techs: 756/16384 = 4.61 %
3 techs: 5712/16384 = 34.86 %
4 techs: 9912/16384 = 60.5 %
Yep, same working. There's 126 different ways to get a particular two numbers. There's 15 combinations of 2 numbers to get. There's 6^7 = 279936 different ways to roll 7 dice. So your chance is 126 x 15/279936 = 0.675 %
The chance of a particular permutation is 0.25^7, there are 4^7 = 16384 possible permutations.
Then just count it up.
Number of ways for all 7 to have tech A = 1, and same for them all to have techs B, C, D. So number of ways for all 7 to produce just one tech is 4/16384
Number of ways for only techs A & B to be covered is a bit trickier. There's 1 A & 6 B's (7 ways), 2 A's & 5 B's (7C2 = 21), 3 & 4 (7C3 = 35), ... 6 & 1 (7C6 = 7) Add that up, and there's 126 ways to get a particular 2 techs. There's 6 combinations of 2 techs, so that's a 756/16384 chance.
Number of ways for 3 techs is going to be just like that for 2, except more of a pain to count. So I'm going to be tricky and use what we worked out already. The number of ways to NOT get tech A is 3^7 = 2187. But of those ways, 3 of them had just one tech, and 6 x 126 = 756 had just two techs. That leaves 1428 ways to have all of techs B, C, D represented. Same deal for leaving out the other 3 techs, so there's 4 x 1428 = 5712 ways to have 3 techs total.
That's 6472 ways covered, which means the other 9912 ways will give you all 4 techs.
So, for 7 tribes drawing from 4 techs, the chances are:
1 tech: 4/16384 = 0.024 %
2 techs: 756/16384 = 4.61 %
3 techs: 5712/16384 = 34.86 %
4 techs: 9912/16384 = 60.5 %
Yep, same working. There's 126 different ways to get a particular two numbers. There's 15 combinations of 2 numbers to get. There's 6^7 = 279936 different ways to roll 7 dice. So your chance is 126 x 15/279936 = 0.675 %
ParadigmShifter
Random Nonsense Generator
You can probably work it out with the multinomial distribution too
http://en.wikipedia.org/wiki/Multinomial_distribution
http://en.wikipedia.org/wiki/Multinomial_distribution
Thanks Sanabas. I had to reread your explanation a few times, I think I spotted a typo in the numbers, and using numerals for both the tribes and how many times they drew a tech I found confusing, but that helped. Thanks!
IdiotsOpposite
Boom, headshot.
How do we prove that 0<1?
Where's the typo? I didn't exactly double-check any of it.
Bah, never mind, just looked myself. There's 6 combinations of 2 techs, not 12. Didn't even notice when I used the correct 6 x 126 when calculating 3 techs. I'm an idiot. I'll go and edit it now.
ParadigmShifter
Random Nonsense Generator
http://answers.yahoo.com/question/index?qid=20090208193402AAY9ZWH
That doesn't work if 0 and 1 are treated as complex numbers
The best you can do then is |0| < |1|
pboily
fingerlickinmathematickin
PS, the properties outlined in that proof also hold for the ordered sub-field R in C. So you can also show 0<1 even if you consider them both to also be complex numbers.
ParadigmShifter
Random Nonsense Generator
There are infinitely many ordered subfields in C though.
ParadigmShifter
Random Nonsense Generator
Show that (the set of) n-tuples (n dimensional vectors), where n is finite, and the tuple elements come from a countable field set, is also countable.
Just realised this is the proof that there are only countably many algebraic numbers
You can do this by defining 2 functions which when combined give a mapping to N which is unique for each tuple.
Just realised this is the proof that there are only countably many algebraic numbers
You can do this by defining 2 functions which when combined give a mapping to N which is unique for each tuple.
You mean the set of n-tuples with elements in a countable field is countable? That is: F^n is countable if F is.
ParadigmShifter
Random Nonsense Generator
Yes, that is what I mean.
EDIT: F doesn't have to be a field. It could be any countable set.
EDIT2: I suppose I should edit out the word "field" in my post above then
EDIT3: I'm thinking of a number theoretical way to do it. There is probably a method using topology too.
EDIT: F doesn't have to be a field. It could be any countable set.
EDIT2: I suppose I should edit out the word "field" in my post above then
EDIT3: I'm thinking of a number theoretical way to do it. There is probably a method using topology too.
It suffices to prove the assertion for n = 2; the general result follows by induction and since there's an obvious bijection between Fn-1 x F and Fn. Since F is countable, there's a bijection between F and N, so we can assume that F = {1, 2, 3, ...}. We list the elements of F x F as follows:
(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1), (1,5), ...
where we first list all (n,m) such that n + m = 1, then n + m = 2 and so on. Elements that have the same sum are listed in increasing order by the first member of the ordered pair. It is clear that each (n,m) appears in this list exactly once, so we have the required bijection.
Now try this one: Again, let F be a countably infinite set. Define S to be the subset of F x F x F x ... (countably infinitely many products of F) such that (a1, a2, a3, ... ) is an element of S if and only if all but a finite number of the ai are zero. Show that S is countable.
(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1), (1,5), ...
where we first list all (n,m) such that n + m = 1, then n + m = 2 and so on. Elements that have the same sum are listed in increasing order by the first member of the ordered pair. It is clear that each (n,m) appears in this list exactly once, so we have the required bijection.
Now try this one: Again, let F be a countably infinite set. Define S to be the subset of F x F x F x ... (countably infinitely many products of F) such that (a1, a2, a3, ... ) is an element of S if and only if all but a finite number of the ai are zero. Show that S is countable.
ParadigmShifter
Random Nonsense Generator
Can you do my question without induction? I think my answer may answer your question too
I call shenanigans on "if and only if all but a finite number of the ai are zero", since we can replace the ai with ANY (globally) constant value, and swap 0 with the constant, so
I call shenanigans on "if and only if all but a finite number of the ai are zero", since we can replace the ai with ANY (globally) constant value, and swap 0 with the constant, so
In your question, is n a fixed natural number, or does it vary over all natural numbers? My solution was for the first interpretation. If the latter, then our questions are probably equivalent. Does your solution involve unique factorization? I don't understand your final comment.
ParadigmShifter
Random Nonsense Generator
Yep, my answer answers your question.
Again, we can assume that F maps to { 1, 2, ... }. Extend to { 0, 1, 2, ... } by making sure the ai's which are a given constant map to 0. Call this representation Rn, say for the nth F in the cartesian product.
Let Pn be a function which returns the nth prime number.
Map each element of F x F x ... to
PnRn
EDIT: And multiply them together
Any constant element in Rn maps to 0 (so Pn^Rn is 1 and doesn't affect the multiplication result) and we can recover the original values of each F in the cartesian product via the fundamental theorem of arithmetic (by factorisation).
EDIT: This is Godel Numbering BTW. I only realised at lunch it can be used to show there are countably many algebraic integers.
http://en.wikipedia.org/wiki/Gödel_numbering
EDIT2: Clarified a bit
EDIT3: LOL, got P and R the wrong way round, spank me. Fixed.
Again, we can assume that F maps to { 1, 2, ... }. Extend to { 0, 1, 2, ... } by making sure the ai's which are a given constant map to 0. Call this representation Rn, say for the nth F in the cartesian product.
Let Pn be a function which returns the nth prime number.
Map each element of F x F x ... to
PnRn
EDIT: And multiply them together
Any constant element in Rn maps to 0 (so Pn^Rn is 1 and doesn't affect the multiplication result) and we can recover the original values of each F in the cartesian product via the fundamental theorem of arithmetic (by factorisation).
EDIT: This is Godel Numbering BTW. I only realised at lunch it can be used to show there are countably many algebraic integers.
http://en.wikipedia.org/wiki/Gödel_numbering
EDIT2: Clarified a bit
EDIT3: LOL, got P and R the wrong way round, spank me. Fixed.
ParadigmShifter
Random Nonsense Generator
Hmm there's an easy way to extend that proof so that as long as there are only finitely many of the ai's which are not drawn from a set of given values (by mapping to { 0, 1, ..., n } and then mapping the countable set to { n+1, n+2, ... }.
Am I missing something there?
EDIT: Yes I am, since in your question there were countably infinite elements in the cartesian product. You need to map the values of the given constant value to 0 so it has no effect on the infinite product.
My maths head hasn't warmed up yet, I'm only starting my second beer.
Am I missing something there?
EDIT: Yes I am, since in your question there were countably infinite elements in the cartesian product. You need to map the values of the given constant value to 0 so it has no effect on the infinite product.
My maths head hasn't warmed up yet, I'm only starting my second beer.
Anybody aware of any good FREE computer algebra systems? My main requirement at the moment is that it can solve ODEs, but generally being able to do algebra and calculus symbolically would be important. And if I could do simple programming (logical operators, for do loops, arrays etc.) along with basic number theory stuff divisibility, mod, etc. That would be helpful too, I've been using Maple 11 at school, but I want to be able to work on my laptop, and Wolfram Alpha is great, but not really cutting it for some things.
ParadigmShifter
Random Nonsense Generator
Have a look at this:
http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems
I think there's a free C++ library as well but the name escapes me.
http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems
I think there's a free C++ library as well but the name escapes me.
Similar threads
