This post will mostly be focused on construction-type problems in which you’re asked to construct something satisfying property .
Minor spoilers for USAMO 2011/4, IMO 2014/5.
1. What is a leap of faith?
Usually, a good thing to do whenever you can is to make “safe moves” which are implied by the property . Here’s a simple example.
It is easy to see, for example, that itself must be odd for this to be true, and so we can make our life easier without incurring any worries by restricting our search to odd . You might therefore call this an “optimization”: a kind of move that makes the problem easier, essentially for free.
But often times such “safe moves” or not enough to solve the problem, and you have to eventually make “leap-of-faith moves”. For example, maybe in the above problem, we might try to focus our attention on numbers for primes and . This does make our life easier, because we’ve zoomed in on a special type of which is easy to compute. But it runs the risk that maybe there is no such example of , or that the smallest one is difficult to find.
2. Circular reasoning can sometimes save the day
However, a strange type of circular reasoning can sometimes happen, in which a move that would otherwise be a leap-of-faith is actually known to be safe because you also know that the problem statement you are trying to prove is true. I can hardly do better than to give the most famous example:
Let’s say in this problem we find ourselves holding two coins of weight . Perhaps we wish to put these coins in the same group, so that we have one less decision to make. However, this could rightly be viewed as a “leap-of-faith”, because there’s no logical reason why the task must remain possible after making this first move.
Except there is a non-logical reason: this is the same as trading the two coins of weight for a single coin of weight . Why is the task still possible? Because the problem says so: the very problem we are trying to solve includes this case, too. If the problem is going to be true, then it had better be true after we make this trade.
Thus by a perverse circular reasoning we can rest assured that our leap-of-faith here will not come back to bite us. (And in fact, this optimization is a major step of the solution.)
3. More examples of circular optimization
Here’s some more examples of problems you can try that I think have a similar idea.
Feel free to post more examples in the comments.