Problem 740

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
CBurkhart
Posts: 3
Joined: Thu Jul 16, 2020 9:55 pm

Problem 740

Post by 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!
Image
amagri
Posts: 7
Joined: Tue May 21, 2019 1:20 pm

Re: Problem 740

Post by 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
Last edited by amagri on Sat Dec 26, 2020 3:10 pm, edited 1 time in total.
CBurkhart
Posts: 3
Joined: Thu Jul 16, 2020 9:55 pm

Re: Problem 740

Post by 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.
Image
amagri
Posts: 7
Joined: Tue May 21, 2019 1:20 pm

Re: Problem 740

Post by amagri »

You are right, they take 2 slips at a time so there is only 1 phase!
User avatar
PurpleBlu3s
Posts: 75
Joined: Mon Sep 19, 2011 6:49 pm

Re: Problem 740

Post by 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.
Image
SohCahDad
Posts: 1
Joined: Fri Jan 01, 2021 6:25 pm

Re: Problem 740

Post by 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
Posts: 493
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 740

Post by 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.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
urimend
Administrator
Posts: 517
Joined: Fri Jul 06, 2018 6:34 pm

Re: Problem 740

Post by urimend »

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