Loading [MathJax]/extensions/TeX/mathchoice.js

Problem #363

Are you my Dad?

Young Jake walked into a bar. There were n men inside the bar, one of whom was Jake's Dad, whom he had never met. He makes a guess on who is his father among the n men and asks him, "Are you my Dad?". If he finds his dad, he returns home with his dad. Otherwise, the man A whom Jake asked takes pity on him. Then, man A guesses from the other n-1 men who might be his dad. The man A takes Jake to his guessed person B and asks him if he is Jake's dad. If the guessed man B is Jake's dad, they go home; otherwise, man B takes Jake from man A and continues to guess who might be Jake's father like man A did.

At the point when the current man who Jake is with makes a guess on a person who has already been checked, Jake leaves the current man, goes back to the bar entry, and again guesses who might be his dad. (Jake will never guess the same person or let any other man guess the same person that has already been checked before.) This process continues until Jake finds his Dad.

What is the expected number of times Jake says, "Are you my Dad?" when n = 400?.

Let M = 10^9 + 7. It can be shown that the answer can be expressed as an irreducible fraction \frac{p}{q}, where p and q are integers and q \not\equiv 0 \pmod{M}.

Output the integer equal to p \cdot q^{-1} \mod M.

Contributed by SHUBHAM KUMAR VERMA

Solved by 7 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.