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 .
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?
So there you have it – a worthy entrant into The Vault, I think you’ll agree.
What is the greatest possible length of a sequence of consecutive positive integers, so that none of the integers have a digit sum divisible by 11?
You can actually get quite far starting with the number 1: you don’t run into trouble until you hit the number 29. After this, it appears to be quite difficult to get another run even close to this.
Given any stretch of positive integers where only the units digit changes, such as 450, 451, 452, …, 459, the digit sum always increases by 1 as we move from left to right. This makes it quite hard to avoid bad digit sums. To do so, we require the digit sum of the smallest integer in the stretch to be 1 more than a multiple of 11.
570, 571, 572, …, 579.
But for the next ten integers, the digit sums are all 1 greater than their counterparts among the first ten:
580, 581, 582, …, 589,
and now 589 has a bad digit sum.
This problem will occur most of the time. The only hope we have of avoiding it is initially having a 9 in the tens position, but even this might fail:
390, 391, 392, …, 399, … (all good so far)
…400, 401, …, 407 (oh dear).
What we really need is for both integers ending with a 0 (like 390 and 400 above) to have a digit sum 1 greater than a multiple of 11.
Note that we have no hope of extending this sequence (or any similar sequence of length 20) to include all ten integers immediately before it, or all ten integers immediately after it – we’ll hit the same roadblock we had when considering 570-589 earlier.
But we can do the next best thing, and extend all the way down to 999981 and all the way up to 1000018.
Thus the best we can do is 38 integers,the smallest example of which is
999981, 999982, …, 1000018.
This is another one of my favourites – so little prerequisite knowledge, and yet so far from obvious.
Several children sit around a circular table, on which lies a collection of 100 chocolates. They proceed to take chocolates, after which it turns out that each child has taken either 6 fewer or 3 times as many chocolates as the child to their left. Prove that some chocolate was left on the table.
It’s possible to spend a long time pondering just how to solve this problem in its full generality. The solution below is brief, and feels natural, so you could be forgiven for believing this to be an easy puzzle; but it takes a clever insight to come up with the presented approach.
It is impossible for every child to have eaten 6 fewer chocolates than the child to their left (since, among other issues, you cannot eat a negative number of chocolates). So some child has eaten 3 times as many chocolates as the child to their left, and hence the number of chocolates eaten by this child is divisible by 3. But now, as we move anti-clockwise around the circle, at every point we must either subtract 6 or multiply by 3, both of which preserve divisibility by 3.
It follows that the number of chocolates eaten by each child is divisible by 3; thus the total number of chocolates consumed is divisible by 3, and so cannot equal 100. With this statement, the result is proved.
I am a fan of this puzzle for several reasons, not least of which because it is typically very tough getting a handle on objects arranged in a circle with dependencies between them. The solution demonstrates that it is possible to dispel the apparent complexity very swiftly.
In a school, more than 90% of the students study both English and French, and more than 90% of the students study English and German. Prove that more than 90% of the students who study both French and German also study English.
This problem took me a long time to solve. On a first glance, it seems innocuous – surely you just play around with the numbers, possibly with a Venn diagram thrown in, and it just falls out.
After five minutes, you wonder why you haven’t solved it yet; maybe it’s too early or too late in the day, or you’ve expended your mental energy elsewhere.
After fifteen minutes, you think to yourself ‘What is going on?! This problem is simple, right? How is it taking this long…?’
Finally, after 30 minutes or longer, you realise just how tough the problem is. The simplicity of the statement deceived you into believing that a solution would be easy to come by; oh how you were fooled.
It turns out there are several successful approaches, at least one of which is fairly short when polished. A Venn diagram is highly recommended.
Let A be the proportion who study English and French but not German, let B be the proportion who study English and German but not French, let C be the proportion who study French and German but not English, and let D be the proportion who study all three languages.
We are told that A+D>0.9, and B+D>0.9. We are required to prove that D/(C+D)>0.9, which is equivalent to D>9C after some rearranging.
Adding the two initial inequalities yields
Adding C-D to both sides of this leads to
But of course A+B+C+D is at most 1, so in fact we have
Finally, we observe that since A+D>0.9, it must be the case that CC+0.8>C+8C
At last we have the desired result D>9C, and the problem is solved.
This is yet another exquisite problem from the Tournament of the Towns, which really is the gift that keeps on giving as far as mathematics competitions are concerned.
But while many problems are attractive for having a simple solution following a seemingly impenetrable statement, this example is quite different. On the face of it, the problem seems straightforward; it is only after you start investigating that you realise how wrong you were.