I've been racking my brain over this problem which I was hoping to use basic probability and combinatorics. I cannot seem to find a similar solution to a sufficiently similar question either (though I am sure one exists somewhere).
The problem is as follows:
Let's say I have 25 boxes.
There are 5 boxes lablled A, 5 labelled B, 5 labelled C, 5 labelled D and 5 labelled E. I also have 25 balls of five different colours - 5 blue, 5 green, 5 red, 5 yellow and 5 purple. Balls are then randomly placed into a box (the box has no capacity constraints).
A matrix is then created of the box letter and the number of balls of each colour (i.e., a 5 x 5 matrix). The columns of the matrix are rearranged in a way that maximises the sum of the entries of the matrix on the main diagonal (note: there may be a better way of rearranging the matrix to obtain the highest accuracy, but I would like to keep it reasonably simple for now).
Note: @kodlu has kindly offered a much better term for this - maximising the trace of the matrix
Accuracy is then calculated as the sum of this diagonal divided by the sum of the elements in the matrix (i.e., 25).
What is the expected value of the accuracy (and by extension, what is the expected value of the accuracy with n^2 boxes and n colours of balls)?
So far, my solution relies on the (incorrect) assumption that there are 5 balls in each box (which would make for a relatively straightforward binomial probability question). However, even in this case, I am not sure how to approach the effects of optimising the matrix.
Any leads / assistance would be greatly appreciated!
Update 1:
To clarify what is meant by rearranging the diagonals, I have the following example (simplified).
| A | B | C | |
|---|---|---|---|
| X | 1 | 0 | 2 |
| Y | 0 | 0 | 3 |
| Z | 3 | 4 | 0 |
Then you could rewrite it as:
| B | C | A | |
|---|---|---|---|
| X | 0 | 2 | 1 |
| Y | 0 | 3 | 0 |
| Z | 4 | 0 | 3 |
In this case, one of the diagonals is (B,Z), (C,Y) and (A,X) which gives a total of 8.