Discrete Math

Question 4: Mathematical Induction Part 2 (15 points) . (a) Suppose we consider problem 4 from practice set 5, where n represents the number of viruses in a petri dish. Suppose that the biologist also counts the number of days he/she leave the viruses in the dish. Day 1 corresponds to the first day the virus is placed in the dish, and no reproduction is made. Suppose every day after that (d > 1), at least one virus reproduces. Prove by strong induction on d that the number of viruses in the dish after d days is at most 2d+1 1. Notes: * A single virus reproduces at most once. * A virus can't be 'born and reproduce on the same day (b) A hospital is trying to determine how to efficiently vaccinate n individuals. Currently the individuals are all waiting in the same waiting room. The individuals are not allowed to move, unless instructed by a health care worker. An individual can only be vaccinated once they are placed alone in a waiting room. The health-care workers can perform only the following tasks: A group of n > 2 people can be divided into two non-empty groups and placed into two waiting rooms. This costs $20 for the disinfection of the two rooms. 3 3 If a person is alone in a waiting room, the health care worker can enter and give them a vaccine. This costs $100. Show by induction that the total cost of separating the individuals and vaccinating all of them is exactly $120n $20, regardless of the order of the above two steps. You must assume that the health care worker can separate and vaccine in any order. Question 4: Mathematical Induction Part 2 (15 points) . (a) Suppose we consider problem 4 from practice set 5, where n represents the number of viruses in a petri dish. Suppose that the biologist also counts the number of days he/she leave the viruses in the dish. Day 1 corresponds to the first day the virus is placed in the dish, and no reproduction is made. Suppose every day after that (d > 1), at least one virus reproduces. Prove by strong induction on d that the number of viruses in the dish after d days is at most 2d+1 1. Notes: * A single virus reproduces at most once. * A virus can't be 'born and reproduce on the same day (b) A hospital is trying to determine how to efficiently vaccinate n individuals. Currently the individuals are all waiting in the same waiting room. The individuals are not allowed to move, unless instructed by a health care worker. An individual can only be vaccinated once they are placed alone in a waiting room. The health-care workers can perform only the following tasks: A group of n > 2 people can be divided into two non-empty groups and placed into two waiting rooms. This costs $20 for the disinfection of the two rooms. 3 3 If a person is alone in a waiting room, the health care worker can enter and give them a vaccine. This costs $100. Show by induction that the total cost of separating the individuals and vaccinating all of them is exactly $120n $20, regardless of the order of the above two steps. You must assume that the health care worker can separate and vaccine in any order