Random Numbers and Sums
Author
Hey,
I was hoping you guys could help me out with this math problem I'm using for a roulette style game.
I've got numbers from 1-16 and I pick 8 of them and sum them up.
The possible sums are from 36-100.
I need a way to check when a number from 1-16 is picked how it affects the sums. As in which sums it eliminates.
So..for example...
16 eliminates 36-43.
16 then 15 eliminates 42-49.
And so on.
I've already implemented the brute force method by I was hoping to get some help figuring out an elegant method. The brute force method envolves storing all 12000+ combinations and looping through them *ouch*.
Thanks,
Paul
I've never considered such a problem before, but this is how I've thinking about it. There aren't any answers, but just an idea.
36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
100 = 16 + 15 + 14 + 13 + 12 + 11 + 10 + 9
Now, consider what happends to the maximum and minimum values for the sum for a single chosen number. That is, suppose you choose 1 of the 8 numbers and then see what the remaining possibilities are.
Chose 16, then the min = 44 and max = 100.
Represent the possibilities like so,
16 | 44, 100
15 | 43, 100
14 | 42, 100
13 | 41, 100
12 | 40, 100
11 | 39, 100
10 | 38, 100
09 | 37, 100
08 | 36, 099
07 | 36, 098
06 | 36, 097
05 | 36, 096
04 | 36, 095
03 | 36, 094
02 | 36, 093
01 | 36, 092
So we see a clear distinction/pattern.
If the number chosen is 11, then the minimum sum will be 39 and the maximum will be 100. And you want to know what sums it eliminates, so you see that it at least eliminates 36-38. To know which other numbers picking 11 will eliminate, just realize that all the other numbers are still in sequence and thus you can get all sums within a value of 1. So 36-38 are the only ones eliminated.
Now consider two sums, apply the same technique and see what pattern comes about.
16, 15 | 42, 100
16, 14 | 41, 100
.
.
.
16, 9 | 46, 100
16, 8 | 45, 99
16, 7 | 44, 98
16, 6 | 43, 97
.
.
.
8, 7 | 36, 96
8, 6 | 36, 95
.
.
.
A similar pattern.
I think you would have the best bet of figuring out which numbers are eliminated after each new number chosen if you order the numbers in sequence. If you pick 15, 3, 12, 13, 7, then order them as 3, 7, 12, 13, 15.
36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
100 = 16 + 15 + 14 + 13 + 12 + 11 + 10 + 9
Now, consider what happends to the maximum and minimum values for the sum for a single chosen number. That is, suppose you choose 1 of the 8 numbers and then see what the remaining possibilities are.
Chose 16, then the min = 44 and max = 100.
Represent the possibilities like so,
16 | 44, 100
15 | 43, 100
14 | 42, 100
13 | 41, 100
12 | 40, 100
11 | 39, 100
10 | 38, 100
09 | 37, 100
08 | 36, 099
07 | 36, 098
06 | 36, 097
05 | 36, 096
04 | 36, 095
03 | 36, 094
02 | 36, 093
01 | 36, 092
So we see a clear distinction/pattern.
If the number chosen is 11, then the minimum sum will be 39 and the maximum will be 100. And you want to know what sums it eliminates, so you see that it at least eliminates 36-38. To know which other numbers picking 11 will eliminate, just realize that all the other numbers are still in sequence and thus you can get all sums within a value of 1. So 36-38 are the only ones eliminated.
Now consider two sums, apply the same technique and see what pattern comes about.
16, 15 | 42, 100
16, 14 | 41, 100
.
.
.
16, 9 | 46, 100
16, 8 | 45, 99
16, 7 | 44, 98
16, 6 | 43, 97
.
.
.
8, 7 | 36, 96
8, 6 | 36, 95
.
.
.
A similar pattern.
I think you would have the best bet of figuring out which numbers are eliminated after each new number chosen if you order the numbers in sequence. If you pick 15, 3, 12, 13, 7, then order them as 3, 7, 12, 13, 15.
Author
That's exactly how I started thinking too. And it works for the first couple of numbers picked. However, later there isn't a linear method anymore. For example, 16 eliminates 36-43, and if you were to pick 8 next it eliminates 100 and 44.
I started with
16+15+13+12+11+10+9=100 and 1+2+3+4+5+6+7+8=36
and figured that if > 8 was picked use the second formula to eliminate numbers, if < 8 use the first formula. I.E. pick 16, compare 16 to 8, there is an 8 difference, so add that to 36, which equals 44 so 36-43 is eliminated. But I'm finding out that it's not always so straight forward.
Paul
I started with
16+15+13+12+11+10+9=100 and 1+2+3+4+5+6+7+8=36
and figured that if > 8 was picked use the second formula to eliminate numbers, if < 8 use the first formula. I.E. pick 16, compare 16 to 8, there is an 8 difference, so add that to 36, which equals 44 so 36-43 is eliminated. But I'm finding out that it's not always so straight forward.
Paul
Here is an idea.
Maintain 4 ordered sets of numbers.
Begin with the sets as follows:
Used = {}
Available = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
Min = {1,2,3,4,5,6,7,8}
Max = {9,10,11,12,13,14,15,16}
Then do the following eight times,
1) Pick a random number, n, from the Available set and move it to the used set.
2) If n is greater than the greatest unused number in the Min set, then replace the greatest number that isn't used in Min with n.
3) Else if n is less than the lowest unused number in the Max set, the replace the lowest unused number with n.
4) Repeat the procedure.
To calculate the totals you can just add all the elements in the min and max sets to find their sums each time, or start with max = 100 and min = 36. Then when you remove an element, subtract it from either sets' sum, and when you add an element, add it to the sets' sum.
I hope it helps.
Maintain 4 ordered sets of numbers.
Begin with the sets as follows:
Used = {}
Available = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
Min = {1,2,3,4,5,6,7,8}
Max = {9,10,11,12,13,14,15,16}
Then do the following eight times,
1) Pick a random number, n, from the Available set and move it to the used set.
2) If n is greater than the greatest unused number in the Min set, then replace the greatest number that isn't used in Min with n.
3) Else if n is less than the lowest unused number in the Max set, the replace the lowest unused number with n.
4) Repeat the procedure.
To calculate the totals you can just add all the elements in the min and max sets to find their sums each time, or start with max = 100 and min = 36. Then when you remove an element, subtract it from either sets' sum, and when you add an element, add it to the sets' sum.
I hope it helps.
Note that the method given only applies to numbers eliminated at either end of the possibilities, and not those in between. The ones in between are much more difficult. It seems that if a number is used, say 7, and if its sibling numbers are still available, then no numbers are eliminated in between since you can basically add by or substract in the sum by replacing with siblings. The problem seems to be when numbers such as 6,7 or 7,8 are used. Since then the adding and substracting using siblings skips numbers.
I don't think this problem has an elegant and simple solution.
Pretend you're left with 4, 7, 9, 13 and that you must choose 2 numbers. Then the sum could be:
11, 13, 16, 17, 20 or 22.
You can see that the sum set has no clear pattern and is not made of intervals...
That makes me think you'll have to handle list of a possibilities.
Now, storing all the combinations of 8 numbers out of 16 is probably not the most effective way to do it.
I would rather try to store a list of the possible sums (i.e. at beginning 65 values: 36 to 100). And every time a number is picked, iterate through the list to see if it's still doable with the numbers left (if not, remove it from the list).
It's not trivial though. I'll let you think about it ;-)
Pretend you're left with 4, 7, 9, 13 and that you must choose 2 numbers. Then the sum could be:
11, 13, 16, 17, 20 or 22.
You can see that the sum set has no clear pattern and is not made of intervals...
That makes me think you'll have to handle list of a possibilities.
Now, storing all the combinations of 8 numbers out of 16 is probably not the most effective way to do it.
I would rather try to store a list of the possible sums (i.e. at beginning 65 values: 36 to 100). And every time a number is picked, iterate through the list to see if it's still doable with the numbers left (if not, remove it from the list).
It's not trivial though. I'll let you think about it ;-)
Interesting problem, though I don't see a direct request for an answer, rather just a subject of interest to try and ingraine yourself with the knowledge of these numbers. So, theres really no answer, but we can come up with some pretty algorythms.
First, lets define our Ks, k1 through k16 as 1 through 16. In fact, lets just drop the ks and use the constants.
Next we have some Xs. x1 through x16.
Now, we know that for each value of x, we either have a 1 or a 0, x E {0, 1}.
So, here are some things that follow.
Sum = x1 + 2*x2 + ... + 16*x16
x1 + x2 + ... + x16 = 8.
On 16 variables that are a binary state, we'd normally have 65536 possible values, but through the magic forcing 8 bits on, we can cut down the possible values. For instance, 0000000000000001 isn't part of this equation. So, I guess this is where you get the number 12870 being how many combinations there are.
Anyways, lets look at what some of these binary combinations would look like.
10101010101010101010 = 1+3+..+15 = 64
01010101010101010101 = 2+4+..+16 = 72
11001100110011001100 = 60
01100110011001100110 = 68
00110011001100110011 = 76
10011001100110011001 = 68
Hrm, we seem to have a bit of a circular pattern going there.
Try this, code a system to generate the 12870 possibilities and then have it report to you how many of these combinations are unique, and then print the frequency of each number. This should give you a fair list of probabilities from which you can weight the rewards of the results of this roulette.
First, lets define our Ks, k1 through k16 as 1 through 16. In fact, lets just drop the ks and use the constants.
Next we have some Xs. x1 through x16.
Now, we know that for each value of x, we either have a 1 or a 0, x E {0, 1}.
So, here are some things that follow.
Sum = x1 + 2*x2 + ... + 16*x16
x1 + x2 + ... + x16 = 8.
On 16 variables that are a binary state, we'd normally have 65536 possible values, but through the magic forcing 8 bits on, we can cut down the possible values. For instance, 0000000000000001 isn't part of this equation. So, I guess this is where you get the number 12870 being how many combinations there are.
Anyways, lets look at what some of these binary combinations would look like.
10101010101010101010 = 1+3+..+15 = 64
01010101010101010101 = 2+4+..+16 = 72
11001100110011001100 = 60
01100110011001100110 = 68
00110011001100110011 = 76
10011001100110011001 = 68
Hrm, we seem to have a bit of a circular pattern going there.
Try this, code a system to generate the 12870 possibilities and then have it report to you how many of these combinations are unique, and then print the frequency of each number. This should give you a fair list of probabilities from which you can weight the rewards of the results of this roulette.
Just a couple of points/thoughts:
1) A brute force solution is fairly trivial and you could store the results for all possible combinations in a tree structure, with eac leaf containing the sum along the path from the root to that leaf. Ensure that the leaves are ordered and then knowing any sequence of digits less than 8 identifies a node below which exists a subtree of all possible sequences having the given prefix.
2) You could approximate the solution by collecting statistics on the frequency of summed values. A conditional probability distribution can be computed offline for partial sequences of length 2,3,4,... etc. So, for length n prefixes, you would have p(sum=n | x1, x2,x3,...,sn),
where the xi are the numbers drawn. You should be able to see that this distribution is determined by the leaves in the subtree under the prefix sequence, as described above.
Personally, I'd just store the brute force solution and perform a tree lookup.
Cheers,
Timkin
1) A brute force solution is fairly trivial and you could store the results for all possible combinations in a tree structure, with eac leaf containing the sum along the path from the root to that leaf. Ensure that the leaves are ordered and then knowing any sequence of digits less than 8 identifies a node below which exists a subtree of all possible sequences having the given prefix.
2) You could approximate the solution by collecting statistics on the frequency of summed values. A conditional probability distribution can be computed offline for partial sequences of length 2,3,4,... etc. So, for length n prefixes, you would have p(sum=n | x1, x2,x3,...,sn),
where the xi are the numbers drawn. You should be able to see that this distribution is determined by the leaves in the subtree under the prefix sequence, as described above.
Personally, I'd just store the brute force solution and perform a tree lookup.
Cheers,
Timkin
Perhaps I'm misunderstanding the problem, but consider this:
Given 8 numbers between 1 and 16, the maximum sum you can obtain is 16*8 = 128 and the minimum you can obtain is 1*8 = 8. When you choose your first number, this range [8, 128] is going to change.
In the event you get a 1, you can still achieve an 8, but 128 is totally out of the question as your max is now [8, 16*7+1=113]. If you choose a 16, you can no longer achieve an 8, but 128 is still game. => [7+16=23, 128].
Consider choosing a number in the middle, say 5. Both 8 and 128 are not achievable, [7*1+5, 7*16+5] = [12, 117].
In general, you can use this as an iterative approach to finding the range after you've chosen x numbers.
So let x be the number of rolls you've completed. Let X be the sum of the rolls up to the current point.
=> you have 8-x rolls remaining and your current range of possible values is [(8-x)+X, 16(8-x)+X]
Given 8 numbers between 1 and 16, the maximum sum you can obtain is 16*8 = 128 and the minimum you can obtain is 1*8 = 8. When you choose your first number, this range [8, 128] is going to change.
In the event you get a 1, you can still achieve an 8, but 128 is totally out of the question as your max is now [8, 16*7+1=113]. If you choose a 16, you can no longer achieve an 8, but 128 is still game. => [7+16=23, 128].
Consider choosing a number in the middle, say 5. Both 8 and 128 are not achievable, [7*1+5, 7*16+5] = [12, 117].
In general, you can use this as an iterative approach to finding the range after you've chosen x numbers.
So let x be the number of rolls you've completed. Let X be the sum of the rolls up to the current point.
=> you have 8-x rolls remaining and your current range of possible values is [(8-x)+X, 16(8-x)+X]
Alright, I wrote a quick program in C to test my thinking...
Heres the output:
So, lets analyze. Minimum value of 36 and maximum of 100. Numbers with the lowest chance of occuring, assuming your method for choosing the bits is evenly distributed, is 36, 37, 99, and 100. The number with the highest chance of occuring seems to be 68. 526 times in 12870 is 4.08%
Well, if I were a betting man, 68 would be the number I'd bet on.
#include <stdlib.h>#include <stdio.h>int bitcount( unsigned int x ){ int n = 0; if (x) do { n++; } while ((x &= x-1)); return(n);}int main( int argc, char ** argv ){ unsigned int spread[256]; int x, y, z; int combinations, sum, min, max; printf( "Init.\n" ); min = max = combinations = sum = 0; for( x=0; x<256; x++ ) spread[x] = 0; printf( "Generating sums.\n" ); for( x=0; x<65536; x++ ) { sum = 0; if ( bitcount(x)==8 ) { combinations += 1; y = x; for ( z=1; z<=16; z++ ) { if ( y&1 ) sum += z; y >>= 1; } if ( (sum>=0)&&(sum<256) ) spread[sum] += 1; } } printf( "Combinations: %i.\n", combinations ); for( x=0; x<256; x++ ) if (spread[x] != 0) { max = x; if (min==0) min=x; } printf( "Summation Spread:\n" ); sum = 0; for( x=min; x<=max; x++ ) { sum += spread[x]; printf( "[%03i]=%03i ", x, spread[x] ); } printf( "\nRandom Ceiling: %i\n", sum );}/* EOF */Heres the output:
Init.Generating sums.Combinations: 12870.Summation Spread:[036]=001 [037]=001 [038]=002 [039]=003 [040]=005 [041]=007[042]=011 [043]=015 [044]=022 [045]=028 [046]=038 [047]=048[048]=063 [049]=077 [050]=097 [051]=116 [052]=141 [053]=164[054]=194 [055]=221 [056]=255 [057]=284 [058]=319 [059]=348[060]=383 [061]=409 [062]=440 [063]=461 [064]=486 [065]=499[066]=515 [067]=519 [068]=526 [069]=519 [070]=515 [071]=499[072]=486 [073]=461 [074]=440 [075]=409 [076]=383 [077]=348[078]=319 [079]=284 [080]=255 [081]=221 [082]=194 [083]=164[084]=141 [085]=116 [086]=097 [087]=077 [088]=063 [089]=048[090]=038 [091]=028 [092]=022 [093]=015 [094]=011 [095]=007[096]=005 [097]=003 [098]=002 [099]=001 [100]=001Random Ceiling: 12870So, lets analyze. Minimum value of 36 and maximum of 100. Numbers with the lowest chance of occuring, assuming your method for choosing the bits is evenly distributed, is 36, 37, 99, and 100. The number with the highest chance of occuring seems to be 68. 526 times in 12870 is 4.08%
Well, if I were a betting man, 68 would be the number I'd bet on.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
