Open Side Menu Go to the Top
Register
Odds of pairing six questions and answers correctly Odds of pairing six questions and answers correctly

09-06-2016 , 04:12 AM
There are six questions, 1 through 6, and six answers, A through F. I have no idea what the questions or the answers are; I just have to hope to match them up.

I'm guessing there are 6! ways to pair the numbers with the letters. So my chance of picking all of them right is 1/720. Somehow my chance of getting at least five right must also be 1/720 because I can't get five right without getting six right. My chance of getting at least four right is 1/360 because half the time when I get four right I get the fifth right, which means I get the sixth right. I suppose then that the chance of getting exactly four right is also 1/720, since half the time when I get four, I also get six. If I get the first three right, I have a 1/3 chance of getting at least four right, so maybe it stands to reason that I have a 1/120 chance of getting at least three right. When I get the first three right, there is a 1/3 chance I'll miss all of the next three, so my chance of getting exactly three right is 1/360. If I get two right, my chance of getting the next one right is 1/4, so my chance of getting at least two right is 1/30. At this point I can't count in my head the combos of getting all the next ones wrong, so I'm not sure about my chance of getting exactly two right. But I'll continue my pattern to say that my chance of getting at least one right is 1/6, and my chance of getting at least zero right is 6/6. It also follows that my chance of missing them all is 5/6, which can't possibly be right.

Obviously there's some cascading error in my thinking, but I don't know where it is. I'd love to know how to solve this for all cases, but at the very least for the cases of getting at least one right and getting exactly one right.
Odds of pairing six questions and answers correctly Quote
09-06-2016 , 04:43 AM
This is a wonderfully interesting question that comes up around here from time to time. In my experience I have found that it is more fun to find the answer yourself rather than someone just telling you the answer.

The key hint is the concept of a derangement.

With that hint you should be able to derive the answer yourself. If not, I would recommend at least giving it a try and posting what you have done.

I and/or others will be happy to continue to point you in the right direction.

P.S. I think you can probably use google to obtain specific information on this problem or hints as how to solve the general problem of this type.
Odds of pairing six questions and answers correctly Quote
09-06-2016 , 09:50 AM
Quote:
Originally Posted by somigosaden
If I get the first three right, I have a 1/3 chance of getting at least four right
This is the first hole in your reasoning. 1/3 is the chance of, say, the 4th question being right. The chance of the 4th or 5th or 6th question being right is greater.
Odds of pairing six questions and answers correctly Quote
09-06-2016 , 11:28 AM
Nice problem. If you want an answer, you can write a program to solve it by brute force. In R, it suffices just one line:

Code:
table(colSums(t(gtools::permutations(6,6))==1:6))
And the result is (score - number of times you get that score):
Spoiler:

Code:
  0   1   2   3   4   6 
265 264 135  40  15   1
Odds of pairing six questions and answers correctly Quote
09-06-2016 , 12:17 PM
Quote:
Originally Posted by somigosaden
I'd love to know how to solve this for all cases,
And here's another hint: principle of inclusion-exclusion.

Quote:
Originally Posted by nickthegeek
Code:
table(colSums(t(gtools::permutations(6,6))==1:6))
Neat!
Odds of pairing six questions and answers correctly Quote
09-06-2016 , 02:22 PM
Another thing you can try (which is obviously obvious) is to work through a simpler case you can easily do by hand. Like do it for N=4.

For a small case like 4, it is easy to write down all the possibilities. It is easy to derive the overall tally of how many are correct.

Either from working "forwards" or from working "backwards", it is pretty straightforward to derive the expressions for each tally possibility (0,1,2,3,4) in this case.

Once you are confident that you have derived the correct expressions for N=4, then try N=5, or maybe skip directly to N=6.

From there you will have a good handle on the general case.

Anyway, there are many ways to peel this onion!
Odds of pairing six questions and answers correctly Quote
09-06-2016 , 09:39 PM
whosnext: Buzz gave a detailed answer that I am putting into a spoiler below.

Spoiler:


Quote:
Originally Posted by somigosaden
There are six questions, 1 through 6, and six answers, A through F. I have no idea what the questions or the answers are; I just have to hope to match them up.

I'm guessing there are 6! ways to pair the numbers with the letters.
I'm not a mathematician. I appreciate mathematicians. I love mathematicians.

But anyhow, 6! seems right to me. And 6!=720

Quote:
So my chance of picking all of them right is 1/720.
Yes. (I think so too... 1/720 for all of then right).

Quote:
Somehow my chance of getting at least five right must also be 1/720 because I can't get five right without getting six right.
There's no way to get just five of them right. Thus there are 0/720 ways to get exactly five right.

Quote:
My chance of getting at least four right is 1/360
No.

Quote:
because half the time when I get four right I get the fifth right, which means I get the sixth right. I suppose then that the chance of getting exactly four right is also 1/720, since half the time when I get four, I also get six.
I don't think that logic works. I try to just use logic I know works.

To get four right, you must have two wrong. It's like having a row of six marbles, four of them white and two of them black. A white marble represents correct placement while a black marble represents incorrect placement.

To have two black,
if the first marble is black, then there are five ways to have another marble be black. And that's it for the first marble.
if the second marble is black, then there are four ways to have another marble (aside from the first) be black. And that's it for the second marble.
if the third marble is black, then there are three ways to have another marble (aside from the first and second) be black. And that's it for the third marble.
if the fourth marble is black, then there are two ways to have another marble (aside from the first, second and third) be black. And that's it for the fourth marble.
if the fifth marble is black, then there is one ways to have another marble (aside from the first, second, third, and fourth) be black. And that's it for the fifth marble.
We've already counted all the ways the sixth marble can be black.

5+4+3+2+1=15. That's the number of ways 2 marbles can be black. Thus that's the number of ways two answers can be exchanged and thus the number of ways exactly four answers can be correct

Quote:
If I get the first three right, I have a 1/3 chance of getting at least four right, so maybe it stands to reason that I have a 1/120 chance of getting at least three right. When I get the first three right, there is a 1/3 chance I'll miss all of the next three, so my chance of getting exactly three right is 1/360.
I don't think that logic works.

For exactly three answers to be wrong, first we choose the three answers that will be wrong, then choose how many ways they can be wrong. Let's do the second part first. If the order is ABCDEF, and we choose ABC to be wrong, there are six (3!) ways to arrange ABC (ABC, ACB, BCA, BAC, CAB, CBA) but it's immediately obvious there are only two arrangements with all three out of place).
Now we just have to decide how many ways we can arrange three white and three black marbles in a row.
000111
001011
001101
001110
010011
010101
010110
011001
011010
011100
100011
100101
100110
101001
101010
101100
110001
110010
110100
111000
If I counted correctly, there are 20 of these. And each one has exactly three misplaced twice.
So 20*2=40. There are 40 ways to have exactly three misplaced (and thus exactly three correctly placed) answers.

To have two correctly placed, consider again black and white marbles. There are 15 ways to arrange 2 white and 4 black marbles. But now when we look at the four black marbles that are misplaced, think of ABCD. 4!=24 possibilities. Here they all are:

ABCD no
ABDC no
ACBD no
ACDB no
ADBC no
ADCB no
BACD no
BADC yes
BCAD no
BCDA yes
BDAC yes
BDCA no
CABD no
CADB yes
CBAD no
CBDA no
CDAB yes
CDBA yes
DABC yes
DACB no
DBAC no
DBCA no
DCAB yes
DCBA yes
I think that's it. 24, (4!), of those, but only 9 (those marked yes) have all four letters out of sequence.

So again, if I have counted correctly, 15*9=135. That's how many ways to have exactly two correct answers.

There are 720 arrangements possible and we have only accounted for 1+0+15+40+135=191 of them. There are 529 more arrangements. Some of those arrangements have one answer correctly placed and the rest have no answers correctly placed. If we find one, we can subtract from 529 to get the other.

I'll come back to this problem tomorrow. Maybe I'll think of something in the meanwhile. Almost sixty years ago as a junior in college I took a graduate math class for fun. I couldn't solve all the problems on the final exam. Several months after the class was finished, I was digging a ditch and not thinking about the problems on that final exam... and the solution to one of the problems popped into my head! Perhaps I had been subconsciously thinking about the problem all that time. Anyhow, maybe I'll subconsciously think about how to put either exactly one or exactly no answers in the correct place.

Quote:
If I get two right, my chance of getting the next one right is 1/4, so my chance of getting at least two right is 1/30.
I don't think that works.

Quote:
At this point I can't count in my head the combos of getting all the next ones wrong, so I'm not sure about my chance of getting exactly two right. But I'll continue my pattern to say that my chance of getting at least one right is 1/6, and my chance of getting at least zero right is 6/6. It also follows that my chance of missing them all is 5/6, which can't possibly be right.
I agree.

Quote:
Obviously there's some cascading error in my thinking, but I don't know where it is.
I don't know what a cascading error is.

Quote:
I'd love to know how to solve this for all cases, but at the very least for the cases of getting at least one right and getting exactly one right.
nickthegeek got the answers for 6, 5, 4, 3, and 2 correctly placed right. (At least we got the same answers). My guess is he also got 1 and 0 right... but I haven't figured out how to do either yet... maybe tomorrow.

It's a fun problem for me. Thanks.

Buzz


Last edited by whosnext; 09-07-2016 at 12:02 AM. Reason: put into a spoiler
Odds of pairing six questions and answers correctly Quote
09-07-2016 , 05:22 AM
Quote:
Originally Posted by Buzz
Almost sixty years ago as a junior in college
Really impressed!

Back to the problem, as others pointed there is a standard solution even a formula that one can find by googling. This gives the number of ways to get no match at all. It took me some time to solve the case of having exactly 1 match by using PIE but I gave up and used a more intuitive method.

Keeping one of the questions fixed, there are 6 ways to do that, then it's enough to compute the number of ways that there is no match for 5 questions. We can do that by using the textbook method mentioned above, say the result is A ways (in spoiler below) and then 6*A gives the number of ways to get exactly 1 match (out of 6 questions).

Spoiler:
A=44


I wonder how you can do this with PIE - I am thinking of heehaw's similar posts where he plays with the PIE coefficients
Odds of pairing six questions and answers correctly Quote
09-07-2016 , 07:57 AM
Spoiler:
OK. I think I figured out a way to count one item (of six). Kind of tedious, but like I said, I’m not a mathematician.

Assuming 0,1,2,3,4,5 represent the six items, let 5 occupy the sixth position and then count all the possibilities using 0,1,2,3,4. Then go down the list (it will be 120 items long… like I say, kind of tedious… go down the list and identify all those that have none of the five in their proper place. (Marked “yes” in the second column below). However many yeses we have, we could do this six times.

01234 no
01243 no
01324 no
01342 no
01423 no
01432 no
02134 no
02143 no
02314 no
02341 no
02413 no
02431 no
03124 no
03142 no
03214 no
03241 no
03412 no
03421 no
04123 no
04132 no
04213 no
04231 no
04312 no
04321 no
10234 no
10243 no
10324 no
10342 yes
10423 yes
10432 no
12034 no
12043 yes
12304 no
12340 yes
12403 yes
12430 no
13024 no
13042 yes
13204 no
13240 no
13402 yes
13420 yes
14023 yes
14032 no
14203 no
14230 no
14302 yes
14320 yes
20134 no
20143 yes
20314 no
20341 yes
20413 yes
20431 no
21034 no
21043 no
21304 no
21340 no
21403 no
21430 no
23014 no
23041 yes
23104 no
23140 yes
23401 yes
23410 yes
24013 yes
24031 no
24103 yes
24130 no
24301 yes
24310 yes
30124 no
30142 yes
30214 no
30241 no
30412 yes
30421 yes
31024 no
31042 no
31204 no
31240 no
31402 no
31420 no
32014 no
32041 yes
32104 no
32140 yes
32401 yes
32410 yes
34012 yes
34021 yes
34102 yes
34120 yes
34201 no
34210 no
40123 yes
40132 no
40213 no
40231 no
40312 yes
40321 yes
41023 no
41032 no
41203 no
41230 no
41302 no
41320 no
42013 yes
42031 no
42103 yes
42130 no
42301 yes
42310 yes
43012 yes
43021 yes
43102 yes
43120 yes
43201 no
43210 no

There are 44 yeses (meaning for those 44, 5 is in the right place but all the others are not placed in their proper order.

Thus 44*6=264 is the number of ways we could have exactly one answer correct.

And then by inference,
  • 720-1-0-15-40-135-264=265
265 is the number of way no answer is correct.


I see that kapw7 has also responded, but I have not looked at his solution yet. I’ll do that now.

Interesting problem.


Buzz
Odds of pairing six questions and answers correctly Quote
09-07-2016 , 08:05 AM
Quote:
Originally Posted by kapw7
Really impressed!
Shucks. Thanks.

Quote:
Back to the problem, as others pointed there is a standard solution even a formula that one can find by googling. This gives the number of ways to get no match at all. It took me some time to solve the case of having exactly 1 match by using PIE but I gave up and used a more intuitive method.
I don't know what PIE means.

Quote:
Keeping one of the questions fixed, there are 6 ways to do that, then it's enough to compute the number of ways that there is no match for 5 questions.
That's exactly how I did it (independently).

Quote:
We can do that by using the textbook method mentioned above, say the result is A ways (in spoiler below) and then 6*A gives the number of ways to get exactly 1 match (out of 6 questions).
That's how i did it!
Spoiler:
A=44
And that's the result I got!

Thanks.

Buzz

Quote:
I wonder how you can do this with PIE - I am thinking of heehaw's similar posts where he plays with the PIE coefficients
I wonder what PIE means. (No matter, I guess).
Odds of pairing six questions and answers correctly Quote
09-07-2016 , 09:51 AM
Quote:
Originally Posted by Buzz
I wonder what PIE means. (No matter, I guess).
Principle of Inclusion-Exclusion

Quote:
Originally Posted by kapw7
It took me some time to solve the case of having exactly 1 match by using PIE but I gave up
N(1) = N(at least 1) - N(at least 2)

Start with an over-estimated number of ways to get at least one right: 6*5! because there are 6 that could be right, and for each one, the number of ways for it to be right is 5! (all the ways to shuffle the other 5 answers).

How many times does that count the number of ways to get at least 2 right?

Focus on individuals. We counted 5! ways to get #1 right and 5! ways to get #2 right. But the 5! ways for #1 included ways to get #2 right, and vice versa. So we have twice counted the number of ways to get #'s 1 and 2 both right. The same is true of any other pair of questions. We don't want correct pairs counted at all, and since they were counted twice, we will subtract them twice.

But we'll subtract an over-estimated N(at least 2), leaving us too short, and we'll have to add back in the ways to get at least 3 right. And so on.
Odds of pairing six questions and answers correctly Quote
09-07-2016 , 10:35 AM
Wow, very nice replies above. And thanks for not spoiling answers!

I will put a general approach in a spoiler.

Spoiler:
Let N be the total number of objects (N=6 in OP).

Let X be the number of objects that are in the correct "slot" (so X can take values 0,1,2,...,N).

Let T(X;N) be the number of ways you can have X correct out of N objects.

Let C(A,B) be the number of ways you can choose B objects from A objects (C is the Combination)

Let D(Y) be the number of ways you can arrange Y objects in which 0 objects are in the correct slot (D is called the Derangement).

Then, it is clear that:

T(X;N) = C(N,X) * D(N-X)

since if there are X in the correct slots, N-X must be in incorrect slots. There are C(N,X) ways to choose the X out of N to be in correct slots. And D(N-X) ways for the N-X to be in incorrect slots.

There are several different ways to derive the D(Y) Derangement function. Principle of Inclusion-Exclusion is perhaps the most common.

I learned it via a simple recursive relationship. It is fairly straightforward to show that:

D(Y) = (Y-1) * [D(Y-1) + D(Y-2)] where D(0)=1 and D(1)=0.

----------

So, for OP's case of N=6 we have:

T(0;6) = C(6,0) * D(6)
T(1;6) = C(6,1) * D(5)
T(2;6) = C(6,2) * D(4)
T(3;6) = C(6,3) * D(3)
T(4;6) = C(6,4) * D(2)
T(5;6) = C(6,5) * D(1)
T(6;6) = C(6,6) * D(0)

which are easily evaluated.

Odds of pairing six questions and answers correctly Quote
09-07-2016 , 06:30 PM
Thanks everyone for putting so much work into this. So it appears that the chance of getting all of them wrong is very close to 1/e. So I would guess that if I had a million questions and a million answers, my chances of missing them all would be even closer to 1/e. It's not intuitive for me that having a greater N doesn't increase your chances of picking one right (despite the obvious counterbalance that there are more wrong options).
Odds of pairing six questions and answers correctly Quote

      
m