## 10217 - A Dinner with Schwarzenegger!!!

Moderator: Board moderators

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

### I am always hating this type of problems which express thems

I am always hating this type of problems which express themselves undefined (You just don't know what the problem means until .......). 10217 is the typist one of this type.
I Believe I Can - leestime.com

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

### my idea to clarify the problem compared with dumb dan's

To clarify the problem:

Exactly one person in the ticket queue will win. A person will win if no person in front of him has won AND his/her birthday is the same as ANY one of the people in front of him.

So if there are N days in the year the first person will have a probability p(1)=1/N to win, second person will have probability p(2)=(1-p(1))*(2/N) to win, p(3)=(1-p(1)-p(2))*(3/N) and so on... and you need to find the highest p(x). (Just calculating the values for p will obviously lead to rounding errors for large N, hence the problem).
my idea to clarify the problem compared with dumb dan's:
p(1)=1/N
p(2)=(1-P(1))*(1/N)
p(3)=(1-P(1)-P(2))*(2/N)
..

p(i)=(1-sum(p(1..i-1)))*(i-1)/N

am i right?
I Believe I Can - leestime.com

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

### Re: my idea to clarify the problem compared with dumb dan's

20717TZ wrote:
To clarify the problem:

Exactly one person in the ticket queue will win. A person will win if no person in front of him has won AND his/her birthday is the same as ANY one of the people in front of him.

So if there are N days in the year the first person will have a probability p(1)=1/N to win, second person will have probability p(2)=(1-p(1))*(2/N) to win, p(3)=(1-p(1)-p(2))*(3/N) and so on... and you need to find the highest p(x). (Just calculating the values for p will obviously lead to rounding errors for large N, hence the problem).
my idea to clarify the problem compared with dumb dan's:
p(1)=1/N
p(2)=(1-P(1))*(1/N)
p(3)=(1-P(1)-P(2))*(2/N)
..

p(i)=(1-sum(p(1..i-1)))*(i-1)/N

am i right?
Yes, you are right. But anybody can tell me how is the generalized forumla?
Impossible is Nothing.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
It is so sad that no one give help since I ask for hint half year ago.
This problem confuses me for long time. Actually I have a few copies of other's AC code, but I think it is meaningless to get AC by sending some code that I don't understand the logic.
This problem may be trivial to the people who solved it, but it also confuse many people, as you see there are other people requesting for hint. So, please, anyone who get AC, tell me how to generalize the formula to floating point position. Thanks!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Well, I shouldn't be doing this, since you're still a couple of problems ahead of me , but hey, I'm not a bad guy

Once you accepted the formula p(x) = (1 - sum(1, x-1)) * (x-1)/N, where sum(1, x-1) = p(1) + p(2) + .. p(x-1), you can rearrange:

sum(1, x-1) = 1 - p(x)*N/(x-1).

Now: p(x+1) = (1 - sum(1, x)) * x/N and since sum(1, x) = p(x) + sum(1, x-1), you can work out the recursive formula:

p(x+1) = p(x) * (N/(x-1) - 1) * x/N

Now comes a little "Manzoor Mathemagic":
As long as p(x+1) is increasing with increasing x, the multiplier (N/(x-1) - 1) * x/N will be greater than 1, but as soon as p(x+1) starts decreasing, this multiplier will be smaller than 1.

So when will p(x+1) be at its maximum?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Thanks a lot little joey!!
You explanation is clear and easy to understand.
little joey wrote:Well, I shouldn't be doing this, since you're still a couple of problems ahead of me , but hey, I'm not a bad guy
I would say: Let's go ahead together Our target are Per and Adrain, right?
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
While little joey is correct I'd just like to correct a little typo of his. It's supposed to be:

p(x+1) = p(x) * (N/x - 1) * (x+1)/N

Also, one can note that you get the generalized formula:

p(x) = (N-1)! / (N-x)! * (x/(N^x))

And good luck catching up to Per and Adrian,
you will need it

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
dumb dan wrote:While little joey is correct I'd just like to correct a little typo of his. It's supposed to be:

p(x+1) = p(x) * (N/x - 1) * (x+1)/N
You're right. I could say I left that 'typo' in on purpose to prevent people from dumbly copying a formula (sorry dan, name pun intentional, no offense meant), but I must admit I just made a silly mistake...

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

I just have a quick look on your post and then start doing everything again myself. So I haven't found that you have leave a trap for me (just kidding )
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
So that means every people compare with the ticket seller as well?
And then p(i)=(1-sum(p(1..i-1)))*i/N ?

So my previous idea is wrong?
Impossible is Nothing.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
cytmike wrote:So that means every people compare with the ticket seller as well?
Yes, it is also written in the first post of this thread.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
little joey wrote: So when will p(x+1) be at its maximum?
Thanks for the post, your trick is educating~!

p(x+1) = p(x) * (N/x - 1) * (x+1)/N,

I am guessing that you were looking for the asnwer to be when

(N/x - 1) * (x+1)/N = 1, p(x+1) is maximized??

When if that is true, then p(x) = p(x+1) is just as big, would it not be the case that something in between x and x+1 have even bigger probability? But if that is so, how to we find it with the given formula?

And, since p(x) = p(x+1), then why should we output x and not x+1?

May me I am just totally confused??

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
If someone's birthday matches the birthday of a person who has bought ticket before him, he (the one who bought ticket later) will be given the honor to have dinner with Schwarzenegger. To give the guy at the front of the queue some chance, his birthday will be compared with the ticket seller's birthday.

I think it is quite clearly stated that the seller's birthday is only compared to the first person's birthday.

So, p(1) = 1/N, p(2) = 1/N, p(3) = ((N-1)/N) * (2/N), etc.

But if I do the mathemagic using these conditions I have to output x-1 and floor(x) to get AC, where p(x)=p(x+1), x>1 for sure since N>=30. But why output x-1? The answer, by intuition, should lay in between x and x+1. Right?
Last edited by yiuyuho on Wed Mar 21, 2007 9:26 pm, edited 4 times in total.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
cleared, double posting.