Circular optimization

Power Overwhelming 2021-08-10

This post will mostly be focused on construction-type problems in which you’re asked to construct something satisfying property ${P}$ .

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 ${P}$ . Here’s a simple example.

Example 1 (USAMO 2011)

Find an integer ${n}$ such that the remainder when ${2^n}$ is divided by ${n}$ is odd.

It is easy to see, for example, that ${n}$ 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 ${n}$ . 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 ${n = pq}$ for primes ${p}$ and ${q}$ . This does make our life easier, because we’ve zoomed in on a special type of ${n}$ which is easy to compute. But it runs the risk that maybe there is no such example of ${n}$ , 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:

Example 2 (IMO 2014)

For every positive integer ${n}$ , the Bank of Cape Town issues coins of denomination ${\frac 1n}$ . Given a finite collection of such coins (of not necessarily different denominations) with total value at most ${99 + \frac12}$ , prove that it is possible to split this collection into ${100}$ or fewer groups, such that each group has total value at most ${1}$ .

Let’s say in this problem we find ourselves holding two coins of weight ${1/6}$ . 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 ${1/6}$ for a single coin of weight ${1/3}$ . 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.

Problem 1

Prove that in any connected graph ${G}$ on ${2004}$ vertices one can delete some edges to obtain a graph (also with ${2004}$ vertices) whose degrees are all odd.

Problem 2 (USA TST 2017)

In a sports league, each team uses a set of at most ${t}$ signature colors. A set ${S}$ of teams is color-identifiable if one can assign each team in ${S}$ one of their signature colors, such that no team in ${S}$ is assigned any signature color of a different team in ${S}$ . For all positive integers ${n}$ and ${t}$ , determine the maximum integer ${g(n,t)}$ such that: In any sports league with exactly ${n}$ distinct colors present over all teams, one can always find a color-identifiable set of size at least ${g(n,t)}$ .

Feel free to post more examples in the comments.