MHP2O - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

ILLUMINATI SEASON 6 Contest

Author: Mann Mehta

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Adhoc, Probability, School Math and Observations

PROBLEM:

You have given N numbers of doors now you have to choose any one door at random. Now there is a magician who open all doors except two doors one which you have choose and another that may or may not contain car. Your task is tell the probability of choosing door 1 and door 2 such that the we find car behind that door.

QUICK EXPLANATION:

This question is motivated from the famous Monty Hall Problem. Basically for generalize N we can find the probability of both door in terms of \frac{P}{Q}.

Finding probability of choosing first door such that car behind that door is trivial example of probability where we know that out of N door exactly behind any one door there is a car then probability of choosing any door among N doors such that car behind that door is \frac{1}{N}. Now after removing all doors except two doors as mention, the probability at which car behind door 2 is very large because initially after removing all ( N - 2 ) doors we know that all car except two of that doesn’t contain a car hence probability of choosing second door can easily prove as ( 1 - \frac{1}{N} ) = ( \frac{N-1}{N} )

Probabaility of choosing first door such that car behind that door is always \frac{1}{N}
Probabaility of choosing second door such that car behind that door is always \frac{N-1}{N}

EXPLANATION:

Monty Hall Paradox -

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car, behind the others, goats. You pick door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

So the answer to this question is "YES". Because using probability we can prove that choosing door 2 provides much better probability of a car behind that door.

Now, we discuss in term of N doors and later see one example to clarify how exactly door 2 is the better option always and having probability much greater then door 1.

See we are having N doors. Now every door have equal probability initially exactly one of the door contain car. So initially all door has a probability of \frac{1}{N} such that car behind that door. Now, you can choose any of door among N doors all have equal chance to have car.

Now after that host or we can say magician open all doors which don’t contain car except two doors one which you already choose and one which may or may not contain a car. Now you have to tell probability of door 2 which is not opened yet. So the probability of door 1 is \frac{1}{N} and overall probability is 1 so with little math we can prove the probability at which door - 2 has a car is ( 1 - \frac{1}{N} ) which is \frac{N-1}{N}.

Now take an example of N = 25

  • Initially all door have equal probability of \frac{1}{25} each.

  • Now suppose you have chose the first door. In believe that the first door contain car note that the probability that chosen door contain a car is \frac{1}{25}.

  • Now magician open all door except the last door or we can say door 2. which is not open yet and it is guarantee that now out of this two doors one of the door must contain a car.

  • Now we can easily see that the door 2 is a better option to choose always because it have high probability compare to door 1. Hence the probability of door 2 such that car behind that door is is \frac{24}{25}.

TIME COMPLEXITY:

  • For each test case the time complexity is O(1) as there is only one print statement per test case.

SOLUTIONS:

Setter's Solution 
/// @author mann2108
/// ILLUMINATI SEASON 6
/// Monty Hall Paradox 2.0 (MHP2O)

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main(){
    FAST_IO
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<1<<" "<<n<<" "<<n-1<<" "<<n<<endl;
    }
}

Share your views, approaches and observations. This is the famous paradox and I believe every mathematician enthusiast must study this concept.

1 Like