Pop Quiz!

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Pop Quiz!

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 Research1            A,B,C2            B,D,E3            A,C4            A,C,D,E5            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!

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   CB   E   E   D   D   D   D   BC   A   C   A   A   C   C   AD   D   D   C   E   A   E   DE   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.

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

Re: Pop Quiz!

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. Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

Re: Pop Quiz!

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.

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

Re: Pop Quiz!

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.

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

Re: Pop Quiz!

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.  AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

Re: Pop Quiz!

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!

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.