# Best score in this puzzle

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column. Score to maximise is just adding all the choices together.

$$*\quad A\quad B\quad C\quad D\quad E$$ $$\alpha\quad 16\quad 16\quad 18\quad 18\quad 18$$ $$\beta\quad 20\quad 18\quad 16\quad 12\quad 10$$ $$\gamma\quad 20\quad 18\quad 18\quad 16\quad 16$$ $$\delta\quad 18\quad 18\quad 16\quad 16\quad 8$$ $$\epsilon\quad 10\quad 12\quad 14\quad 14\quad 14$$

Example: ($^{C}$ means chosen)

$$*\quad A\quad B\quad C\quad D\quad E$$ $$\alpha\quad 16^{C}\quad 16\quad 18\quad 18\quad 18$$ $$\beta\quad 20\quad 18\quad 16\quad 12\quad 10^{C}$$ $$\gamma\quad 20\quad 18^{C}\quad 18\quad 16\quad 16$$ $$\delta\quad 18\quad 18\quad 16^{C}\quad 16\quad 8$$ $$\epsilon\quad 10\quad 12\quad 14\quad 14^{C}\quad 14$$

Gives a score of $16+10+18+16+14=74$

Now there are a few ways to do this, but can firstly, someone actually tell me if $88$ really is the best result, and secondly show me how to do it via graph theory. I think I have done it by graph theory matching myself, and will put up my solution as an answer below.

• en.wikipedia.org/wiki/Hungarian_algorithm – Erick Wong Oct 30 '14 at 10:03
• @ErickWong Doesn't that minimise? – Statisticslove Oct 30 '14 at 10:08
• @Statisticslove If you minimize the matrix with negative numbers, it is the same as maximizing... – 5xum Oct 30 '14 at 10:12
• @5xum Have you looked at the method? That couldn't possibly work...? – Statisticslove Oct 30 '14 at 10:17
• Wikipedia suggests that rather than negating the entries, you just subtract them from a sufficiently large value (such as the maximum entry), which is certainly no less effective and maintains a positive entry table. – DanielV Oct 30 '14 at 10:23

Yes, $88$ is the maximum.

First, a score of $88$ can be attained, e.g., by choosing $\alpha E,\beta A,\gamma C,\delta B,\epsilon D$, for a score of $18+20+18+18+14=88$ (I think there are $6$ ways to get a score of $88$ but that's not important.)

To beat $88$, you would need to make at least $90$, since (for some silly reason) all the entries are even numbers. If you were allowed to take the biggest element from each row, you would get $18+20+20+18+14=90$. But you can't do that, because the two $20$s are in the same column. So $88$ is the maximum, like I said.

Alternatively, you could just run through the $5!=120$ possible selections by hand in a few minutes.

• Yeah that was the rough logic I had, I wasn't sure how to make it perfectly rigorous, thank you. Why is even silly ;P? – Statisticslove Oct 30 '14 at 10:30
• Perhaps "contrived" is a more accurate word than "silly". – DanielV Oct 30 '14 at 10:31
• @DanielV How so? – Statisticslove Oct 30 '14 at 10:33
• @DanielV I intentionally multiplied all entries by $2$ changed rows and then transposed so I could avoid any punishment for posting an assignment question? I don't think I would bother :P – Statisticslove Oct 30 '14 at 10:36
• @DanielV I think your sum overestimates the probability, because you are adding probabilities of non-disjoint events. – bof Oct 30 '14 at 10:45