Monday, October 31, 2011

Problem 19 Answer: "Rating Trading, Part 2"

›
We prove the problem NP-complete by reduction to the subset-sum problem. Given an instance of the subset-sum problem, where we have a set A1...

Problem 18 Answer: "Rating Trading"

›
Problem 18A. Create a graph in which each node represents a player, and there is an edge from A to B if and only if B wants the game A has. ...
Friday, March 18, 2011

Problem 17 Solution: "Seeds of Victory"

›
No. The problem is that there are 12 ways of choosing a Final Four with seeds 1,1,2,3, and only one way of choosing a Final Four with seed...
1 comment:
Thursday, February 24, 2011

Problem 16 Solution: "Fall Out Pick Up"

›
(Note: We will identify an object of weight a and value b by the notation [a,b].) (a) and (b). No. Suppose there was an algorithm with compe...
Saturday, February 19, 2011

Problem 15 Solution: "For Science"

›
Specify a bijective mapping that associates each possible ordering with an integer in the range [1,24]. It does not matter how you do this; ...
1 comment:
Wednesday, February 24, 2010

Problem 14 Solution - "Community Events"

›
Suppose there are N attributes - number the attributes from 1 to N. Then define an N-by-N matrix T as follows: The value in the ith row and ...
2 comments:
Monday, February 22, 2010

Problem 13 Solution: "Characteristic Characters"

›
Consider the system with figured characteristics. Suppose there are N total characteristics. We will make the following definitions: Let T b...