A Different Perspective

(Xu Chen here) Today I am going to talk about a subtle but important thought process for many problems, which is how you visualize the objects you are working with. This is more of an intuitive idea than rigorous math, so forgive me if not everything is super clear in this post.

How you look at the problem can heavily influence what ideas you can come up with: The solution often follows from a good understanding of the underlying structure.

Example 1.

Let's start with a simple example.

(USAJMO 2019/2) Let $\Z$ be the set of all integers. Find all pairs of integers $(a,b)$ for which there exist functions $f:\Z\to\Z$ and $g:\Z\to\Z$ satisfying $$f(g(x))=x+a\quad \text{and}\quad g(f(x))=x+b$$ for all integers $x$.

Hopefully it is clear that we cannot treat this as a standard FE, but must instead consider some combinatorial ideas. Let's think of $\Z$ on the number line. We draw red arrows to represent $x\mapsto f(x)$ and blue arrows to represent $x\mapsto g(x)$:

One condition says that starting from $x$ and following a blue arrow, then a red arrow, puts you at $x+a$. This is kind of hard to see from our current picture. It follows that this is probably not the correct way to think about the problem. Let's rearrange $\Z$ into $|a|$ chains, each chain being one residue class mod $|a|$.

Now the condition says blue then red moves us one vertex down the chain. Much better. But the other condition about $x+b$ is still not represented properly. A bit of experimenting should give that it is more natural to think of two copies of $\Z$, with $f$ and $g$ mapping back and forth between them.

From this diagram, it should be clear that the chains in the two copies of $\Z$ pair up, from which $|a|=|b|$. There are more details to the solution, but this is the main idea.

Thus we see that when the conditions of the question are clearly visible in the diagram, it becomes much easier to see what is actually going on. Let's look at a different illustrative example.

Example 2.

(IMO 2012/3) The liar's guessing game is a game played between two players $A$ and $B$. The rules of the game depend on two positive integers $k$ and $n$ which are known to both players.

At the start of the game, $A$ chooses integers $x$ and $N$ with $1\leq x\leq N.$ Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. Player $B$ now tries to obtain information about $x$ by asking player $A$ questions as follows: each question consists of $B$ specifying an arbitrary set $S$ of positive integers (possibly one specified in some previous question), and asking $A$ whether $x$ belongs to $S$. Player $B$ may ask as many questions as he wishes. After each question, player $A$ must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any $k+1$ consecutive answers, at least one answer must be truthful.

After $B$ has asked as many questions as he wants, he must specify a set $X$ of at most $n$ positive integers. If $x$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that:

(a) If $n \geq 2^k,$ then $B$ can guarantee a win.

(b) For all sufficiently large $k$, there exists an integer $n \geq (1.99)^k$ such that $B$ cannot guarantee a win.

A very long question indeed. The setup of the question can be quite confusing, since there is incomplete information, lying, and lots of numbers being thrown around. We make two observations what the players' strategies must look like.

• Since $B$ can ask arbitrarily many questions, we can assume $B$ eliminates one number at a time until there are $n$ numbers left.
• Similarly, $A$'s strategy necessarily involves keeping a set of $n+1$ "possible" numbers, since he does not benefit from keeping more.

Thus the only important case is $N = n+1$, and $A$ cannot allow $B$ to eliminate any number. This gives the following interpretation of the question:

Let $n,k$ be positive integers known to both players. We start with the sequence $(x_1,x_2,\dots,x_{n+1}) = (0,0,\dots,0)$. Each move, player $B$ partitions $\{1,2,\dots,n+1\}$ into two sets $S,T$. Player $A$ then chooses to either:

• Increase $x_i$ by 1 for each $i\in S$ and reset $x_j$ to 0 for each $j\in T$, or
• Increase $x_i$ by 1 for each $i\in T$ and reset $x_j$ to 0 for each $j\in S$.

Player $B$ wins if $x_i=k+1$ for some $i$.

Here $x_i$ answers the question "If $x=i$, how many times has $A$ lied consecutively?", so it is equivalent to the original problem. If you like, you can even think of $n+1$ chips moving from left to right with a "finish line" at $k+1$:

I find this formulation of the problem much easier to think about, since the game is now perfect information, the game state only depends on $(x_i)$, etc. Note that we have discarded all irrelevant information: $x,N$ are not part of the problem anymore. This prevents us from wasting time thinking about unimportant things.

This can directly motivate the main ideas in the solution:

• For part (a), player $B$ wants to force some $x_i$ upwards. It then makes sense to finish by repeatedly splitting the large $x_i$'s into two halves to force $A$ to increase one of the halves.
• For part (b), player $A$ wants to keep all the $x_i$'s small in some sense. It then makes sense to minimise $\sum_{i=1}^n f(x_i)$ for some function $f$.

Conclusion

Finding the correct visualization is not always easy, so here are a few things that may help:

• As above: The problem conditions should look "natural" in the construct, and irrelevant information should be discarded.
• Tinker around! There are many ways to look at the same thing, some are better suited for the question than others, and you don't know until you try.
• Ask yourself: What is this problem really about? What properties emerge from the given definitions?

That's all I have today, hopefully this helps in building intuition for some problems.