Pop Quiz!

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Pop Quiz!

Postby quintopia » Thu Mar 13, 2008 7:06 pm UTC

You are given a pop quiz! Surprise! The test gives you the names of five scientists and five lines of research. Each line of research is different and each has only one of the listed scientists working in it. Your job is to draw lines between scientists and lines of research to match them up correctly. Your lines must represent a true function from scientists to lines of research (a complete graph is cheating!).

The problem: You didn't study! Here's all that you can remember:

Code: Select all

Scientist  Possible Lines of Research
1            A,B,C
2            B,D,E
3            A,C
4            A,C,D,E
5            A,C,E


You get one point for every line correctly drawn and lose no points for lines incorrectly drawn (as long you aren't cheating and drawing more than 5 lines, which loses all points instantly). Assume that each of the narrowed down options seems equally likely and give any matching that maximizes your expected score. Give a short proof that no better matching exists.

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

Re: Pop Quiz!

Postby Puck » Thu Mar 13, 2008 7:32 pm UTC

Neat problem! Here's my solution.

Spoiler:
The answer sets that are consistent with what you remember can be enumerated as follows:

Code: Select all

A   B   B   B   B   B   B   C
B   E   E   D   D   D   D   B
C   A   C   A   A   C   C   A
D   D   D   C   E   A   E   D
E   C   A   E   C   E   A   E


So the truth is one of those eight columns - and using the given assumption, each column is equally likely. But, in order to maximize our expected score, we must pick the most likely answer for each question, independent of the others. That is, the expected value for any set of 5 answers is equivalent to the sum of the expected values of each individual answer.

Therefore, the correct set of choices is found simply by picking the most likely choice in each row, resulting in the following mapping:

1 B
2 D
3 A (or C, they are equally likely)
4 D
5 E

This gives an expected score of 22/8 = 2.75 points.

The interesting thing is that this set of choices cannot possibly result in a perfect score - but none of the 8 choices above (nor any other set of choices) produces a higher expected value across all the possible truth sets.
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

User avatar
MFHodge
Posts: 4246
Joined: Thu Apr 19, 2007 6:27 pm UTC
Location: :noitacoL Raleigh, NC
Contact:

Re: Pop Quiz!

Postby MFHodge » Thu Mar 13, 2008 8:31 pm UTC

I like Puck's solution, but I'll toss out mine as a "low-risk" method.

Spoiler:
Draw: 1B, 2B, 2D, 4D, 3(A or C)

This has a minimum return of 2.00, since you can be certain to have the correct number connected to B and D. Expected return is 2.50. In a real life situation, I would probably accept the slightly lower average return in exchange for the garunteed 2.00 or higher.
Image

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

Re: Pop Quiz!

Postby Puck » Thu Mar 13, 2008 8:52 pm UTC

VTHodge wrote:I like Puck's solution, but I'll toss out mine as a "low-risk" method.

Spoiler:
Draw: 1B, 2B, 2D, 4D, 3(A or C)

This has a minimum return of 2.00, since you can be certain to have the correct number connected to B and D. Expected return is 2.50. In a real life situation, I would probably accept the slightly lower average return in exchange for the garunteed 2.00 or higher.


Spoiler:
I suppose upon further review it's open to interpretation, but "a true function from scientists to fields" to me means that each scientist must map to exactly one field; that is, you can't have two different answers for scientist 2 - you would have f(2) = B and f(2) = D at the same time. And, you can't have no answer for scientist 5 (that is, f(5) = undefined).

I conceptualized the problem as a Scantron test - there are 5 questions (the 5 scientists) and for each, you can pick one of the 5 fields. As I said, it's possible this is not what the OP intended, but that's how I read it.

Heh, also, strictly as a matter of choice and personal preference, if I were doing this in real life, I would probably find which of the eight choices that could actually be correct is the most likely, and pick that one - I don't think the perfectionist in me would allow me to put down a set of answers that isn't consistent with itself (or with what I remember for sure).

Given that restriction, I think the best you can do is BDCAE or BDACE, both of which have an expected score of 19/8 = 2.375.
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Pop Quiz!

Postby quintopia » Fri Mar 14, 2008 12:10 am UTC

Your assumption is correct Puck. You can't have the same scientist in two fields. But you can certainly leave some scientist blank, although this is always less than optimal.

User avatar
MFHodge
Posts: 4246
Joined: Thu Apr 19, 2007 6:27 pm UTC
Location: :noitacoL Raleigh, NC
Contact:

Re: Pop Quiz!

Postby MFHodge » Fri Mar 14, 2008 6:11 pm UTC

Of course I knew I was cheating a bit, but I was just trying to follow the limitations at the end that gave a maximum of five lines. I forgot about the requirement that answers be a "true function". I just think that a lot of the fun of logic puzzles is in the bending of rules, and Puck had already given a good non-cheat answer. :wink:
Image

AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

Re: Pop Quiz!

Postby AvalonXQ » Mon Mar 17, 2008 5:03 pm UTC

How does the solution change if there are no limits/rules about the number of different lines or where they can be drawn, but each incorrect line costs you half a point?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Pop Quiz!

Postby Cauchy » Mon Mar 17, 2008 6:04 pm UTC

Using Puck's chart:

Since a correct answer is worth twice as many positive points as an incorrect answer is worth negative points, a line breaks even for expected score if it has at least a 1-in-3 chance of being correct, which means that at least three of the eight possibilities Puck listed have to have the letter in the appropriate spot.

With this, we see that we want to connect B to the first spot, D to the second, each of A and C to the third, D to the fourth, and E to the fifth. This is worth (1/8)(6 - (1/2)(2) + 4 - (1/2)(4) + 4 - (1/2)4 + 4 - (1/2)4 + 4 - (1/2)4 + 4 - (1/2)4) = (1/8)(15) = 15/8.

As far as security goes, you're guaranteed three answers by this method and can't get more than four, so you'll score at least 1.5 and won't score more than 3.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 4 guests