Someone fills a 6x6 matrix with the numbers from 1 to 36 first across, then down, like:

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36

Now they ask for volunteers to randomly select numbers. The number selected will be circled and the others in the same row and column will be crossed out. Non-crossed out numbers are selected until no more numbers can be chosen. For example, selecting 8 means that 7, 9, 10, 11, 12, 2, 14, 20, 26, and 32, can no longer be chosen.

When all is said and done, the total of the circled numbers is 111.

Can you prove why this is so?

*To give credit where due, I first saw this on curiousmath.com*

Easy enough.

Label the columns 1,2,3,4,5, and 6

Label the rows 0,6,12,18,24, and 30

Any number in the grid is then the sum of its row and column number.

When the selection process is finished we have 6 numbers, one of which
is in each column and one of which is in each row. Their sum is
necessarily the sum of all 6 column numbers plus all 6 row numbers.

! + 2 + 3 + 4 + 5 + 6 +6 + 12 + 18+ 24 + 30 = 111