I first came across this problem years ago, somewhere online, but the exact source remains elusive:
Split randomly into two subsets and , each containing integers. Put the elements of into increasing order and put the elements of into decreasing order .
Prove that
This is an astonishing result, and on first glance you might be incredulous. Playing with small examples might begin to change your mind, but it stills seems unbelievable.
Incredibly, there is a remarkably simple proof, which I found only recently years are first seeing the problem
In each pair , one number will contribute positively and one negatively to the final sum. It turns out that no matter how you split the initial set, it is always the same numbers that contribute positively, namely the integers , (which will we call large), with the remaining numbers always contributing negatively (which we will call small).
To see why this is true, just observe that any large integers in the set must appear at the back of the tail end of the sequence , whereas any large integers in the set must appear at the front of the sequence , in effect filling the gaps left by the large integers in .
The result of this is that no two large integers are paired with each other, and as every large integer is greater than every small integer, it is always the large integers that contribute positively to the final sum. What is this sum?
Finally, the word ‘magic’ in the title of this post refers to a trick that used this result to stun audiences at a gathering of mathematics enthusiasts I went to last year.
So there you have it – a worthy entrant into The Vault, I think you’ll agree.