Bitcoin Forum
December 06, 2016, 06:15:10 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: 0.30 btc bounty: maths help (statistics)  (Read 10513 times)
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 01:56:31 PM
 #1

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).
Once a transaction has 6 confirmations, it is extremely unlikely that an attacker without at least 50% of the network's computation power would be able to reverse it.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481048110
Hero Member
*
Offline Offline

Posts: 1481048110

View Profile Personal Message (Offline)

Ignore
1481048110
Reply with quote  #2

1481048110
Report to moderator
1481048110
Hero Member
*
Offline Offline

Posts: 1481048110

View Profile Personal Message (Offline)

Ignore
1481048110
Reply with quote  #2

1481048110
Report to moderator
1481048110
Hero Member
*
Offline Offline

Posts: 1481048110

View Profile Personal Message (Offline)

Ignore
1481048110
Reply with quote  #2

1481048110
Report to moderator
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
June 07, 2011, 02:22:30 PM
 #2

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
lemonginger
Full Member
***
Offline Offline

Activity: 210


firstbits: 121vnq


View Profile
June 07, 2011, 02:33:49 PM
 #3

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 Offline

Activity: 210


firstbits: 121vnq


View Profile
June 07, 2011, 02:34:19 PM
 #4

also why is this in development section?
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 02:36:53 PM
 #5

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 Smiley

...
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)?
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 02:38:48 PM
 #6

also why is this in development section?

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

Activity: 138


View Profile
June 07, 2011, 03:11:26 PM
 #7

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 Offline

Activity: 1302



View Profile
June 07, 2011, 05:08:12 PM
 #8

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 05:12:26 PM
 #9

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 Offline

Activity: 1302



View Profile
June 07, 2011, 05:45:46 PM
 #10

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 06:00:10 PM
 #11

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 Smiley

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 Offline

Activity: 210


firstbits: 121vnq


View Profile
June 07, 2011, 06:52:10 PM
 #12

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.
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 10:14:39 PM
 #13

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 Offline

Activity: 416


View Profile
June 07, 2011, 10:56:31 PM
 #14

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 Offline

Activity: 1302



View Profile
June 07, 2011, 11:05:15 PM
 #15

Ahh, good point.

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

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 11:32:30 PM
 #16

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? Smiley

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.

untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 07, 2011, 11:37:05 PM
 #17

it'll just be a binomial distribution.

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

Activity: 416


View Profile
June 08, 2011, 02:04:27 AM
 #18


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? Smiley

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
untitlednotepad
Newbie
*
Offline Offline

Activity: 10


View Profile
June 08, 2011, 10:58:26 AM
 #19

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 Offline

Activity: 26


View Profile
June 08, 2011, 06:52:58 PM
 #20

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.
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!