Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Pigeonhole Principle In a certain roleplaying game, the hero is tasked with invading a village of goblins, to slay as many goblins as they can.
Pigeonhole Principle In a certain roleplaying game, the hero is tasked with invading a village of goblins, to slay as many goblins as they can. Each goblin has a health total called hit points (HP), which is a positive integer value. Goblins can have HP as low as 2, for the lowly salt goblins, up to 111, for the mighty goblin lords. A goblin can have any amount of HP between 2 and 111, inclusive. For the following parts, you may not just cite the pigeonhole principle and must write a complete proof of the statements. (a) Goblins are considered to be in the same family if they have the same amount of HP, and a family of goblins is any collection of goblins that are all in the same family. Thinking they are very dark and edgy, the hero slays 666 goblins. Prove that the hero has slain at least 7 goblins that were in the same family. (b) Goblins are considered to be friends with each other if their HP is not coprime (i.e. their HP values share a divisor or factor that is greater than 1). For example, a goblin with 15HP is friends with a goblin with 70HP, since 15 and 70 share a factor of 5 , while a goblin with 35HP is not friends with a goblin with 38HP, since 35 and 38 are coprime. The hero, having already slain families of goblins decides they do not want to slay goblins that are friends. They decide on conservatively only slaying 30 goblins. "There's no way that any of these goblins were friends" thought the hero. The hero was wrong, at least one pair of those goblins were friends, and the hero is bad at math. Prove that if 30 goblins are slain, at least 2 of those slain goblins were friends. (Hint: Consider prime numbers and prime factors) (c) The hero continues this for months, slaying countless goblins, only to find that the adventuring guild they worked for was corrupt and only wanted the goblins gone so that they can build a Champ Guild Mega Guild location in place of the goblin village. Having been used for Land Development and wracked with guilt, the hero devotes their energy instead to magically reviving the slain goblins and restoring the goblin village to its former glory. They decide to start by reviving enough goblins so they are guaranteed to have revived at least 10 goblins that all belong to the same goblin family, but they have no idea which goblins were in families in the first place. How many goblins does the hero have to revive to guarantee that they have revived at least 10 goblins that belong to the same goblin family? Explain your reasoning
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started