In: Advanced Math
A group of k Vikings independently set out to make a new home. Each Viking has a copy of the same map, showing n islands. Each Viking decides to set sail for some random island. If two or more Vikings land on the same island, they have a battle. (No matter how many Vikings land on that island, it counts as one battle.)
(a) How many battles do we expect will occur? (Hint: Fix a single island, what is the probability of no viking ever landing there? What about exactly one viking reaching this island? What is the relationship of these events and there being a fight in the island?)
(b) You should have obtained a closed formula that depends on n and k. For both formulas, consider the cases in which there is only one island on the map. Do your solutions confirm the intuitive answer for this case? What if there’s only one Viking? What answers do you get for 400 Vikings and 100 islands?