- 21 Jun '03 19:07 / 1 editNOTE: THis is the first in a series of puzzles I've invented that feature RHP personalities. Enjoy.

Acolyte has decided to avoid the fate of the destitute student, and find gainful employment. His area of expertise being Answer Prancing, he heads down to Ans., Prance, & Dance to apply for a job. He joins the ranks of N purple-hose clad prancer hopefuls () awaiting interview. Now, the hiring officer has objective criteria such that given two candidates, the superior Answer Prancer can always be certainly determined. Hte hiring officer follows a very efficient strategy. He picks some M<N, rejects the first M candidates in line, and then hires the first interviewee after that who is better than ALL of his predecessors. This can be shown to be the strategy that maximizes his chances of hiring the best Prancer, under certain circumstances. The questions are:

1. What value of M, in terms of N, should the officer use to maximize the probability of getting the best candidate?

2. If he picks the correct M, what is the probability he picks the best prospective Prancer?

3. Acolyte, who is a skilled mathematician, wants to maximize his chances of getting a job. He is confident of his prancing skills, but does not know if he is the best. In what position in the line should he stand? - 22 Jun '03 09:43

What does the hiring officer do if the best candidate is one of the first M? Surely this would mean that none of the remaining N-M candidates would be better than all their predecessors.*Originally posted by royalchicken***NOTE: THis is the first in a series of puzzles I've invented that feature RHP personalities. Enjoy.**

Acolyte has decided to avoid the fate of the destitute student, and find gainful employment. His area of expertise being Answer Prancing, he heads down to Ans., Prance, & Dance to apply for a job. He joins the ranks of N purple-hose clad prancer h ...[text shortened]... cing skills, but does not know if he is the best. In what position in the line should he stand?

Also, is it fair to assume that 'better than' is transitive (ie if A is better than B and B is better than C, then A is better than C)? - 22 Jun '03 16:58

Ah. By "better than all predecessors", I mean "better than all previously intervied, i.e all that were not rejected out of hand." THere is a chance the best on wll be rejected, but say, for example, the 9th-best is the second-best among the remaining N_M, but the 8th-best occurs after he does. THen the 9th-best gets the job.*Originally posted by Acolyte***What does the hiring officer do if the best candidate is one of the first M? Surely this would mean that none of the remaining N-M candidates would be better than all their predecessors.**

Also, is it fair to assume that 'better than' is transitive (ie if A is better than B and B is better than C, then A is better than C)?

'better than' is a transitive relation.

This puzzle has a quite counterintuitive answer, but by using the proper value of M, the officer can get fairly good results. - 22 Jun '03 20:42

The way I've understood this problem, the hiring officer is going to evaluate M-1 candidates, where the best fitted prancer of them always is chosen.*Originally posted by royalchicken***1. What value of M, in terms of N, should the officer use to maximize the probability of getting the best candidate?**

2. If he picks the correct M, what is the probability he picks the best prospective Prancer?

3. Acolyte, who is a skilled mathematician, wants to maximize his chances of getting a job. He is confident of his prancing skills, but does not know if he is the best. In what position in the line should he stand?

1. The officer would be able to find the best fitted prancer in all cases if he interviewed them all. (It wouldn't be very efficient, however it seems not to be of importance in this case.)

Therefore M should be equal to 0 => M = 0N

2. If he chooses to interview them all, as outlined in 1., the officer will be certain to always find the best prancer.

Therefore P = 1

3. Since the officer would choose to interview them all, and the best prancer interviewed would always be picked, it would not matter where Acolyte is positioned in the queue.

On second thoughts ... I guess there's an obvious piece of information I've missed. - 22 Jun '03 21:17

Humm. The probability could be as high as 1, but that wouldn't be very efficient. It would be very efficient, though, if one would interview just the last person in the queue. The probability would in that case be as low as P = 1/N*Originally posted by royalchicken***I perhaps expressed myself wrong or unclearly. He is going for the best probability of getting the Paramount Prancer while minimizing the number of interviews.**

I can see the pros and cons with each option. But I fail to see how the `correct' value of M can be determined.

Also, congrats with your 1000th-post-to-be. - 22 Jun '03 22:18The probability for picking out the correct prancer:

P = (N - M)/N

After rearranging we get:

M = N - NP

It is possible to get the probability as high as P = 1 (shown in a previous post):

M = N - N*1 = 0

Ack. There must be a fundamental error in there somewhere! I'll just sit down waiting for anyone else to come up with a suggestion. - 23 Jun '03 01:03 / 2 edits

Does that mean that if the second person interviewed is better fitted than the first, he will be automaticly hired? (Even if the prancer best suited at is at the end of the queue?)*Originally posted by royalchicken***He picks some M less than N, rejects the first M candidates in line, and then hires the first interviewee after that who is better than ALL of his predecessors.**

If so, please disreagard everything I've said earlier. - 23 Jun '03 16:27Yes, basically. It goes like this: The first M are rejected. He then starts interviewing the remaining candidates as they are placedin line. As soon as he finds one, say, for example, the second best of all of them, who is better than all those interviewed before him, he hires him, even if, for example, the absolute best was the next man in line.

Hint: The best M is not a rational number. - 24 Jun '03 21:52

Surely then he will always pick the first person he interviews, as they are trivially better than everyone interviewed before them.*Originally posted by royalchicken***Yes, basically. It goes like this: The first M are rejected. He then starts interviewing the remaining candidates as they are placedin line. As soon as he finds one, say, for example, the second best of all of them, who is better than all those interviewed before him, he hires him, even if, for example, the absolute best was the next man in line.**

Hint: The best M is not a rational number. - 25 Jun '03 09:50 / 2 editsIn that case, isn't the M+1th person is a kind of benchmark, in that the first person who is better than him will get the job? What does the hiring officer do if none of the remaining candidates are better than the M+1th person? I still don't understand the merits of this strategy.

Also, could you give me the objective function that the hiring officer is trying to maximise? It can't be as simple as 'probability of best candidate being selected', because then he would just interview everyone so he could be sure of finding the best one.