Question

Problem 1. Suppose that we take a random sequence of numbers modulo n. The proba- bility that the first k terms are all distinct is n - 1 п 2 n - (k – 1) P(n, k) = 2 п п п as we saw in class. For this problem, you will want to write a (very short) program to compute this number, but you do not need to submit it this time. (For both parts, you can submit a numerical approximation to the answer.) a) Suppose that n 365. What is the smallest k for which P(365, k) is less than 1/2? (This is the solution to the “birthday problem”: if k people are in a room, there is a greater than 50% chance that two of them have the same lay. b) Suppose that n = 1000. What is the smallest k for which P(1000, k) is less than 1/100?

Answer 1

The smallest value of k for the part a is 23.

The C program for the solving the above problem is:

#include <iostream>
using namespace std;

int main() {
        int n = 365, i = 1;
        float a, total = 1;
        while(total >= (float)1/2) {
                a = (float)(n-i) / n;
                total *= a;
                i += 1;
        }
        cout << i;
}

The sample of the code is:

1 #include <iostream> 2 using namespace std; 3 49 int main() { 5 int n = 365, i = 1; 6 float a, total = 1; 79 while(total >= (float)1/2) { 8 (float)(n-i) / n; 9 total *= a; 10 i += 1; 11 } 12 cout << i; 13-)

The output of the code is:

C:\Users\user\Desktop\Untitled2.exe 23 Process exited after 0.06519 seconds with return value o icPress any key to continue

The smallest value of k for the part b is 95.

The C program for the solving the above problem is:

#include <iostream>
using namespace std;

int main() {
        int n = 1000, i = 1;
        float a, total = 1;
        while(total >= (float)1/100) {
                a = (float)(n-i) / n;
                total *= a;
                i += 1;
        }
        cout << i;
}

The sample of the code is:

6 1 #include <iostream> 2 using namespace std; 3 4 int main() { 5 int n = 1000, i = 1; 6 float a, total = 1; 7 while(total >= (float)1/100) { 8 (float)(n-i) / n; 9 total *= a; 10 11 } 12 cout << i; 13 i += 1;

The output of the code is:

C:\Users\user\Desktop\Untitled2.exe 95 Process exited after 0.06725 seconds with return value o Press any key to continue ...

Comment down if you have any queries regarding the code or understanding. I will help you out as soon as possible.