To Spoil or Not to Spoil (ft. A7, the most beautiful problem of ISL '23)

 (Dylan here.)

As usual, some non-maths, followed by some maths.

I. To Spoil or Not to Spoil?

Some context, so everyone is on the same page:

• To spoil a maths problem is to reveal key ideas, steps, and/or details of its solution to others, without their consent. 
• The content of the problem that is conveyed is called a spoiler (often confused with the thing at the back of race cars that prevent them from flying!).
• Spoilers could be as short as one word, a picture, or a non-verbal cue.
• Spoiling could happen anytime there is more than one person in the same room doing maths. It is very common in an unsupervised classroom of high school students.

The questions I wish to answer (or at least, bring up for discussion):

1. Do spoilers help or impede learning? 
2. How is spoiling different from teaching?
3. When is is okay to give up on a maths problem?
4. Why do people spoil maths problems?

A. Arguments for and against

Okay, so no one is actually debating this. Spoiling olympiad problems, especially in a group setting, has always been (and will probably continue to be) seen as disruptive and in poor spirit. 

Nevertheless, I'm interested in the wider pedagogical question of: how much should we as educators teach explicitly, how much should we set aside for guided discovery, and how much should we leave for independent exploration? (We get to approach this question both in the point of view of a student, and also as a teacher!)

For spoiling:

• It's Q2 of a 10-question set; surely people have either already solved it, or tried it to bits and given up by now.
• I was trying to share why I thought this problem was so cool/easy, and it slipped out by accident.
• They're going to go through the solutions soon anyway; I was just trying to give you a hint so you could work out the rest before the end of the session. 
• Being spoiled a problem doesn't ruin the sole chance of finding the idea oneself; there are plenty of other problems with similar ideas for one to try.
• It speeds up one's learning, by skipping over the period of trying ideas that don't work. 

Against spoiling:

• I'm still trying new ideas; I want to practise deciding by myself if these ideas work or not.
• Even if I'm stuck now, I want to give myself the chance to inspire a new idea in time.
• Spoilers would skip over the period of trying ideas that don't work, but this is important for building understanding and intuition.
• Being spoiled on a problem wastes its educational value.
• Working through problems without spoilers builds the habit of delayed gratification.

B. (brief tangent) School classes vs. olympiad trainings

In school, most classes have content presented to you directly. You are told how to solve $a^2-2a = 15$, or how to differentiate $x^2$; you don't get a chance to reinvent the wheel. But in maths olympiad training, sessions are designed very differently: students work on a couple of problems for 3-4 hours, with only a brief introduction of vague content at the beginning. 

Why this difference? Well, the skill set nurtured is different. One involves absorbing and retaining information, while the other emphasises application of ideas, intuition building, and creativity. 

Importantly, this is not a hard divide. We also need to do (and have done) a great deal of learning of ideas (not sure about you, but I definitely did not reinvent the Cauchy-Schwarz inequality). Such ideas need not be most efficiently learnt in a problem solving session (though eventually, problems will allow one to experience the multitude of ways in which Cauchy-Schwarz may be applied). And conversely, there are aspects of school classes that require creative input as well.

Even soft ideas such as 

When proving $A\geq B$, it might be easier to prove $AB\geq B^2$, or perhaps equivalently, to normalise $B=1$. 

can be taught! Not by simply stating it as above, of course, but with sufficient context, motivation, and illlustrative examples. It's just hard to teach (it was already very difficult for me to form the sentence). But it is certainly possible. 

C. Back to spoilers: the issue of empathy

I believe the issue arises in the asymmetry of knowledge and experience between student and teacher (or spoilee and spoiler), plus a lack of empathy to bridge the gap. This means the one who spoils a problem does not consider the problem-solving experience of their peers, in various senses:

• They might be conceptualising/approaching the problem in a completely different way from you.
• They might be stuck somewhere due to a specific gap in their knowledge/experience, unknown to you.
• They may have only just started working on the problem.
• They might not be in the mood to be think about maths that day.

To paraphrase, most arguments "for spoiling" involve assumptions about others. And in practice, these assumptions are often false. For an example from personal experience, I have run themed sessions that highlight a combinatorial idea I deem extremely important, only to realise over the session that some students seem to have a completely different approach to combinatorics (so this idea is no more special than any others in the bag of tricks). And on the flipside, I have heard others speak about functional equations in a way that hints they see something deeper than what I see, but I couldn't figure out what.

Back to the example of Cauchy-Schwarz, I'm pretty sure the first time I learnt it, it was just some algebraic statement about two sets of $n$ variables. The expression $\sum_i a_ib_i$ was similar to expressions in the rearrangement inequality. The proof $\sum_i (a_i-\lambda b_i)^2 \geq 0$, introducing a new variable $\lambda$ only to later take the discriminant of the quadratic, was a legendary trick, beyond unmotivatable to me then. Inequality problems showed me how to turn a sum $\sum_i X_i$ into a sum $\sum_i a_ib_i$ by a clever splitting of the expression $X_i$, to get a desired inequality.

Now I know that Cauchy-Schwarz sits among the geometric notions of a norm (lengths) and inner product (projections/angles) in $n$-dimensional Euclidean space (where Pythagoras still holds). The proof above encodes the perpendicular distance from a vector $\vec a$ to the line spanned by $\vec b$, which is zero only if $\vec a\parallel \vec b$. I know how the power mean inequalities correspond to other norms. I know how the underlying reason why these norms obey triangle inequality, is convexity properties of $x\mapsto |x|^p$ (i.e. Jensen's inequality). 

When teaching students about Cauchy-Schwarz, it is tempting to assume they see the geometry, or can think about more than $3$ dimensions, or can interpret $\vec a = (a_1,\dots,a_n)$ as coordinates of a vector (implicitly, with respect to an orthonormal basis). It is easy to assume they can tell that rearrangement and Cauchy-Schwarz are worlds apart (rearrangement is linear optimisation; C-S is quadratic). We unconsciously forget that young students don't know if Cauchy-Schwarz may be proven with smoothing/convexity, and how.

In a world where everyone experiences maths differently, and people try their best to communicate and share ideas anyway, we can practise, whether as a student, a peer, or a teacher, having empathy. And as we begin to view maths through the eyes of others, we end up seeing more.

D. How does one best learn?

Finally, we address a specific question: do spoilers, or reading solutions to problems "early", accelerate or impede learning?

The answer is of course, it depends. It depends on your learning style, why you are doing maths, and how you want to do maths.

Take the example of studying for school exams. Some opt to work through past year papers, and using the questions they get wrong to inform them on what they don't know. Some choose to read through 10+ years of past problems, believing that it is more efficient. Some spend most time making detailed and/or concise revision notes, and only do one/two papers to acclimatise to exam pacing and conditions. Some do a weighted combination of all of the above.

Some believe their exam results reflect their intellect and ability (specific to the subject or in general; short-term or long-term). Some study for the exam with the intent of peaking in the moment, then forgetting all content right after it ends. Some see the exam merely as an administrative necessity, for the school to justify eventually graduating you. 

Some like to spend hours struggling with figuring out a concept, believing it helps build some intangible quality; others believe the struggle is unnecessary and only delays effective learning. Some want to solidify whatever they learn to stay in their head forever; others like to learn widely, broadly, and quickly, and whatever ends up sticking will naturally stick. Some like to conceptualise things on their own; others thrive in collaborative discussion. 

Some can afford hours and plenty of residual brain space to learning; others have divided priorities and interests. Some are energised by learning; others are drained.

All this applies to maths olympiad as well! In particular, (I believe) there is no universally right way to do maths. This is especially true when a good amount of learning is done independently, a lot of important maths ideas are not written down explicitly anywhere, and not all forms of support are readily available to everyone (e.g. some may not have other peers to discuss with, or a teacher that advises them on what to learn). Not just students, but also teachers and olympiad trainers, are trying to figure out how to best teach/learn maths. 

If it depends, how does one then decide if spoilers help or impede their own learning; or more generally, how to learn most effectively? 

My suggestion would be to try as many possible forms of learning as possible. This means:

•  saying "no, let me try a bit longer", but also saying "yes, give me a hint" occasionally. 
• working on questions today, but learning new theory tomorrow. 
• trying problems you like, but also problems you don't like. 
• writing things down, but also working in your head sometimes. 
• learning broadly, but also deep-diving. 
• dabbling into CS, physics, or even finance (statistics) and philosophy. 
• learning how to press on and try new ideas, but also figuring out how to learn even after giving up.

And hopefully, in the process of exploring to find your preferred style of doing maths, you continue to have lots of fun!

Okay, enough yapping, time for some maths.

II. ISL '23 A7: Poetry in Motion

(ISL '23 A7) Let $N$ be a positive integer. Prove that there exist three permutations $a_1,\dots,a_N$, $b_1,\dots,b_N$, and $c_1,\dots,c_N$ of $1,\dots,N$ such that $$\left |\sqrt{a_k} + \sqrt{b_k}+\sqrt{c_k}-2\sqrt{N}\right | < 2023$$for every $k=1,2,\dots,N$.

A. (brief tangent) Why this problem stood out to me

My particular preference is towards combi problems, since I can engage with them without pen and paper. This problem concerns permutations of $\sqrt 1, \sqrt2, \dots, \sqrt N$; we want three permutations that satisfy some averaging/balancing property. Such a simple formulation; how could this be the hardest algebra problem on the shortlist? On the other hand, there's probably some interesting interplay between the analyticity of $x\mapsto \sqrt x$ and the discreteness of permutations!

B. First thoughts

Here, I collect some initial trains of thought (in no particular order, due to my poor memory). 

0. Initial simplifications.

The exact size of the number $2023$ shouldn't matter; it probably is just a sufficiently large constant.

1. Why should I believe this problem is true? 

In particular, why is the average $2\sqrt N$? This means I want to compute $\sqrt 1 + \sqrt 2 + \dots + \sqrt N$. Luckily, I know about integration in calculus as computing the area beneath a curve:

$$\sqrt 1 + \dots + \sqrt N \approx \int_{0}^N \sqrt x = \frac{2}{3}N^{3/2}$$ 

so the average over three permutations split into $N$ groups, is $3 \cdot \frac{2}{3}N^{3/2} / N = 2\sqrt N$. Brilliant!

2. Why is this problem hard?

Okay, let's try forming groups of $3$. How do I begin?

Well, what group should contain $\sqrt 1$? Hmm... I have no freedom here; I need to pair it with two other copies of $\sqrt N$! 

Okay, so one small gets paired with two large. What happens if we do this in general?

Let's work out what such a sum would be: $\sqrt x + \sqrt{N-2x} + \sqrt{N-2x}$, since the larger numbers deplete twice as fast as the smaller numbers. 

Well, whatever this sum is, it certainly isn't going to be constant as $x$ varies. For a sanity check, if we had kept going with small-large-large till all numbers are exhausted, we would have (when $x=N/3$ the final group sum $3\sqrt{N/3} = \sqrt{3N}$, shy of the target sum $2\sqrt N$. But somewhere in the middle, say $x=.18N$, the sum becomes $(\sqrt{.18} + 2\cdot .8)\sqrt{N} > 2\sqrt N$.

(I just chose some intermediate value of $0< x/N < 1/3$ so that $\sqrt{N-2x}$ is something I could compute in my head. By some stroke of luck, $x = 0.18N$ in fact attains the maximum group sum in this proposed grouping; one may prove this by some derivative-vanishes calculus. Not that knowing this will be of any use, though.)

Well, maybe the idea is to start with small-large-large (so that groups containing $1$ or constant-sized elements are fine), then do some combinatorial balancing/redistribution of the intermediate groups.

In fact, this problem suggests something peculiar: there are (probably) groups with three copies of  $2\sqrt N /3 = \sqrt{4N/9}$. So somehow, the distribution/redistribution has to bridge between small-large-large and three-$\sqrt{4N/9}$'s. 

3. Two permutations

Three permuations is a handful, so let's try to see how to balance two permutations. What would we best pair two permutations of $\sqrt 1, \dots, \sqrt N$ while keeping the group sums as close to the average as possible?

Well, there isn't much choice. The smallest element must be paired with the largest element, then the second smallest with the second largest, and so on. This is in fact true for any initial set $a_1,\dots,a_N$.

Well, this tells us that the analogous question for two permutations is only true if the initial set $a_1,\dots,a_N$ is close to an arithmetic progression (or more generally, has reflectional symmetry). In particular, the freedom of three permutations (instead of two) is crucial.

4. Generalising the function $x\mapsto \sqrt{x}$

The fact that $1$ must be paired with two $\sqrt N$'s means that the square root function is "tight" in some sense. In particular, the problem is false with $1^\alpha,\dots,N^\alpha$ for $\alpha > 1/2$.  

This begs the question: is the question true for $\alpha < 1/2$? Or for some controlled perturbation of the square root? Or some piecewise linear function? In particular, is the question true because of the specific shape of $x\mapsto \sqrt x$, or is it combinatorial upon extracting some broad shape information (like min, max, average, and a roughly even distribution)?

This initial exploration of the problem has led me to this central question: is the problem analytic or combinatorial in nature? Specifically, which parts of this problem is analytic (i.e. depends on properties of the square root; concavity, range, smoothness) and which parts are combinatorial (algorithmic design to arrange/rearrange groups in an averaging manner)?

C. Digging deeper

Actually, this was as far as I thought about the problem on my initial go at it (at this point, I haven't written anything down yet). I only came back to it months later, after it resurfaced in conversation with another senior. I decided it was time for me to take down this problem once and for all.

5. Local rebalancing

Given two groups $a_1,b_1,c_1$ and $a_2,b_2,c_2$ with different sums, could I swap $a_1\leftrightarrow a_2$, $b_1\leftrightarrow b_2$, or $c_1\leftrightarrow c_2$ to bring the sums as close as possible together? How would that look like? 

Wouldn't it be nice if this idea worked! But it doesn't (thankfully too, otherwise it'd have been a pretty dull problem). The main problem is that even if the balancing conditions are figured out, the local balancing \textbf{disregards scale}: the difference can't ever be bounded by a constant independent of the size of the values. For instance, small-large-large vs three-mediums.

We thus need to look for a global allocation of groups.

6. Discretisation

Implicitly in the above discussion, I have been discretising the values $\sqrt 1, \dots, \sqrt N$. So when I say $1$ is grouped with two $\sqrt N$'s, what I really mean is that constants are grouped with two $(\sqrt N - \text{constant})$'s. Notice the subtle asymmetry: while there are $2023^2$ (constantly many) values less than $2023$, there are $\approx c\sqrt N$ values at least $\sqrt N - 2023$. Even in this regime, the small-large-large doesn't work. 

Anyhow, if one were to achieve any sort of combinatorial global allocation, it would be wise to discretise the values. Intuitively, this means dividing the continuous real line into boxes (of constant width, since the error allowed here is a constant; in general, the widths might vary with the distribution of values). Conceretely, this means rounding each $\sqrt k$ value to a nearby integer.

Note: whether you round down, up, or to the closest integer, doesn't matter! All it does is affect each group sum by $\pm 3$ (and $3\ll 2023$). I chose to round everything up (i.e. take ceiling), but you might prefer taking the floor; the arguments won't change anyway.

Now our values are $1,2,2,2,3,3,3,3,3,4,\dots, \lceil \sqrt N \rceil$.

7. Drawing pictures

Having discretised, we can now finally draw a picture of what we are trying to do! Here we draw a histogram (i.e. frequency-against-value) of the numbers. 

What I get is a triangle: $1,3,5,\dots, 2k-1$. Of course, this is only if $N=k^2$; in general, it looks like $1,3,5,\dots,2k-1,a$ for $a\leq 2k$. While this is a technically crucial detail, we know morally that it shouldn't matter (since the discretisation was arbitrary anyway). So for simplicity, let's assume $N=k^2$ and the histogram is in fact the full triangle. 

8. Wait... induction?

Hold on—a triangle contains a smaller triangle inside! So it may be possible to prove this by induction (in the case $N = k^2$, at least). 

Time to try it! Let's mark out a smaller red triangle of points, assume it can be balanced in groups of $3$, and try to balance the remaining points on the border (black).

Pause; before we even begin figuring this out, let's do a sanity check: we need the average to be $2k/3$, so the red triangle needs to be the "correct relative position with respect to $2k/3$". Hmm... this means that the red induction triangle shouldn't be the one drawn above, but should be this one instead (two from the left, one from the right):

9. Finishing the induction

What is the shape of the remaining black points that we have to group? 

Well, the frequency values are $1,3,4,4,4,\dots,4,2k-1$. Which is essentially $4$ copies of each of the values $1,2,\dots,k$, and $2k$ additional copies of the value $k$. (Well, actually three times of this, since we have 3 copies of everything. But whatever). And we are aiming for the average value $2k/3$. 

If you got to this point, you might be thinking about the values combinatorially (say, generalising small-large-large) or physically (a density-$4$ slanted rod with a density-$2$ vertical rod). In any case, the values line up just right! The groups are $x,k-x,k$; or, symmetric chunks of the density-$4$ rod together with one chunk of the density-$2$ vertical rod. 

Induction complete!

10. Housekeeping: general $N$

At this point, we have fully proven the result for $N=k^2$ by induction. But what about general $N$?

Well, at this point, I have considered myself to have solved the essence of the problem. As described earlier, the final frequency deficit $1,3,\dots,2k-1,a$ in the histogram is an artefact of the round, and morally shouldn't matter (and I am neither a high school student nor under contest pressure to write up a complete solution). 

Nevertheless, I do see that the precise induction step doesn't immediately transfer: one has to absorb most of the deficit into the induction hypothesis (red triangle) and only tolerate a constant amount of deficit at each step. But in theory, that's fine.

D. What happens after solving the problem?

Some reflection is due. The solution above indeed depended on the specific shape of $x\mapsto \sqrt x$, namely that the histogram formed a triangle (which is built from smaller triangles by adding layers: the spirit of induction). Furthermore, the induction step works out just nice (echoing the tightness of the $1,\sqrt N,\sqrt N$ group). There was indeed not to much combinatorics (unless one counts discretisation as a combinatorial idea, which is reasonable).

But, why does everything work out just nice? What's up with the final $x,k-x,k$ induction grouping? and is the result true/proof methods extendable to other functions such as $x\mapsto \sqrt[3] x$? (One metric of truly understanding a problem or solution, is whether one understands the key ideas well enough to be able to generalise the problem!)

This reflection took time. It didn't come immediately after solving the problem; perspectives just slowly sank in over time (with this somewhere in the back of my mind). 

11. The triangle

At some point it dawned on me that while I drew the histogram as a right angled triangle, literally any triangle would work! In particular, I have instead drew a discretised equilateral triangle. 

Now this is getting somewhere: the equilateral triangle has $3$-fold rotational symmetry! Can this be a natural way to understand the groupings? 

Well, let's focus on the three corners of the equilateral. Small-large-large; looking good so far. Now, how about a point on the boundary? Grouping it with its other two images under rotations, then projecting, one gets $x,k-x,k$. Wow!

So, that's precisely the true underlying nature of this problem. Let me summarise it in precise fancy jargon:

The group of size $3$ acts by linear isometries on the equilateral triangle. For any point, the vector sum of all its images is zero. Taking a discretisation (proportional to area) followed by projection, one obtains an allocation of $\sqrt 1,\dots,\sqrt N$ into approximately mean-balanced groups of $3$.

12. The tetrahedron (first generalisation)

Armed with this newfound insight, let's generalise the problem by moving into $3$ dimensions (again, I am free to do this because I'm no longer constrained by olympiad syllabus! and as mentioned earlier, ability to generalise reflects some understanding of deep insight). 

The tetrahedron has full symmetry group $S_4$, but we are looking for something smaller. Hopefully a size-$4$ subgroup for which all $4$ vertices of the tetrahedron fall in a single orbit, and other orbits have a similar symmetry about the origin. 

I know abstractly that this exists: $V_4$, the Klein-$4$ group. But for the sake of the younger audience, let me try to describe it in a few ways, and also concretely, so that you may believe it exists. Abstractly, the group is the set of double-transpositions:

$$V_4 = \{e, (12)(34), (13)(24),(14)(23)\}$$

Thinking of $S_4$ as "permutations of $\{1,2,3,4\}$", in fact $1,2,3,4$ correspond to the four vertices $P_1,P_2,P_3,P_4$ of the tetrahedron. 

Let's work with an explicit tetrahedron in $\R^3$: I pick in $(x,y,z)$-coordinates the vertices $P_1 = (1,1,1)$, $P_2 = (1,-1,-1)$, $P_3=(-1,1,-1)$, $P_4 = (-1,-1,1)$. Now the group element $g=(12)(34)$ swaps $P_1\leftrightarrow P_2$ and $P_3\leftrightarrow P_4$; geometrically, it is the $180^\circ$-rotation of the tetrahedron about an axis that passes through the midpoint of $P_1P_2$ and $P_3P_4$:

Explicitly, the midpoints are $(1,0,0)$ and $(-1,0,0)$, so $g$ is $180^\circ$-rotation about the $x$-axis: $(x,y,z) \mapsto (x,-y,-z)$. 

Similarly, one sees the other group elements correspond to $180^\circ$-rotations about the $y$- and $z$-axes. These are all isometries (distance-preserving, thus also volume-preserving), and any point has the sum of its images being zero:

$$(x,y,z) + (x,-y,-z) + (-x,y,-z) + (-x,-y,z) = (0,0,0)$$

Now let's discretise and project. We get the histogram profile corresponding to $x\mapsto \sqrt[3] x$ (since volume scales proportional to length cubed). To conclude, we have obtained the following generalisation:

(ISL '23 A7, tweaked) Let $N$ be a positive integer. Prove that there exist four permutations $a_1,\dots,a_N$, $b_1,\dots,b_N$, $c_1,\dots,c_N$, and $d_1,\dots, d_N$ of $1,\dots,N$ such that $$\left |\sqrt[3]{a_k} + \sqrt[3]{b_k}+\sqrt[3]{c_k}+\sqrt[3]{d_k}-3\sqrt[3]{N}\right | < 2023$$for every $k=1,2,\dots,N$.

Note: the cofficient $3$ in $3\sqrt[3]{N}$ is due to the centre of the tetrahedron being $\frac{3}{4}$ of the way along an altitude (and groups being of size $4$). This, in turn, follows from the fact that the centre of the tetrahedron is the weighted average of the $4$ vertices. 

Note: you might be worried (or more likely, completely forgot) that while the equilateral admits a regular tiling, the tetrahedron does not. Geometric intuition tells me the result should be true anyway (and that even if I can't discretise the tetrahedron nicely, I can still run an induction argument on the $\lceil \sqrt[3] x \rceil$ values).

13. Combinatorial generalisations

Anyone who fancies algorithmic combinatorics might be disappointed to find that the solution is ultra-specific to the function $x\mapsto \sqrt x$ (I might be wrong, but the term used to describe these results that require specific setups is "non-robust", meaning that it is intolerant of adverserial/random perturbations/errors to the input). In particular, it is still not clear, though very believable (to me at least), that the problem with $x\mapsto \sqrt[3] x$ with three permutations is true!

I haven't figured out any generalisations in this direction yet (though I'm pretty sure proving a robust statement would require some new idea, genuinely different in flavour to the idea for the original problem).

E. Spoiling ISL '23 A7

If you have gotten here by fast scrolling, you might realise that the single words "equilateral" or "triangle", or any of the pictures above, would be considered a spoiler. And they would obscure all the intuition gained from trying the problem fresh (e.g. knowing to look for a global allocation, because local swaps won't work). Even reading through this post would have deprived you from trying it fresh yourself.

But also, the presentation of the problem already pruned a branch of thought. After all, "prove this" already tells you that "this" is true! Consider instead the following modified yes/no problem:

(ISL '23 A7, modified) Does there exist an absolute constant $C$ such that for every positive integer $N$, there exist three permutations $a_1,\dots,a_N$, $b_1,\dots,b_N$, and $c_1,\dots,c_N$ of $1,\dots,N$ such that $$\left |\sqrt{a_k} + \sqrt{b_k}+\sqrt{c_k}-2\sqrt{N}\right | < C$$for every $k=1,2,\dots,N$?

Trying and failing to prove "no" might (and usually does) hint towards ideas for why "yes" is true. After all, even though the presentation is a mouthful, this might very well be the initial/more natural formulation that the problem setter worked through! 

What does this mean? Well, if a problem asks you to "prove this", it helps to consciously ignore the passive spoiler, and try and decide for yourself why you would believe that "this" is true (or a natural structure to consider). 

III. Conclusion

1. Don't spoil problems without first having empathy.
2. Find a style of doing maths that suits you.
3. Draw pictures. 
4. Embrace the natural flow of ideas! Fruitless ideas are just as important as ideas that work. 
5. To see if you've fully understood the heart of a problem, try to generalise it.
6. Identify, and consciously ignore, spoilers within the problem.