Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In Mario Kart, one "cup" involves 4 races, and after every race each racer gets points awarded based on what place they came in (better rank means more points). After playing it enough I grew curious about the mathematical problem of trying to reason backwards from the final scores to the individual race results - when is it possible and how might one do it?

Formally, the problem goes like this: suppose we have a scoring vector $\mathbf{v}\in\mathbb{Z}^n$ with components that are strictly decreasing with index. There are $r$ permutation matrices $P_1,P_2,\dots,P_r$ that we don't have, but we do have the final score vector $\mathbf{f}=(P_1+P_2+\cdots+P_r)\mathbf{v}$. What conditions on our information - $\mathbf{v},r,\mathbf{f}$ - allow there to be a unique solution, and how might we go about computing them? I imagine if $r$ is small enough compared to $n$ and the scoring vector $\mathbf{v}$ is "sparse" or the components "independent" enough (a fuzzy intuition), there will probably be a unique solution, but it doesn't look at all amenable to linear algebra methods that I know of.

More generally, we could understand the scoring vector to hail from a different type of vector space, or understand the score-distributing matrices $P_i$ to be from a different candidate set than permutation matrices (perhaps from a group representation of something other than the symmetric group?).

share|improve this question
1  
The first thing that came to my mind was this: arxiv.org/PS_cache/arxiv/pdf/0904/0904.3169v1.pdf. It shows that it is hard to reconstruct matrices from their row sums and columns sums, when we allow more than two different "colors" in the matrix. –  utdiscant Oct 21 '11 at 16:00
add comment

1 Answer

It never occurred to me to play Mario Kart in this way :)

One sufficient condition would be to have "maximally independent" values of $v_i$, for example that they are all logarithms of different primes; that way it is easy to reconstruct the full set scores for each player. However this would allow only to reconstruct the sum of the matrices, and not the set of individual matrices $P_i$.

To have unique $P_i$ one obvious requirement is that for any $n \geq 2$ no set of $n$ players can have a set of $n$ scores in common -- for instance if players 3 and 4 both have the scores x and y, then there are at least two ways to construct the $P_i$. In matrix terms, this means that no submatrix of the "sum matrix" can be strictly positive. Perhaps Perron–Frobenius-like results can help from there.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.