Monday, October 31, 2011

Gaming Math: Problem 18 Answer and Problem 19

The answer to Problem 18, "Rating Trading", has been posted.

Problem 19: Rating Trading, Part 2

Consider the following generalization of the Math Trade Problem, which I came up with while thinking about how to use a similar "math trade" process to trade Magic cards. The difficulty with trading Magic cards using math trades is that Magic cards vary extremely widely in value, so the restriction of one-for-one trades is likely to be prohibitive. Therefore, suppose that we have the following Generalized Math Trade Problem:

Consider a group of N players, each of which has one or more cards to trade. Each player has a separate "subjective value" of each object - i.e. one player might value a given card at $12, while another might value it at only $8. The goal is to redistribute the cards among the players so as to maximize the sum of the amount each player values the cards he ends up with, subject to the constraint that each player ends up with cards that he values at least as much as the cards he started out with.

The "decision problem variation" of the Generalized Math Trade Problem is as follows: given an instance of the Generalized Math Trade Problem and a target value, determine if there is a solution such that the sum of the amount each player values the cards he ends up with is at least the target value (subject to all the other constraints of course).

Problem 19: Show that the decision problem variation of the Generalized Math Trade Problem is NP-complete.

Hints (ROT13 to read; you can read them one at a time)

1. Gur erqhpgvba vf gb gur fhofrg-fhz ceboyrz.
2. Gur fbyhgvba vaibyirf bayl gjb cnegvpvcnagf.
3. Bar bs gur cnegvpvcnagf unf bayl bar vgrz.

And the solution.

1 comment:

Dan Mont said...

Hey Alex, great problems. I will try to focus. But have you thought of sending these to your old math team coach at Montgomery Blair? he might like to use them as practice problems for his team