Bitcoin Forum
July 20, 2018, 02:15:27 AM
 News: Latest stable version of Bitcoin Core: 0.16.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: 1 2 [All]
 Author Topic: 0.30 btc bounty: maths help (statistics)  (Read 13550 times)
Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 01:56:31 PM

Fact 1:
Alice chooses 6 items from the following list of products:
A1, A2, A3, A4, A5, A6

Fact 2:
Bob chooses 6 items from the following list of products:
B1, B2, B3, B4, B5, B6

Fact 3:
They are free to choose the same product more than once, so for example, Alice might choose to buy the following 6 items:
A1, A1, A2, A2, A2, A6

Fact 4:
Each 'A' product is used with a corresponding 'B' product, so for example, an A5 needs exactly one B5 to be of any use, and a B5 needs exactly one A5 to be useful (Let's call this match a 'complimentary pair').

Questions:

From Bob and Alice's 12 items, what are the chances that:

• They have exactly 1 complimentary pair
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B1, B1, B1, B1, B1)

• They have exactly 2 complimentary pairs
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B1, B1, B1, B1)

• They have exactly 3 complimentary pairs
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B1, B2, B3)

• They have exactly 4 complimentary pairs
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B4, B4, B4)

• They have exactly 5 complimentary pairs
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B4, B5, B2)

• They have exactly 6 complimentary pairs
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B2, B3, B4, B5, B6)

For each correct answer with detailed workings I will give 0.05 btc (~\$1) for a total of 0.30 btc (~\$6).
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
kjj
Legendary

Offline

Activity: 1302
Merit: 1001

 June 07, 2011, 02:22:30 PM

In question 6, for example, would lists A1,A1,A1,A1,A1,A1,B1,B1,B1,B1,B1,B1 be equivalent to A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6 for your purposes?

If so, each party will pick one of 6^6 lists, and the other person's choices don't matter, so the chances are 1 in 6^6.

Moving on to question 5, there are 6^1 ways to pick a list that matches in at least 5 places, but one of them is the answer to #6, so the chances are 1 in 6^5 minus 1/6^6.

In question 4, there are 6^2 ways to pick a list that matches in at least 4 places, but some match more, so we have to remove them again.  So, 1 in 6^4 minus 1/6^5 minus 1/6^6.

Question 3, 6^3 possible, minus the extras, so: 1 in 6^3 minus 1/6^4 minus 1/6^5 minus 1/6^6.

Q2: 1 in 6^2 minus 1/6^3 minus 1/6^4 minus 1/6^5 minus 1/6^6.

Q1: 1 in 6^1 minus 1/6^2 minus 1/6^3 minus 1/6^4 minus 1/6^5 minus 1/6^6.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
lemonginger
Full Member

Offline

Activity: 210
Merit: 100

firstbits: 121vnq

 June 07, 2011, 02:33:49 PM

Wording on this one is a little confusing. Don't let the product thing confuse you. You could just as easily say they each roll a die six times (if I am understanding the wording correctly) . and ask if they have matching numbers.

so for example your first "complementary pair" exercise would be translated from

"They have exactly 1 complimentary pair
(eg, Alice chose A1, A2, A3, A4, A5, A6, Bob chose B1, B1, B1, B1, B1, B1)"

to
Alice rolled [1,2,3,4,5,6] Bob rolled [1,1,1,1,1,1,]

Since all numbers have an equal chance of being rolled, we can think of the problem as A) What are the chances that Alice and Bob each rolled one 1, B) what are the chances that Alice and Bob each rolled 2 ones, C) What are the chances that Alice and Bob each rolled three ones, etc

I don't want to do your homework for ya, even for money (someone else might though!) but this might help you on your way
lemonginger
Full Member

Offline

Activity: 210
Merit: 100

firstbits: 121vnq

 June 07, 2011, 02:34:19 PM

also why is this in development section?
Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 02:36:53 PM

In question 6, for example, would lists A1,A1,A1,A1,A1,A1,B1,B1,B1,B1,B1,B1 be equivalent to A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B5,B6 for your purposes?
yes
If so, each party will pick one of 6^6 lists, and the other person's choices don't matter, so the chances are 1 in 6^6.
sounds correct, give me a few minutes to think about it

...
Q1: 1 in 6^1 minus 1/6^2 minus 1/6^3 minus 1/6^4 minus 1/6^5 minus 1/6^6.

Can you simplify them into a % for me? I don't get how to take that statement and work out the 'chance' that it occurs.

Should P1 be equal to P6 (1 in 46656) or am I just guessing wrong on that (wild guess)?
Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 02:38:48 PM

also why is this in development section?

sorry i don't know where it needs to go
AllYourBase
Full Member

Offline

Activity: 138
Merit: 100

 June 07, 2011, 03:11:26 PM

also why is this in development section?

sorry i don't know where it needs to go

I'd post this in the market place, under the buying subforum, since you're spending bitcoins for a service.
kjj
Legendary

Offline

Activity: 1302
Merit: 1001

 June 07, 2011, 05:08:12 PM

There are 6^6 possible lists for each party.  The second party's list doesn't matter at all.

6^6 = 46656.

One of the lists matches all six in the second list, so that chance is 1 in 6^6 or 1 in 46656 or ~ 0.0021433%.

Six (6^1) of the lists match in at least 5 places, but one was the answer above, so 5 in 46656 or ~ 0.010716%

Thirty six (6^2) of the lists match in at least 4 places, but 5 matched in 5 places, and 1 matched in six, so 30 in 46656 or ~ 0.0643%

Two hundred sixteen (6^3) of the lists match in at least 3 places, but 36 matched more, so 180 in 46656 or ~ 0.3858%

1296 (6^4) of the lists match in at least 2 places, but 216 already matched, so 1080 in 46656 or ~ 2.314%

7776 (6^5) of the lists match in at least 1 place, but 1296 have already matched, so 6480 in 46656 or ~ 13.88889%

I hope that better explains where all the minuses came from in my first post.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 05:12:26 PM

thank you kjj, should i send to your signature address or a different one?

also, for a bonus 0.05, what's the chance that there are no matches?

thanks

edit: i ran the numbers with a lot of data from random.org and after 5831 tries, i got the following ratios, which disagree quite a lot with your figures:

matches   count(matches)   (count(matches)/5831*100)
0   37   0.6345
1   359   6.1567
2   1222   20.9570
3   2099   35.9973
4   1676   28.7429
5   417   7.1514
6   21   0.3601
kjj
Legendary

Offline

Activity: 1302
Merit: 1001

 June 07, 2011, 05:45:46 PM

The chance of no matches is what's left, 38880 out of 46656 (6^5 in 6^6) or ~ 83.333%.

Either your simulation, or your description of the problem is wrong, they don't match.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 06:00:10 PM

The chance of no matches is what's left, 38880 out of 46656 (6^5 in 6^6) or ~ 83.333%.

Either your simulation, or your description of the problem is wrong, they don't match.

or your interpretation of my description

it seems extremely unlikely to me given the description, that 0 matches would occur 83% of the time.

here's a few example rows from the data:

[6,3,6,6,3,4] + [6,3,4,3,6,6] = 6 matches
[1,5,2,6,1,5] + [2,3,5,6,5,1] = 5 matches
[4,2,1,1,5,6] + [1,5,3,3,3,1] = 3 matches
[5,6,3,5,5,1] + [1,2,5,4,3,2] = 3 matches
[4,2,5,2,6,6] + [2,1,1,1,1,3] = 1 match
[3,5,5,4,4,5] + [1,1,6,1,6,2] = 0 matches

i can use random.org all day long but i'd much rather find out the actual mathematical formula.

edit: here's some more...

[1,5,2,6,1,5] + [2,3,5,6,5,1] = 5
[4,2,1,1,5,6] + [1,5,3,3,3,1] = 3
[5,6,3,5,5,1] + [1,2,5,4,3,2] = 3
[5,2,6,2,4,1] + [2,5,5,4,3,6] = 4
[1,2,2,5,6,2] + [1,4,3,6,5,6] = 3
[5,6,3,2,2,4] + [1,3,5,3,2,2] = 4
[2,4,3,6,4,1] + [1,5,2,2,2,6] = 3
[3,1,4,3,1,1] + [5,4,1,4,6,2] = 2
[6,3,3,1,3,3] + [4,1,5,6,1,4] = 2
[3,5,1,2,1,1] + [6,4,3,5,2,2] = 3
[5,4,6,3,2,5] + [4,4,3,3,2,1] = 3
[4,6,4,2,4,5] + [3,3,2,1,5,3] = 2
[4,2,5,2,6,6] + [2,1,1,1,1,3] = 1
[1,4,1,1,6,5] + [5,1,1,1,3,3] = 4
[2,2,6,4,4,1] + [1,6,5,3,2,6] = 3
[2,4,5,4,4,3] + [2,4,4,6,2,4] = 4
[3,3,1,5,3,3] + [2,3,2,5,5,6] = 2
[1,1,3,2,2,6] + [6,4,1,3,2,4] = 4
[5,1,2,6,2,1] + [4,6,2,3,3,6] = 2
[6,6,5,2,3,6] + [2,5,5,3,5,2] = 3
[2,1,6,4,2,4] + [4,1,2,6,5,4] = 5
[1,2,5,2,6,1] + [3,5,3,3,2,3] = 2
[3,5,5,5,5,6] + [5,6,6,6,5,1] = 3
[5,2,3,2,4,4] + [4,5,4,1,1,1] = 3
[6,1,5,2,1,4] + [3,3,5,3,3,2] = 2
[1,2,5,6,4,1] + [2,2,5,1,4,3] = 4
[6,2,6,2,3,6] + [3,6,3,1,2,3] = 3
[3,4,2,6,5,1] + [2,6,4,6,6,4] = 3
[6,6,2,2,6,4] + [2,5,5,4,4,3] = 2
[5,4,6,1,4,3] + [6,2,5,3,5,1] = 4
[3,2,4,5,2,2] + [1,5,6,6,3,4] = 3
[1,3,4,1,2,3] + [6,2,6,6,1,4] = 3
[4,1,4,5,4,3] + [5,4,4,6,1,6] = 4
[4,2,4,6,4,5] + [3,2,4,4,6,1] = 4
[6,3,4,6,2,3] + [3,5,1,2,3,4] = 4
[3,5,5,4,4,5] + [1,1,6,1,6,2] = 0
[3,5,1,4,6,1] + [2,3,2,4,3,2] = 2
[6,6,6,4,6,3] + [4,5,6,6,5,6] = 4
[3,2,3,3,6,4] + [3,2,5,6,5,5] = 3
[5,2,6,1,1,1] + [5,6,3,4,3,3] = 2
[3,1,6,6,5,4] + [1,1,1,3,4,5] = 4
[6,5,2,1,2,3] + [6,1,4,1,3,2] = 4
[5,3,4,3,4,4] + [6,6,1,2,5,2] = 1
[5,5,3,4,1,6] + [2,1,1,2,3,2] = 2
[6,5,5,5,1,6] + [4,3,3,6,5,5] = 3
[5,4,3,6,4,2] + [3,2,1,2,1,5] = 3
[2,3,5,1,1,6] + [6,4,5,6,3,2] = 4
[4,6,1,2,6,1] + [2,1,4,4,2,2] = 3
[3,3,1,3,4,1] + [1,4,6,5,4,6] = 2
[4,2,3,5,3,2] + [6,4,4,5,4,6] = 2
[5,2,4,1,6,1] + [6,1,1,2,2,4] = 5
[6,3,4,4,5,5] + [4,2,3,1,4,2] = 3
[5,1,1,1,2,1] + [5,4,6,1,6,5] = 2
[3,4,2,5,4,3] + [4,1,2,3,6,2] = 3
[5,1,5,1,6,3] + [2,1,5,5,5,6] = 4
[6,5,4,3,3,4] + [5,3,4,1,4,1] = 4
[1,3,1,6,6,3] + [1,1,1,4,4,1] = 2
[4,3,4,4,1,2] + [3,6,1,6,1,3] = 2
[5,5,1,1,6,1] + [2,1,1,4,1,2] = 3
[3,6,1,5,1,6] + [2,6,2,6,2,3] = 3
[6,3,5,6,4,5] + [3,1,3,3,1,3] = 1
[6,3,4,3,2,4] + [4,4,4,4,1,3] = 3
[4,2,3,3,5,1] + [5,2,4,6,2,3] = 4
[5,2,1,5,4,2] + [4,3,2,4,6,4] = 2
[6,4,4,3,3,4] + [2,5,4,1,4,5] = 2
[4,2,3,1,4,1] + [1,2,3,5,2,3] = 3
[1,2,4,1,3,3] + [1,6,2,2,3,6] = 3
[1,5,6,5,3,3] + [5,6,5,5,1,4] = 4
[4,5,5,6,1,5] + [4,2,6,4,2,1] = 3
[4,5,3,2,6,6] + [5,4,1,1,6,2] = 4
[1,2,2,5,4,6] + [3,6,2,5,2,1] = 5
[1,2,4,1,5,3] + [3,4,4,1,4,5] = 4
[5,2,5,5,2,1] + [6,2,1,4,3,4] = 2
[4,3,4,1,4,5] + [4,1,3,3,2,1] = 3
[3,1,2,3,2,1] + [1,2,4,1,1,1] = 3
[6,4,5,1,6,4] + [2,6,3,4,5,3] = 3
[4,1,3,5,6,2] + [5,3,1,4,5,4] = 4
[5,5,5,4,4,2] + [5,2,3,3,1,2] = 2
[4,1,5,1,2,5] + [1,5,2,4,4,4] = 4
[5,2,5,2,5,4] + [5,2,5,1,1,5] = 4
[4,3,5,3,4,3] + [1,3,3,4,5,2] = 4
[2,2,4,4,4,4] + [4,2,4,5,6,2] = 4
[4,6,5,3,2,4] + [5,4,5,5,4,6] = 4
[2,1,2,1,2,5] + [4,4,5,1,1,3] = 3
[1,4,6,6,3,6] + [6,5,4,1,4,3] = 4
[5,3,6,2,1,4] + [4,1,6,1,1,6] = 3
[3,2,3,6,3,2] + [6,5,5,4,3,4] = 2
[3,1,5,2,1,1] + [4,3,5,2,2,2] = 3
[4,5,6,2,5,3] + [2,5,4,2,1,3] = 4
[6,6,6,1,4,2] + [2,4,4,5,6,3] = 3
lemonginger
Full Member

Offline

Activity: 210
Merit: 100

firstbits: 121vnq

 June 07, 2011, 06:52:10 PM

yes he is assuming that the numbers have to be in the exact same order. hence the statement (only 1 out of all possible lists matches the other list 6 times). Numbers can match up in any order.
Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 10:14:39 PM

yes he is assuming that the numbers have to be in the exact same order. hence the statement (only 1 out of all possible lists matches the other list 6 times). Numbers can match up in any order.

Thank you for spotting this, I couldn't figure out why his numbers were so different.
ByteCoin
Sr. Member

Offline

Activity: 416
Merit: 250

 June 07, 2011, 10:56:31 PM

matches   count(matches)   (count(matches)/5831*100)
0   37   0.6345
1   359   6.1567
2   1222   20.9570
3   2099   35.9973
4   1676   28.7429
5   417   7.1514
6   21   0.3601

I have solved the problem but the method would be tedious by hand. If it's an academic problem then there's a better way than mine.
No pairs   1 pair   2 pairs   3 pairs   4 pairs   5 pairs   6 pairs
0.61%   5.82%   21.34%   36.45%   27.80%   7.58%   0.41%

kjj's method cannot succeed. If one party chooses 123456 then we must have at least one match whereas if one party chooses 111111 then there's about 1/3 chance of no matches.

This thread should probably be moved to Bitcoin Forum > Economy > Marketplace > Buying

ByteCoin
kjj
Legendary

Offline

Activity: 1302
Merit: 1001

 June 07, 2011, 11:05:15 PM

Ahh, good point.

If order doesn't matter, I'm pretty sure it'll just be a binomial distribution.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 11:32:30 PM

matches   count(matches)   (count(matches)/5831*100)
0   37   0.6345
1   359   6.1567
2   1222   20.9570
3   2099   35.9973
4   1676   28.7429
5   417   7.1514
6   21   0.3601

I have solved the problem but the method would be tedious by hand. If it's an academic problem then there's a better way than mine.
No pairs   1 pair   2 pairs   3 pairs   4 pairs   5 pairs   6 pairs
0.61%   5.82%   21.34%   36.45%   27.80%   7.58%   0.41%

kjj's method cannot succeed. If one party chooses 123456 then we must have at least one match whereas if one party chooses 111111 then there's about 1/3 chance of no matches.

This thread should probably be moved to Bitcoin Forum > Economy > Marketplace > Buying

ByteCoin

thank you bytecoin that is very close to the random data.
to pay the bounty though, i must see how you arrived at your final numbers. did you use a formula or did you write out numbers on a page 46000 times?

i suppose instead of random data i could populate my test table with exactly 1 instance of every combo (46656*46656 records?) and then count the matches, but doing that would assume 'hard-coding' of the number of product variations (6), which i'd rather avoid.

Newbie

Offline

Activity: 10
Merit: 0

 June 07, 2011, 11:37:05 PM

it'll just be a binomial distribution.

i wish i remembered from school what that meant.
ByteCoin
Sr. Member

Offline

Activity: 416
Merit: 250

 June 08, 2011, 02:04:27 AM

thank you bytecoin that is very close to the random data.
to pay the bounty though, i must see how you arrived at your final numbers. did you use a formula or did you write out numbers on a page 46000 times?

Essentially the latter. Do I get the money now?

doing that would assume 'hard-coding' of the number of product variations (6), which i'd rather avoid.
Is this a real world problem you're trying to solve? What is the range of the "product variations" and how much do you care (in BTC)  about an exact answer?

ByteCoin
Newbie

Offline

Activity: 10
Merit: 0

 June 08, 2011, 10:58:26 AM

unfortunately, my spec hasn't really been satisfied yet:

For each correct answer with detailed workings

there's no particular real world example yet, although the dice are a good example IF the number is 6, or i suppose you could think of a 9-sided dice if you wanted to work with 9 numbers.

but this knowledge would be handy for many different purposes and i'm a bit sad that i don't remember any of this stuff from school. i'd like to try to get my head around the math again without resorting to buying some old books and studying it for months. combinations and permutations.
UniverseMan
Newbie

Offline

Activity: 26
Merit: 0

 June 08, 2011, 06:52:58 PM

thank you kjj, should i send to your signature address or a different one?

also, for a bonus 0.05, what's the chance that there are no matches?

thanks

edit: i ran the numbers with a lot of data from random.org and after 5831 tries, i got the following ratios, which disagree quite a lot with your figures:

matches   count(matches)   (count(matches)/5831*100)
0   37   0.6345
1   359   6.1567
2   1222   20.9570
3   2099   35.9973
4   1676   28.7429
5   417   7.1514
6   21   0.3601
I wrote a python code to get a better random sampling that just 5831 iterations.
Code:
from __future__ import division
import random

pairs = [0]*7
iterations = 1000000
for iter in range(iterations):
list = [ [random.randint(1,6) for i in range(6)] for j in 0,1]

equalList = [ [a==b for b in list[1]] for a in list[0] ]

equalCount = 0
truePos = []
for el in equalList:
if len(truePos)>0:
for pos in truePos:
el[pos] = False
if any(el):
equalCount += 1
truePos.append( el.index(True) )

pairs[equalCount] += 1

pct = [str(round(pair/iterations*100,4)) for pair in pairs]
print pct
After running for 1 million iterations it produced the following percents:
matches      count(matches)/1000000*100
0            0.6119
1            5.8219
2            21.3333
3            36.4260
4            27.7966
5            7.6010
6            0.4093

Hopefully this gives us a good check of the solutions we produce.

I'm working on the exact solution now. If you increased the bounty I'd be more inclined to work on it. It may take hours to work out; \$6 is great for a 5 minute problem, but for a 5 hr problem it is less attractive.
lemonginger
Full Member

Offline

Activity: 210
Merit: 100

firstbits: 121vnq

 June 08, 2011, 08:45:49 PM

hours to work out? Come on people this is a permutations 101 question.

ByteCoin
Sr. Member

Offline

Activity: 416
Merit: 250

 June 08, 2011, 10:39:32 PM

 0 _ 738035/120932352 1 _ 586435/10077696 2 _ 4301435/20155392 3 _ 33057475/90699264 4 _ 33616325/120932352 5 _ 1145495/15116544 6 _ 737353/181398528

I don't think it's a particularly easy problem.
An exact formula for the probability of no matches is

6^-12 * Sum_{k=1..6}(6-k)^6 * C(6,k) * Sum_{j=0..k} (-1)^(k-j) * C(k,j) * j^n

where C(a,b)=a!/(b!*(a-b)!)

but this is a simpler case than the other numbers of matches.

Possibly proper mathematicians have more powerful tools to bring to bear on such problems.

Explaining even this simple formula would take quite a lot of work but if you're willing to crack open a maths book then "Stirling numbers of the second kind" would be a good place to start.

ByteCoin
Newbie

Offline

Activity: 10
Merit: 0

 June 09, 2011, 05:44:41 AM

sorry i thought someone who is familiar with this kind of thing might be able to do it easily. i certainly didn't expect it to take 5 hours for the right person (although i admit it might take me 5 weeks to work it out).
kjj
Legendary

Offline

Activity: 1302
Merit: 1001

 November 02, 2012, 06:55:44 PM

Sorry for resurrecting this ancient thread, but I figure it is already in obsolete, so no one will care.

For some reason, I started thinking about this again.  I had forgotten the part about the Stirling numbers, but I had the "well, duh!" moment when I realized that 6^12 is only about 2 billion, and I might maybe be able to find some sort of computing device capable of iterating all of the combinations.

Code:
2176782336 Random Diff Stirling Diff
0   13284630 0.6103% 0.61% -0.0016% 0.6103% 0.0000%
1  126669960 5.8191% 5.82% -0.0028% 5.8191% 0.0000%
2  464554980 21.3414% 21.33% 0.0081% 21.3414% 0.0000%
3  793379400 36.4473% 36.43% 0.0213% 36.4473% 0.0000%
4  605093850 27.7976% 27.80% 0.0010% 27.7976% 0.0000%
5  164951280 7.5778% 7.60% -0.0232% 7.5778% 0.0000%
6    8848236 0.4065% 0.41% -0.0028% 0.4065% 0.0000%

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
 Pages: 1 2 [All]