1 in 5 Americans

Computer Science Level 5

In this video , Michael Aranda states that "one in 5 Americans either has had bed bugs or knows someone who has." Assume the following about the population of USA:

There are 326,000,000 people in USA.
Each person is equally likely to be infected by bed bugs, and whether someone is infected is independent from whether another person is infected.
Number the people from 0 to 325,999,999. Person $x$ knows person $y$ if and only if $x \equiv y+k \pmod{326,000,000}$ for some $k \in [-250, 250]$ . That is, each person knows all people whose difference in numbers is at most 250, looping between 0 and 325,999,999. As an example, person number 500 knows all people whose number is in the set $\{250, 251, 252, \ldots, 750\}$ , and person number 0 knows all people whose number is in the set $\{325999750, 325999751, \ldots, 325999759, 0, 1, 2, \ldots, 250\}$ .

If the expected number of people infected with bed bugs is $N$ , find $25 \lfloor \frac{N-1}{25} \rfloor$ .

Hint: The answer is between 100,000 and 200,000.

The answer is 145150.

2 solutions

Ivan Koswara
Jul 31, 2017

Let the probability of having bed bugs be $p$ . Since 1 in 5 people know someone with bed bugs (which may be themself), 4 in 5 doesn't. Assuming having bed bugs is independent between people, the probability that someone doesn't know anyone with bed bugs is simply $(1-p)^{501}$ . This must be equal to $0.8$ ; by Wolfram Alpha, we obtain $p \approx 0.0004452971\ldots$ . The expected number of people with bed bugs is then $326000000 \cdot p \approx 145166.8662\ldots$ , which rounds to $\boxed{145150}$ .

Hmm, I'm a little skeptical of this solution. How did you know that this method would work for the given constraint that every person $n$ knows everyone from $n-250$ to $n+250$ ? If I had given a different construction, the number of people infected does change.

Trevor Arashiro - 3 years, 10 months ago

This method works as long as each person knows exactly 501 people (which may include themself). And of course, you can generalize it so each person knows the same constant number of people. The reason it works is because each person is infected independently from another. If infection is not independent (e.g. infection is more likely in rural areas), or if the numbers of known acquaintances are different among people (e.g. more people know each other in office than in farms), then the solution doesn't work and indeed you might need to use simulation.

Let's say $B_n$ is the event that person $n$ is infected, and $K_n$ is the event that person $n$ knows anyone that's infected (which may be themself). In other words, if $S_n$ is the set of people that $n$ knows, then $K_n = \bigcup_{i \in S_n} B_i$ . Then by De Morgan's laws, $\overline{K_n} = \bigcap_{i \in S_n} \overline{B_i}$ , so

$\displaystyle P( \overline{K_n} ) = P \left( \bigcap_{i \in S_n} \overline{B_i} \right)$

But since we assumed $B_p$ 's are all independent, we have

$\displaystyle P( \overline{K_n} ) = \prod_{i \in S_n} P( \overline{B_i} )$

Finally, just plug in $P(\overline{K_n}) = 1 - P(K_n) = 1 - \frac{1}{5} = \frac{4}{5}$ . Call $P(B_i) = p$ , then $P(\overline{B_i}) = 1 - P(B_i) = 1-p$ . Since $|S_n| = 501$ , the RHS becomes $(1-p)^{501}$ . And of course, by linearity of expectation, $N$ is simply $326000000 \cdot p$ , so once we have $p$ , we have $N$ .

Ivan Koswara - 3 years, 10 months ago

Trevor Arashiro
Jul 7, 2017

The full code is posted below.

If your computer can handle it, you could make an array with 326000000 elements and generate N random numbers and see how many people know the infected. However, this method was incredibly slow for me (took 20 mins per simulation). Here is an alternative method that takes 0.1 seconds per simulation (on CS50).

1) generate an array (call it bugArray) of N random numbers, quick sort the array.

2) for all elements in bugArray check bugArray[i]=bugArray[i + 1]

Note: we could just generate random numbers to replace the duplicate elements and then insertion sort the new bugArray, but that actually takes a while. Steps 3-6 are only to speed up this process sort.

3) for each i where step two is true, set duplicatePlaces[k] = i and set duplicateValues[k]= random number() mod 326000000.

4) quick sort duplicateValues

5) insert, in order, each element duplicateValues[k] into bugArray[duplucatePlaces[k]].

6) insertion sort the new bugArray.

7) repeat steps 2-6 until there are no duplicates

Here comes a little math. Remember, bugsArray[2]=10 means that person number 10 has bedbugs and that subject has the 3rd smallest number (since arrays start at 0). For simplicities sake, assume the population of America is 35, 7 people are infected, and each person p knows the 4 people whose numbers are Between p+2 and p-2. If someone knows more than one person with bed bugs, that person only increases the count by 1.

bugArray[0] = 1; bugArray[1]= 7: bugArray[2]=9; bugArray[7]=15; bugArray[4]=19; bugArray[5]=25; bugArray[6]=30.

If a 1 represents someone who has bed bugs or knows someone else with bed bugs, but not both, and a 2 represents an overlap (someone who knows two or more people with bed bugs or has bed bugs and knows someone else with bed bugs), then the subjects, in order, would look like this.

|1-------|7-|9------|15--|19------|25---|30

11101122211011112111101111111111011 < (these last two 1's come from the first infected person).

The total number of people who have bed bugs or know someone who has bedbugs is 31. We get this by multiplying the number of infected people by 5 and subtracting the number of duplicates. 5*7-4=31.

If two infected people's numbers are more than 4 apart there will be no over lap between the two. However, if the difference is less than that, we must subtract the number of overlaps.

I'll leave it as an exercise to the reader to prove that the total number of people who have bed bugs or know someone with bed bugs is given by (this does not include the last element of the bugArray, a couple rules must be added for that one).

$\text{total}=\displaystyle \sum_{i=0}^{\text{number of infected people-1}} \left\{ \begin{array}{c}\text{numKnown}+1, & \text{bugArray[}(i+1)\text{]}-\text{for bugArray[i]}>\text{numKnown}\\ \text{bugArray[}(i+1)\text{]}-\text{bugArray[i]}, & \text{for bugArray[i]}<=\text{numKnown} \end{array} \right\}$

Here, numKnown means the number of people each subjects knows (in the example above, numKnown=4 and in the original problem, numKnown=500).

Hint: shift all the values in the example above 2 right so they become

|1-------|7-|9------|15--|19------|25---|30

11111011222110111121111011111111110 < (these last two 1's come from the first infected person).

After using the above formula, and running many simulations, one can expect to find an answer between 145162 and 145173 infected people. The floor function in the problem causes all answers between 145150 and 145174 to be counted correct.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <cs50.h>
#include <math.h>
#include <time.h>
#include <string.h>
#define population 326000000
#define bugs 145173
#define numKnown 500
#define trials 600

// list of element number of every infected person
int subjList[bugs];
// array to be sorted and first few elements added to subjList
int duplicateArray[500];
// keeps track of where the added numbers are
int missingSpots[1000];

void printline(int count) {
   int i;

   for(i = 0;i <count-1;i++) {
      printf("=");
   }

   printf("=\n");
}
//------------------------------------------------------------------------
void display() {
    int i;
    printf("[");
    // navigate through all items 
    for(i = 0;i<50;i++) {
        printf("%d ", subjList[i]);
        if (i%11 == 0) {
            printf("\n");
        }
    }
   printf("]\n");
}

void swap(int num1, int num2) {
   int temp = subjList[num1];
   subjList[num1] = subjList[num2];
   subjList[num2] = temp;
}

int partition(int left, int right, int pivot) {
   int leftPointer = left - 1;
   int rightPointer = right;

   while(true) {
      while(subjList[++leftPointer] < pivot) {
         //do nothing
      }

      while(rightPointer > 0 && subjList[--rightPointer] > pivot) {
         //do nothing
      }

      if(leftPointer >= rightPointer) {
         break;
      } else {
        swap(leftPointer,rightPointer);
      }
   }
   swap(leftPointer,right);
   return leftPointer;
}

void quickSort(int left, int right) {
   if(right-left <= 0) {
      return;   
   } else {
      int pivot = subjList[right];
      int partitionPoint = partition(left, right, pivot);
      quickSort(left,partitionPoint-1);
      quickSort(partitionPoint+1,right);
   }        
}
//------------------------------------------------------------------------------

void swap2(int num1, int num2) {
   int temp = duplicateArray[num1];
   duplicateArray[num1] = duplicateArray[num2];
   duplicateArray[num2] = temp;
}

int partition2(int left, int right, int pivot) {
   int leftPointer = left - 1;
   int rightPointer = right;

   while(true) {
      while(duplicateArray[++leftPointer] < pivot) {
         //do nothing
      }

      while(rightPointer > 0 && duplicateArray[--rightPointer] > pivot) {
         //do nothing
      }

      if(leftPointer >= rightPointer) {
         break;
      } else {
        swap2(leftPointer,rightPointer);
      }
   }
   swap2(leftPointer,right);
   return leftPointer;
}

void quickSort2(int left, int right) {
   if(right-left <= 0) {
      return;   
   } else {
      int pivot = duplicateArray[right];
      int partitionPoint = partition2(left, right, pivot);
      quickSort2(left,partitionPoint-1);
      quickSort2(partitionPoint+1,right);
   }        
}

//---------------------------------------------------------------------------------------------

void sortTop(int totalDuplicates) {
    int move = 0;
    // dont need to check if element was inserted into last place of subjArray cuz last element there is never deleted
    while (true) {
        move = 0;
        // stop trying to sort if we have moved the new number to the last (or unlikely case, first) place of subjArray
        if (missingSpots[totalDuplicates - 1] == bugs - 1 || missingSpots[totalDuplicates - 1] == 0) {
            return;
        } else if (subjList[missingSpots[totalDuplicates - 1]] > subjList[missingSpots[totalDuplicates - 1] + 1]) {
            // swap the place in the array that has these two numbers because they're in the wrong order
            swap(missingSpots[totalDuplicates - 1], missingSpots[totalDuplicates - 1] + 1);
            missingSpots[totalDuplicates - 1] += 1;
            move = 1;
        } else if (subjList[missingSpots[totalDuplicates - 1]] < subjList[missingSpots[totalDuplicates - 1] - 1]) {
            swap(missingSpots[totalDuplicates - 1], missingSpots[totalDuplicates - 1] - 1);
            missingSpots[totalDuplicates - 1] -= 1;
            move = 1;
        }
        if (move == 0) {
            return;
        }
    }
}

void sortBottom() {
    int move = 0;
    if (missingSpots[0] == 0) {
        if (subjList[0] > subjList[1]) {
            // swap the place in the array that has these two numbers because they're in the wrong order
            swap(0, 1);
            // moves the place of the thing in the missing spots array cuz we just moved it one in the master array
            missingSpots[0] += 1;
            move = 1;
        }
    }
    while (true) {
        move = 0;
        // stop trying to sort if we have moved the new number to the last place of subjArray
        if (missingSpots[0] == 0) {
            return;
        } else if (subjList[missingSpots[0]] > subjList[missingSpots[0] + 1]) {
            // swap the place in the array that has these two numbers because they're in the wrong order
            swap(missingSpots[0], missingSpots[0] + 1);
            missingSpots[0] += 1;
            move = 1;
        } else if (subjList[missingSpots[0]] < subjList[missingSpots[0] - 1]) {
            swap(missingSpots[0], missingSpots[0] - 1);
            missingSpots[0] -= 1;
            move = 1;
        }
        if (move == 0) {
            return;
        }
    }
}

// if two numbers are inserted next to eachother, this method still works
void modifiedBubbleSort(int totalDuplicates) {
    int move = 0;
    // dont need to check if element was inserted into last place of subjArray cuz last element there is never deleted
    while (true) {
        move = 0;
        for (int n = 1; n < totalDuplicates - 1; n++) {
            // stop trying to sort if we have moved the new number to the last (or unlikely case, first) place of subjArray
            if (missingSpots[n] == bugs - 1 || missingSpots[n] == 0) {
                return;
            } else if (subjList[missingSpots[n]] > subjList[missingSpots[n] + 1]) {
                // swap the place in the array that has these two numbers because they're in the wrong order
                swap(missingSpots[n], missingSpots[n] + 1);
                missingSpots[n] += 1;
                move = 1;
            } else if (subjList[missingSpots[n]] < subjList[missingSpots[n] - 1]) {
                swap(missingSpots[n], missingSpots[n] - 1);
                missingSpots[n] -= 1;
                move = 1;
            }
        }
        if (move == 0) {
            return;
        }
    }
}


// checks for duplicates within the master list, replaces them with other random numbers and re-sorts
//************************************* 
void resortAndCheck(int totalDuplicates) {
    // sorts the new list, duplicateArray, which is full of new randoms
    quickSort2(0,totalDuplicates - 1);
    for (int n = 0; n < totalDuplicates; n++) {
        subjList[missingSpots[n]] = duplicateArray[n];
    }
    // here, we only need to call sort top and bottom
    // THESE FUNCTIONS ARE MADE BECAUSE THE COMPUTER CAN'T CHECK THE TOP AND BOTTOM ELEMENTS AGAINST THE ELEMENT ABOVE OR BELOW THEM
    // BECAUSE IT IS OUT OF THE ARRAY'S RANGE.  
    // we don't want to continuously check if every new value is the largest or smallest in the array because that wastes time.  
    // since the new random num list has been sorted, everything between the top and bottom elements will not try to access anything
    // outside the range of the array
    if (totalDuplicates == 1) {
        sortTop(1);
    } else if (totalDuplicates == 2) {
        // puts largest new randomly generated number in right spot in array
        sortTop(2);
        // puts smallest new randomly generated number in right spot in array
        sortBottom();
        // note that sort top must be called here again incase it bumps into sortBottom;
        sortTop(2);
    // must sort everything here
    } else if (totalDuplicates > 2) {
        sortTop(totalDuplicates);
        sortBottom();
        modifiedBubbleSort(totalDuplicates);
        sortTop(totalDuplicates);
        // for bottom value, if it is inserted too low, then it must be moved up.  However, because it is less than the
        // SECOND RANDOMLY generated newly inserted number, which is out of place itself, the sort bottom function will stop.  However,
        // the bottom element still might not be in the right spot.  thus we must recall the function
        sortBottom();
    }
    // display();
    totalDuplicates = 0;
    // checks for duplicates
    for (int k = 0; k < bugs; k++) {
        if (subjList[k] == subjList[(k + 1)%bugs]) {
            missingSpots[totalDuplicates] = k;
            duplicateArray[totalDuplicates] = rand()%population;
            totalDuplicates++;
        }
    }
    if (totalDuplicates == 0) {
        return;
    } else {
        resortAndCheck(totalDuplicates);
    }
}
//***********************************


//int argc, string argv[]

int main() {
    // difference between two infected subject element numbers
    int difference;
    // number of people who have or know someone who has bedbugs
    int total = 0;
    // average % of population who knows someone with bedbugs or has bedbugs
    double runningAverage = 0;
    int totalDuplicates = 0;
    srand(time(NULL));
    for (int j = 1; j <= trials; j++) {

        for (int y = 0; y < 300; y++) {
            duplicateArray[y] = population;
        }
        for (int i = 0; i < bugs; i++) {
            subjList[i] = (int) ((double) rand() / 6.58737315337);
        }
        // sorts list
        quickSort(0, bugs - 1);
        // checks for duplicates and assigns duplicates to duplicate array
        for (int k = 0; k < bugs - 1; k++) {
            if (subjList[k] == subjList[(k + 1)%bugs]) {
                missingSpots[totalDuplicates] = k;
                duplicateArray[totalDuplicates] = rand()%population;
                totalDuplicates++;
            }
        }
        resortAndCheck(totalDuplicates);
         // DO NOT DO THIS FOR THE LAST ARRAY ELEMENT, this totals the number of people who have/know someone who has bedbugs
        for (int k = 0; k < bugs - 1; k++) {
            difference = subjList[k + 1] - subjList[k];
            if (difference > numKnown) {  
                total = total + numKnown + 1;
            } else {
                total = total + difference;
                if (difference <= 0) {
                    printf("error, difference < 0");
                    return 1;
                }
            }
        }
        totalDuplicates = 0;
        // also, this is to add to the total number of people who know someone with bedbugs or have bedbugs themselves.
        if (subjList[bugs - 1] + numKnown < population) {
            total = total + numKnown + 1;
        } else if (subjList[0] + population - subjList[bugs - 1] > numKnown) {
            total = total + numKnown + 1;
        } else {
            total = total + population - subjList[bugs - 1] + subjList[0];
        }
        runningAverage += (double) total / (double) population;
        printf("on this try, total = %i and running average = %f\n", total, runningAverage / (double) j);
        total = 0;
    }
    printf("\n");
    printline(50);
    printline(50);
    printline(50);
    printf("\n\n%f%% of people have or know someone who has bedbugs in a population of %i \n with %i people infected", runningAverage / (double) trials, population, bugs);
    printf(" (%f%% of population or one out of every %f people)\n", (float) bugs / (float) population, (float) population / (float) bugs);
    // printf("if each knows %i people and is known by %i people\n\n", numKnown, numKnown);
}

1 in 5 Americans

The answer is 145150.

2 solutions

0 pending reports