Problem 740

[CBurkhart]

Am I to understand that q(n) is (number of ways to successfully run the process until the last person and the last person gets their own name)/(number of ways to successfully run the process until the last person).

I've come up with four completely different solutions (including brute force simulation) so far but they are all giving the same wrong answer for q(3).

Thanks!

[amagri]

Following the problem statement, the process fails if the last person gets at least one slip with their own name...

From my understanding, the process may also fail if the (n-1)th person (the one before the last) gets their own name. So I guess that we should also count this occurrence, right?

For instance, with 3 persons: P1 can choose 3, P2 can choose 1, P3 can choose 1, P1 can choose 3.
At this stage, there are 2 slips with the number 2, so P2 can only only get their own name. And so the process fails.

Thank you in advance

[CBurkhart]

Thanks! I misread the problem to be that person 1 chose twice, then person 2 chose twice, etc.

Edit: I actually think it is still ambiguous which way they choose (123123 or 112233), but leaning towards your idea currently. However the phrasing "last person gets at least one slip" wouldn't make sense since in 123123 they would never get two slips with their name. Unless only the last person doesn't perform that check the first time around??

Final edit: I was right the first time, each person chooses twice in a row, however not all outcomes are equally weighted.

[amagri]

You are right, they take 2 slips at a time so there is only 1 phase!

[PurpleBlu3s]

I agree the problem is ambiguously worded. My initial interpretation was the 123123 version, but I see the 112233 version fits better given this statement:

The process will fail if the last person gets at least one slip with their own name.

Perhaps something like this would be clearer?

As before each person takes a random slip from the hat that does not contain their name. The same person repeats this process again so that they end up with two slips neither of which contain their name. Then the next person does the same, and so on.

[SohCahDad]

I think “ambiguously worded” is too kind! The wording is contradictory!!

First:

“As before each person takes a random slip from the hat that does not contain their name. Then they do the same process again so that they end up with two slips neither of which contain their name.”

- which clearly implies 123123.

Then:

“The process will fail if the last person gets at least one slip with their own name”

- which makes no sense with the (only sensible interpretation of the previous bit) 123123 approach as:

(a) 3113 leads to failure before the last person (as person 2 drawing next could only get a 2!) [I see amagri has correctly pointed out the same - thanks!]

(b) “at least one slip” suggests the possibility of the last person getting more than 1 slip with their name on it which shouldn’t happen with the 123123 approach.

Assuming, we are SUPPOSED to go for the 112233 approach, a re-wording is, in my view, definitely required. Perhaps:

“This time, each person takes TWO random slips returning and replacing either or both if they have their own name on. As a result, the last person will be left with two slips and the process will fail if either or both of these slips have the last person’s own name on.”

Or PurpleBlu3s suggestion!

[MuthuVeerappanR]

It takes a simple brute force to verify that the intended process is 112233.

The source of confusion is maybe because of the following words:

“As before each person takes a random slip from the hat that does not contain their name. Then they do the same process again so that they end up with two slips neither of which contain their name.”

The 'they' is used here only because PE wants problems to be gender-neutral. For example something like,

“As before each person takes a random slip from the hat that does not contain his (or her) name. Then he (or she) does the same process again so that he (or she) ends up with two slips neither of which contain his (or her) name.”

would've easily avoided the confusion here. But it really does show how much the Dev team wanted the problem statement to be inclusive.

Also, the first part of the sentence says "... each person takes a random slip...".

I'm all for users wanting the problem to be not-ambiguous, but in case it is, we could post here (in a more courteous way) the doubt to the admins. It may be bit late for them reply and in the mean time, we could write a brute force to clarify it ourselves and then post the clarification here to help others. That would be a much more constructive way IMHO.

[urimend]

Thanks everyone.
The phrasing of the problem has been adjusted to emphasize that each person takes two slips consecutively.