Hints: The 67th Permutation Problem
Answer to Hint 1: After sorting the triple in non-decreasing order, the median is the middle element — it is the second-smallest and also the second-largest among the three.
So each block’s contribution is whichever value ends up “in the middle” once the three numbers are sorted.
What quantity are you effectively trying to maximize across the $n$ blocks?
Answer to Hint 2: You want the sum of those middle elements to be as large as possible, using each integer from $1$ to $3n$ exactly once.
Fix a single block and suppose its three values are the smallest, middle, and largest among that block’s three numbers. Which of those three becomes the median?
Answer to Hint 3: The median is always the value that is neither the minimum nor the maximum among the three — the “middle-sized” one.
So to make a block’s median large, you want that block to contain two relatively large numbers and one relatively small number, with the median being the smaller of the two large ones.
What tension appears when you try to do this for every block at once?
Answer to Hint 4: The small numbers are scarce — each time you “spend” a very small value inside a block, it is no longer available elsewhere. The art is to pair the current largest remaining values with the smallest remaining “filler” values in a disciplined way.
Try building the permutation block by block from the extremes of $\{1,\ldots,3n\}$: which two values from the top of the range and which one from the bottom should share a block if you want the block median to be as large as possible?
Answer to Hint 5: Take the two largest still-unused integers together with the smallest still-unused integer for each block. Arrange the three positions so that, when sorted, the middle value is the second-largest among those three — for example, list them in the order (largest, second-largest, smallest) along the permutation.
Repeat until all numbers are placed.