Combi Solving: APMO 2023 P1

(Dylan here.)

Today, I'll be solving a (pseudorandomly chosen) combinatorics problem. But instead of just explaining the solution, I will detail my messy thought process as I work through it in real time.  After solving the problem, I will do a brief meta-commentary, and try to abstract the problem. Finally, for the more mathematically mature, I will talk about what possibly lies beyond it: various extensions and related areas.

Let's begin.

1    The Problem

(APMO 2023 P1) Let $n\geq 5$ be an integer. Consider $n$ squares with side lengths $1,2,\dots,n$ respectively. The squares are arranged in the plane with their sides parallel to the $x$ and $y$ axes. Suppose that no two squares touch, except possibly at their vertices. Show that it is possible to arrange these squares in a way such that every square touches exactly $2$ other squares. 

1.1    First Thoughts

In no particular order:

• This is a construction problem. 
• The orientation of the squares are fixed to be aligned; the conditions that (a) squares touch at corners and (b) squares have integer side lengths, imply that the squares should also be 'lattice-aligned', i.e. corners have integer coordinates. 
• (Key Idea 1) The fact that every square touches exactly two others is a very strong condition. It screams a structure result from graph theory: that a $2$-regular graph decomposes into disjoint cycles. (To spell it out: squares are vertices, squares touching each other are edges.) 
• The vertex-touching condition reminds me of the board game Blokus. 
• Before even trying some constructions, I can anticipate some challenges: (a) getting the 'perimeter' of the cycles to agree; perhaps triangle-inequality/parity issues. (b) that there may not be enough 'space' to fit the squares in a cycle (perhaps area constraints that force squares to overlap). (c) It might be difficult to put large squares together with small squares. 

1.2    Experimentation

It is now time to try some small cases: $n=5,6,\dots$. What I'm actually trying to do is to get a feel of whether my intuition and ideas above are correct, and whether there's other intuition that I missed. I also want to have a sense of whether the general construction will be built by many disjoint cycles of squares, or a single big cycle. Finally, at the back of my mind, I will also be thinking about how the construction for general $n$ may be obtained from generalising, or extending, small/smaller constructions. 

After some trial and error, here are the constructions for $n=5$ and $n=6$:

And my observations:

• The helpful heuristic for constructing small cases was to place the large squares first, and on the sides; opposite side lengths differing by $1$ or $2$ could then be offset by a 'diagonal' square of side length $1$ or $2$ respectively.
• Each cycle needs at least $4$ squares; but actually, more! $5$ or $6$ is necessary, since square side lengths must be distinct.
• Size and parity seem to be easily avoidable challenges. But without worry of overlap of the squares, I can abstract the problem 'algebraically' as follows:
• I want to 'split' numbers $1,2,\dots,n$ into $4$ groups: 'left', 'up', 'right', 'down', corresponding to how their side lengths contribute to the perimeter of the cycle.
• Each number must appear in either one or two groups. If they appear in two groups, they must be 'adjacent' groups.
• The 'left' and 'right' groups must have equal total sum. The 'up' and 'down' groups must have equal total sum.
• Additional soft-rules: each group should have a number that only appears in that group; preferably, large numbers should be in only one group; etc. 
• The two corners of a square that touch other squares can either be (a) along a side, or (b) along a diagonal. The freedom to choose between these two options seems important.
• Both one large cycle and many small disjoint cycles seem plausible for the general construction. However, the latter is conceptually simpler: 
• (Key Idea 2) If I could get $k=8$ squares of consecutive lengths (i.e. $N+1,N+2,\dots,N+k$) to fit in a cycle, then the problem is resolved by induction, up to the base cases!

1.3    Pursuing the key ideas

I first thought of $k=8$ with sort of an octagon configuration: $4$ side-squares and $4$ diagonal-squares. But before moving to construct such a configuration, I realised that $k=6$ was easily obtainable from the $n=6$ construction above: simply replace the side lengths $1,\dots,6$ with $N+1,\dots,N+6$! It works because each side of the $n=6$ cycle is contributed by two squares.

After establishing the $n\mapsto n+6$ induction step, I have now reduced the problem to resolving the small cases $n=5,\dots,10$, of which $n=5,6$ I have already constructed for. And I already have the octagon idea for $n=8$. I now work out the rest of the constructions:

$n=7$ and $n=9$ hints towards the idea of a general construction involving a single long cycle; I found myself consciously checking to make sure the diagonal squares were of correct parity for a construction to even exist. $n=8$ (image omitted) is indeed realisable by an octagon (e.g. with diagonal lengths $1,2,3,6$), and $n=10$ can be obtained by taking the cycle with lengths $5,\dots,10$ and inserting squares $1,4$ and $2,3$ on opposite sides. This completes the problem!

1.4     The solution

A sketch of how I would write up the proof: 

• Set up the induction statement $n\mapsto n+6$. 
• Draw constructions for $n=5,\dots,10$. 
• Draw the construction of the cycle of squares with side lengths $N+1,\dots,N+6$, in particular noting that the diagonal squares do not overlap.

How I would explain the solution to someone who hasn't solved it: 

• The key idea is to induct from $n$ to $n+6$. $6$ squares of consecutive lengths can be positioned in a cycle. All that's left is to resolve the small cases. 

How I would give someone hints about the problem:

• Have you tried small cases? What do you think the general construction looks like? (hint to Key Idea 1: connectivity structure.)
• Can you extend a construction of smaller $n$ to a construction of larger $n$? (hint to Key Idea 2: induction.)

2    The Meta-Commentary

2.1    General thoughts

I feel that this problem is relatively standard, in the sense that it falls to the general approach to combi problems: (1) understand the freedom and constraints, (2) bridge special/small cases to the general case. We don't even get to go down the rest of the list: (3) forming heuristics, soft-hypotheses, and plausible stepping stones, (4) changing the lens: looking broader/narrower, investigating a broader class of structures, (5) ... 

Among the two key ideas of this problem, the first (regarding connectivity) comes from an understanding of graph theory and being able to recognise this structure in the problem. Without this prior idea, it might be hard to discover it in small cases (since all $n\leq 9$ constructions only involve a single cycle). The second key idea (regarding induction) is motivated from the fact that one may try to extend constructions by adding squares to existing constructions. 

I believe an alternative feasible approach to the construction would be to explicitly build a single long cycle of squares. However, I would anticipate that this approach is more 'fiddly' in the sense of having to ensure that squares do not overlap, and also perhaps having to split at least two cases by parity. 

2.2    Problem elements

Here's a breakdown of the key elements of the problem:

• $n$ objects arranged in the plane – the main freedom of this problem.
• Sides parallel to the $x$ and $y$ axes – constraint on orientation. 
• Squares – constraint on shape.
• Side lengths $1,\dots,n$ – constraint on length/size, maybe parity. 
• No two squares touch, except possibly at their vertices – constraint on connectivity/distance/space.
• Every square touches exactly $2$ other squares – constraint on connectivity. 

In particular, the fact that the problem investigates the interaction between freedom and constraints makes it clear that it is fact combi, and not geometry (even though squares are involved), number theory (even though side lengths are integers), or algebra (even though there is a partial algebraic abstraction). Nevertheless, one should be open to the possibility that geometric/number theoretic/algebraic ideas may still come into play (although they do not play much of a role in this specific problem).

2.3    Loose threads, dead ends, and blind spots

It is often easy to pick up on what worked on a problem, but not too easy to stay aware of what didn't work, wasn't useful, or was missed. We'll spend a bit of time exploring it in this subsection. 

For this particular problem and my particular approach, the algebraic abstraction turned out to be not too useful. However, if one were to construct a single long cycle instead, it would probably be a better framework (assigning numbers so the sums match, and then making sure they actually fit without overlapping). It possibly leads into additive combinatorics.

We also didn't get to exploring "non-convex" cycles, e.g. a configuration of squares shaped like a crescent moon. The reason is because the amount of freedom in arranging the squares is already so tremendous compared to the constraints. 

My approach also implicitly focused on cycles that are generally parallel to the axes, with diagonal squares being the oddity. I could have instead investigated cycles that are generally parallel to the diagonals, i.e. most squares in the cycle are diagonal, with perhaps only $4$ side-squares per cycle. Again, this was irrelevant to our approach of adding disjoint cycles, but it would be an alternative way to build a single large cycle of squares.

Our disjoint cycles were built by consecutive-sized squares, but we could have also tried to consider building cycles that mixed large squares with small ones (which would be necessary if we wished to build, say, cycles of $5$ squares).

3    Extensions

This is the first problem of a contest, so it is expected for students not to spend too much time thinking about it. Nevertheless, I believe it is worthwhile to explore deeper into extensions of this problem, for the following reasons: (a) it helps to give context to how important the ideas are and how they are motivated; (b) the maths usually only gets interesting upon stepping back to see the 'big picture', (c) several harder combi problems may require one to explore extensions as a way of gaining clarity on what structure is actually important.

3.1   First tweaks

For interest of brevity, I will focus on posing questions and not answering them; the keen eye might realise that some lines of pursuit will quickly run dry, while others lead to deeper rabbit holes, but I will not discriminate at this point. Free exploration is a developed skill, but one simple way to begin is to start with the breakdown of problem elements above, and add/remove/modify individual elements. In no particular order:

1. Adding an optimisation dimension to the problem: can I try to maximise the number of disjoint cycles in my construction?
2. Adding an enumerative dimension to the problem: how many constructions are there? Is it exponential in $n$, or worse?
3. Adding an adversarial dimension to the problem: what if two players were competing to place squares on a finite board (like Blokus)? Or trying to maximise the number of corner adjacencies?
4. Adding a literal dimension to the problem: what if I replace squares with cubes?
5. Changing the shape: what if I replace squares with equilateral triangles or regular hexagons? (These shapes can still be required to be aligned to an isometric grid.) How about rectangles? Circles?
6. Changing the sizes: what if I replace $1,\dots,n$ with, say, perfect squares, cubes, or powers of $2$? Or a general 'dense' subset, e.g. any $n$ numbers among $1,\dots,2n$?
7. Removing the alignment constraint: what if I no longer require squares to be axis-aligned? With the extra freedom, what extra constraints can I impose? 
8. Removing the spacing condition: what if squares can touch on edges as well, just not overlap? 
9. Changing the valency: what if I require squares to touch $3$ other squares? 
10. Changing the number: what if I have to arrange an infinite number of squares?

3.2    Forming questions

Now that we have base tweaks, we can try to combine them in interesting ways. In particular, I wish to combine them in a way that brings out the lesser explored areas: (a) geometric ideas of area/adjacency, (b) algebraic ideas, (c) combinatorial counting bounds, (d) parity. Here are some of them:

• (4+8) Can I arrange circles of radii $1,\dots,n$ such that every circle touches (i.e. is tangent to) exactly $3$ others? (leans into geometry)
• (8+9) Can I arrange squares of side lengths $1,2,\dots$ such that every square touches exactly $3$ others? (leans into just-do-it, perhaps)
• (1+7) What is the minimum-size square that I can fit $n$ non-overlapping squares of side length $1,\dots,n$ into? What if I require them to all be connected, and by corners? (leans into space constraints)
• (5) If the $n$ squares' side lengths are chosen among $1,\dots,2n-2$, can I still have a construction for sufficiently large $n$? (leans into additive combi; the $2n-2$ is to avoid parity problems).
• (negative space) The squares mark out a few bounded regions of the plane; is there a lower bound on the area of these regions? (leans into space constraints)
• Can I dissect a $2023\times 2023$ square into $n$ rectangles (for some $n$), such that every number from $1,\dots,2n$ appears exactly once as a width and exactly once as a length?

4    Conclusion

I hope this post gave you insight into how I approach combinatorics problems, formulate ideas, and explore beyond the surface level. Whether or not this post conveyed them, here are the sort-of 'intended' messages:

1. There is intuition and motivation behind both the problem statement and the solution.
2. It helps to name your ideas, for both internal clarity and also for communication.
3. There is tremendous value in introspection: understanding your own thought process and why you are struggling with a problem, not just learning the solution. 

Thanks for reading to the end!