Who is Alice, and why do her coins give multiples of everything?

INT. CLASSROOM SOMEWHERE IN NUS — LATE AFTERNOON

Close-up of an open copy of Bott-Tu on the desk, atop pages of largely illegible scratchwork. Slow zoom out and pan up to a duo in front of the whiteboard. In the far corner of the frame, a third becomes visible, seated, lightly patting one's own tummy. 

"Let's write an IMO problem," said one. 

"Sure," said the other.

"Get back to real math," said the third. But it was too late: the juices of creativity and mathematical delusion had begun flowing, unyielding to all forces of nature (except perhaps dinnertime). 

"Let's start with a grid of numbers."

A grid was drawn on the board, but no numbers were written. Indeed, it was because they did not yet know what numbers belonged in the grid.

"Integers? Rationals? Real numbers?"

"Maybe some number theory thing... let's stick with integers first."

"Okay."

The grid remained empty, like an empty stomach.

"How about a finite amount of information?"

"So it could be a bounded grid of numbers... or, residues modulo a fixed prime."

The grid still remained empty, like my empty stomach.

"Okay, how about: we give the $(x,y)$-th cell the value $a_{x,y} = f(x,y)$ mod $p$, where $f$ is periodic mod $p$?"

"So like, a polynomial in $x,y$."

"Exactly."

"So like a torus."

"Oooh."

For context, a torus is a fancy word for the surface of a donut, like in Zootopia or The Simpsons. One also realises it as a square with opposite sides glued, like the Portal video game if there were portals on opposing walls, or modern versions of Snake. The doubly periodic condition on $f$ means that the grid of numbers can be seen as numbers on a grid on a torus. I don't know if I prefer chocolate or strawberry sprinkles, but both are definitely better than those plain sugar ones.

"Can we add some combi flavour into the problem? Like, a player walking around the grid, being able to choose their path."

"And no matter what path the player chooses, something must happen?"

"Yeah."

Actually, waffles are superior to donuts. When they're fresh, of course. You have to eat them right off the waffle press. Peanut, kaya, nutella... all choices are good choices. 

"Let's stick with the simplest possible freedom of choice: start at the origin, and move either up or right each time."

"But the grid is finite, so the player can always eventually explore every single path."

"You're right... so maybe the player has to avoid certain squares or values, like mines."

For context, mines are explosives that go off when people step on them. Or if you click on them, if you were playing Minesweeper. Did you know that mines are typically calibrated for human weight, so animals or debris won't trigger them? It's kinda crazy how much precision engineering has gone into designing maximally destructive technologies.

"But then why would the specific values in the cell matter at all?"

"You're right... maybe the player has to try not to collect all residues mod $p$?"

"Like they have to step on a minimum number of distinct values, or something."

"Mm."

They stared at the still empty grid on the whiteboard. The silence gave their brains space to process and wander. I'm sure some of the best ideas in history were born this way. Like cookie dough ice cream.

"Aha!"

"What is it?"

"Ok so... hear me out... let's say the grid has an extra symmetry. So like maybe the player takes a path from the bottom left corner, leaving the square along the top edge."

A line was carelessly drawn across the still unpopulated grid.

"But it is also the same path of numbers from the top left corner to the right edge."

A second line was drawn. They crossed at some point in the grid. The lines had no choice but to cross each other, like strands of wanton noodles, or a game of Hex.

"Hmm... so the two paths must intersect."

"Exactly."

"And they share the same value at the intersection."

"Yeah. And that could be related to the ultimate goal of the problem, that something must happen regardless of whatever path the player takes."

"Okay, so a grid with a rotational symmetry... $f(x,y) = f(y,p-x)$?"

"Something like that. But to avoid having the same value twice is kind of useless, since there are only finitely many possible values anyway..."

"Should we remove the mod $p$ then?"

"But that would destroy the torus."

"Yeah..."

Such are the precious moments in problem-setting: when a rough but fresh idea is found, and it doesn't work instantly, but there's clearly so much potential and depth behind it. Topology manifesting naturally in an olympiad problem? At this point, the idea itself had taken the reins; the pair were but mere vessels to its awakening. 

It was time to tinker and tweak.

"Wait! What if, one path is negative of the other?"

"So, $f(x,y) = - f(y,p-x)$?"

"Yes. So then where they intersect..."

"The values are negative to each other!"

"So they sum to zero."

Something was definitely brewing now, like a witch's cauldron, but with math instead of frogs.

"Okay, so what polynomials work?"

"Well, linear is boring; let's try quadratic."

 The blank slate has served its purpose; it's finally time to fill in the grid. 

"So let $f(x,y) = ax^2+bxy+cy^2$, say."

"Now $f(y,-x) = ay^2-bxy+cx^2$, which we insist to be $= -(ax^2+bxy+cy^2)$."

"Compare coefficients... so $a+c = 0$ and $b$ can be anything."

"That's great... and we can scale mod $p$, so let's set $a=1$. So $f(x,y) = x^2+bxy-y^2$."

"Um... that's kind of ugly."

Indeed, problem aesthetics is equally important to mathematical content. No one wants to solve an ugly problem. An ugly donut is still fine though, as long as its not those plain sugar ones. 

"That's okay, we still can choose $b$... so we can change coordinates so that there are only two non-zero terms."

"What do you mean?"

"Well, like... $(x+y)^2-2y^2$. So $b=2$, I guess."

"Let's give it a name: $n = x+y$. So $n$ always goes up by one with the path, but $y$ either stays the same or goes up by one. That's the choice that the player can make, that corresponds to moving up or right in the original $(x,y)$ coordinates."

"Exactly."

"Okay, so we have a proper problem! Let me write it down..."

(version 1) Let $y_0, y_1,y_2,\dots$ be a sequence with $y_0=0$ and $y_{i+1} = y_i$ or $y_i+1$ for each $i$. Prove that two values in the sequence $(n^2-2y_n^2)_{n=1,2,\dots}$ sum to a multiple of $p$.

"Wow, that's pretty cool. I mean, it's still ugly as is... but it's kinda cool how there's no reference to the grid at all."

"Yeah, and there's nothing special about $p$! Mod $N$ for any $N$ would work."

"You're right."

"And you don't have to start at the origin, since its a torus... the paths must still always intersect."

"Really?"

More grids and lines were doodled on the board, like cross-hatching in anime fanart.

"Ahh... so if I start anywhere on the $(x,y)$-grid and move until I'm either $1000N$ to the right or above where I started, then I can use the rotational symmetry to turn the path $90^\circ$, with all values negated; then I can use the translations of the torus to force an intersection."

"Exactly. It's beautiful."

"So $y_0$ can be anything!"

"And also, let's reverse the sign of $n^2-2y_n^2$, so that the positive coefficient is on the variable."

"Oh... yeah whatever, doesn't matter to me."

(version 2) Let $N$ be a positive integer, and $y_1,y_2,\dots$ a sequence of integers with $y_{n+1}-y_n \in \{0,1\}$ for all $n$. Prove that there are distinct positive integers $m,n$ such that $(2y_n^2-n^2) + (2y_m^2-m^2)$ is a multiple of $N$.

"It's missing the element of a game though. We initially had the player choosing to go up or right with their path, but now it's just an arbitrary sequence. Kinda contrived, don't you think?"

"I don't know... don't you think it's cleaner this way?"

"Let's try a stylistically different version."

(version 3) Alice starts out with some coins in a box. On the $n$-th minute (for $n=1,2,3,\dots$), she can choose to put an additional coin into the box or do nothing, and then she writes the number $2c^2-n^2$ on the board where $c$ is the number of coins in the box. Show that for any positive integer $m$, there will eventually be two numbers on the board that sum to a multiple of $m$.

"Yeah... I don't know. I kind of prefer the sequence version."

"I prefer the personified version."

They then drew our compasses and battled viciously, no holds barred. Galois would have been proud. 

"Okay whatever, we'll decide later. But let's see if there's a purely number-theoretic proof first. Some quadratic reciprocity nonsense or something that destroys the problem." 

"Yeah, and meanwhile I'll explore other polynomials, like cubics, to see if there are other polynomials with this symmetry which still have a clean presentation."

"Okay."

They got to work like an oreo milkshake in a blender. A few minutes later...

"So if one takes $m$ to be a prime $p$ for which $-1$ is not a quadratic residue, say $p=7$, then no two non-zero residues sum to a multiple of $p$. But one still can't write down $0$ on the board twice... anyway, I also wrote out the grid for $m=11$, and found paths which only have problems where it intersects the rotated copy of itself. Seems like there's probably no number theory hack. The problem's solid from this angle."

"Odd-degree polynomials don't work, and for even degrees... well, does $n^6-30c^4(n-c)^2-2c^6$ look nice to you? There seems to be nothing as clean as $2c^2-n^2$."

"Okay, I think it's time to call it a day. I think we set a decent problem."

"Yeah, we're pretty good at this. They should really pay us."

"Anyway, time for dinner."

Yes, time for dinner.

----------

Disclaimer: the above narrative has been heavily dramatised, to compensate for the author's poor memory. 

Afterword: with the help of test-solvers, other perspectives came to light: intersection theory on a torus (i.e. actually closing up paths into loops), and that the symmetry arose from the number field norm $n^2-2c^2 = N(n+\sqrt 2c)$, with $1\pm \sqrt 2$ being a unit in $\mathbb Z[\sqrt 2]$ with norm $-1$. 

The problem ultimately did not make it to the IMO/shortlist; instead, it was Q5 in this year's SMO, sitting behind a past shortlist question. 

Alice eventually stopped putting coins into the box after she realised she was funding someone else's slot machine addiction. She returned to her old job, trying to send messages securely to Bob.