I already gave you one problem about algorithms, so it's time to give you a problem related to what I am studying in the other class I am taking this semester - combinatorics.
Problem 7: By Our Powers Combined
In the Xbox 360 game "Marvel: Ultimate Alliance 2," the player controls a team of superheroes as they battle evil. One of the key weapons in this fight is "Fusion" attacks, which are special attacks that combine two heroes' superpowers. Each pair of heroes has a Fusion attack., and when the player chooses to use a Fusion attack he chooses which two heroes to do the attack with. (For example, a team of 4 would have 6 different possible pairings of heroes and thus 6 different Fusion attacks.) There are three types of Fusion attacks: "Targeted," which are attacks that do a lot of damage to a single target (useful for fighting bosses), "Clearing", which attack all enemies in a wide area (useful for clearing out large groups of enemies), and "Guided", which allows the player to steer the attack after it fires to sweep up as many enemies as possible in the attack.
Since every pair of heroes has a Fusion attack, this situation can be represented as a complete graph with the vertices representing heroes, the edges representing pairs of heroes, and each edge labeled with what kind of Fusion attack that pair has.
There are 24 heroes in the game, and the player can bring 4 of them into battle at a time. Show that it is not possible to assign Fusion types to pairs of heroes in such a way that no matter what team of 4 the player chooses, he will always have at least one of each kind of Fusion attack available.
Major Hint: If there were only 6 heroes in the game, teams only consisted of 3 heroes, and there were only two types of fusions, then the problem would be the special case of Ramsey's theorem described in the first "Example" in the link, and there would be no way to do it. You may use this result in solving the problem, and the technique used to solve the problem is very similar to the technique used in proving that result.
The solution is here.
Subscribe to:
Post Comments (Atom)
2 comments:
This was a very cool problem, that I would have made no headway on without your hint.
Do you know about Ramsey? He was a brilliant mathematician that died very young. Many people think if he had lived a normal lifespan he would have proved a lot of amazing theorems.
We want some more posts! ;-)
Post a Comment