The answer is if $a=b$ or $a=-b$. In the former case, one can take $f(x) \equiv x+a$ and $g(x) \equiv x$. In the latter case, one can take $f(x) \equiv -x+a$ and $g(x) = -x$. Now we prove these are the only possibilities. First: Claim: The functions $f$ and $g$ are bijections. Proof. Surjectivity is obvious. To see injective, note that if $f(u) = f(v)$ then $g(f(u)) = g(f(v)) \implies u+b = v+b \implies u=v$, and similarly for $g$. $\blacksquare$ Note also that for any $x$, we have \begin{align*} f(x+b) &= f(g(f(x))) = f(x) + a \\ g(x+a) &= g(f(g(x))) = g(x) + b. \end{align*}If either $a$ is zero or $b$ is zero, we immediately get the other is zero, and hence done. So assume $ab \ne 0$. If $|b| > |a|$, then two of \[ \{ f(0), f(1), \dots, f(b-1) \} \pmod a \]coincide, which together with repeatedly applying the first equation above will then give a contradiction to injectivity of $f$. Similarly, if $|a| > |b|$ swapping the roles of $f$ and $g$ (and $a$ and $b$) will give a contradiction to injectivity of $g$. This completes the proof. Remark: Here is a way to visualize the argument, so one can see pictorially what is going on. We draw two parallel number lines indexed by ${\mathbb Z}$. Starting from $0$, we draw red arrow from $0$ to $f(0)$, and then a blue arrow from $f(0)$ to $g(f(0)) = b$, and then a red arrow from $b$ to $g(b) = f(0)+a$, and so on. These arrows can be extended both directions, leading to an infinite ``squaretooth'' wave. The following is a picture of an example with $a,b > 0$. [asy][asy] size(11cm); usepackage("amsmath"); usepackage("amssymb"); draw( (-3,2)--(13,2), Arrows(TeXHead) ); draw( (-3,-2)--(13,-2), Arrows(TeXHead) ); label("$\mathbb Z$", (13, 2), dir(0)); label("$\mathbb Z$", (13, -2), dir(0)); pair bm1 = (-5,2); pair b0 = (0,2); pair b1 = (5,2); pair b2 = (10,2); pair b3 = (15,2); pair am1 = (-1,-2); pair a0 = (2.5,-2); pair a1 = (6,-2); pair a2 = (9.5,-2); pair a3 = (13,-2); dot("$0$", b0, dir(90)); dot("$b$", b1, dir(90)); dot("$2b$", b2, dir(90)); dot("$f(0)-a$", am1, dir(-90)); dot("$f(0)$", a0, dir(-90)); dot("$f(0)+a$", a1, dir(-90)); dot("$f(0)+2a$", a2, dir(-90)); draw(midpoint(bm1--am1)--am1, red, EndArrow, Margins); label("$f$", midpoint(bm1--am1)--am1, dir(50), red); draw(b0--a0, red, EndArrow, Margins); label("$f$", b0--a0, dir(50), red); draw(b1--a1, red, EndArrow, Margins); label("$f$", b1--a1, dir(50), red); draw(b2--a2, red, EndArrow, Margins); label("$f$", b2--a2, dir(50), red); draw(am1--b0, blue, EndArrow, Margins); label("$g$", midpoint(am1--b0)--b0, dir(-50), blue); draw(a0--b1, blue, EndArrow, Margins); label("$g$", a0--b1, dir(-50), blue); draw(a1--b2, blue, EndArrow, Margins); label("$g$", a1--b2, dir(-50), blue); draw(a2--midpoint(a2--b3), blue, EndArrow, Margins); label("$g$", a2--midpoint(a2--b3), dir(-50), blue); [/asy][/asy] The problem is essentially trying to decompose our two copies of ${\mathbb Z}$ into multiple squaretooth waves. We expect for this to be possible, the ``width'' of the waves on the top and bottom must be the same --- i.e., that $|a| = |b|$.

My problem. The answer is $(k, k)$ and $(-k, k)$ for all $k$. These work by taking $\big(f(x), g(x)\big) = (x, x + k)$ and $\big(f(x), g(x)\big) = (-x, -x + k)$. Now we show that $|a| = |b|$ in any valid pair. It is clear that $a = 0$ iff $b = 0$, so we only focus on the case where neither is zero. Note that $f$ is bijective, and that \[f(x + b) = f\Big(g\big(f(x)\big)\Big) = f(x) + a.\]Thus $f$ maps residue classes modulo $b$ to classes modulo $a$, so we have an induced map $\hat{f}: \mathbb{Z}/b\mathbb{Z} \to \mathbb{Z}/a\mathbb{Z}$. This must also be bijective, so $|a| = |b|$ as requested.

I got |a| = |b|

@above That’s what I got.

Found $(a,b)$, and when writing the actual proof realized $(a,-a)$ also works.

do f and g have to be polynomials (do we have to prove this if it is?)

How do we know they are bijective?

shoot I never proved that it's the only possibility, would that make me lose 1 or 2 points? or get the entire proof wrong?

Wait what? The problem is proving that those are the only possibilities... proving they work is trivial

CantonMathGuy wrote: My problem. The answer is $(k, k)$ and $(-k, k)$ for all $k$. These work by taking $\big(f(x), g(x)\big) = (x, x + k)$ and $\big(f(x), g(x)\big) = (-x, -x + k)$. Now we show that $|a| = |b|$ in any valid pair. It is clear that $a = 0$ iff $b = 0$, so we only focus on the case where neither is zero. Note that $f$ is bijective, and that \[f(x + b) = f\Big(g\big(f(x)\big)\Big) = f(x) + a.\]Thus $f$ maps residue classes modulo $b$ to classes modulo $a$, so we have an induced map $\hat{f}: \mathbb{Z}/b\mathbb{Z} \to \mathbb{Z}/a\mathbb{Z}$. This must also be bijective, so $|a| = |b|$ as requested. With this solution, doesn't "modulo $b$" assume that $b>0$?

kvs wrote: Wait what? The problem is proving that those are the only possibilities... proving they work is trivial rip me, this is the first olympiad I'm doing lol.....

you cant substitute b = -b

kvs wrote: Wait what? The problem is proving that those are the only possibilities... proving they work is trivial oops that's what i thought but it took me ~30 min to find solutions because i assumed f=g so when a is odd oops

So how much would I get for forgetting to put the absolute value sign?

jj_ca888 wrote: you cant substitute b = -b Whoops. For some reason I treated it like an $x$. If we replaced $b$ with $x$, then I could substitute $x =-x$ because the FE holds over all $x$, right?

MKBHD wrote: So how much would I get for forgetting to put the absolute value sign? My best guess is a 1

AMC_Kid wrote: jj_ca888 wrote: you cant substitute b = -b Whoops. For some reason I treated it like an $x$. If we replaced $b$ with $x$, then I could substitute $x =-x$ because the FE holds over all $x$, right? right

v_Enhance wrote: The answer is if $a=b$ or $a=-b$. In the former case, one can take $f(x) \equiv x+a$ and $g(x) \equiv x$. In the latter case, one can take $f(x) \equiv -x+a$ and $g(x) = -x$. Now we prove these are the only possibilities. The conditions imply that $f$ and $g$ are bijections. Note also that for any $x$, we have \begin{align*} f(x+b) &= f(g(f(x))) = f(x) + a \\ g(x+a) &= g(f(g(x))) = g(x) + b. \end{align*}If either $a$ is zero or $b$ is zero, we immediately get the other is zero, and hence done. So assume $ab \ne 0$. If $|b| > |a|$, then two of \[ \{ f(0), f(1), \dots, f(b-1) \} \pmod a \]coincide, which together with repeatedly applying the first equation above will then give a contradiction to injectivity of $f$. Similarly, if $|a| > |b|$ swapping the roles of $f$ and $g$ (and $a$ and $b$) will give a contradiction to injectivity of $g$. This completes the proof. Remark: Here is a way to visualize the argument, so one can see pictorially what is going on. We draw two parallel number lines indexed by ${\mathbb Z}$. Starting from $0$, we draw red arrow from $0$ to $f(0)$, and then a blue arrow from $f(0)$ to $g(f(0)) = b$, and then a red arrow from $b$ to $g(b) = f(0)+a$, and so on. These arrows can be extended both directions, leading to an infinite ``squaretooth'' wave. The following is a picture of an example with $a,b > 0$. [asy][asy] size(11cm); usepackage("amsmath"); usepackage("amssymb"); draw( (-3,2)--(13,2), Arrows(TeXHead) ); draw( (-3,-2)--(13,-2), Arrows(TeXHead) ); label("$\mathbb Z$", (13, 2), dir(0)); label("$\mathbb Z$", (13, -2), dir(0)); pair bm1 = (-5,2); pair b0 = (0,2); pair b1 = (5,2); pair b2 = (10,2); pair b3 = (15,2); pair am1 = (-1,-2); pair a0 = (2.5,-2); pair a1 = (6,-2); pair a2 = (9.5,-2); pair a3 = (13,-2); dot("$0$", b0, dir(90)); dot("$b$", b1, dir(90)); dot("$2b$", b2, dir(90)); dot("$f(0)-a$", am1, dir(-90)); dot("$f(0)$", a0, dir(-90)); dot("$f(0)+a$", a1, dir(-90)); dot("$f(0)+2a$", a2, dir(-90)); draw(midpoint(bm1--am1)--am1, red, EndArrow, Margins); label("$f$", midpoint(bm1--am1)--am1, dir(50), red); draw(b0--a0, red, EndArrow, Margins); label("$f$", b0--a0, dir(50), red); draw(b1--a1, red, EndArrow, Margins); label("$f$", b1--a1, dir(50), red); draw(b2--a2, red, EndArrow, Margins); label("$f$", b2--a2, dir(50), red); draw(am1--b0, blue, EndArrow, Margins); label("$g$", midpoint(am1--b0)--b0, dir(-50), blue); draw(a0--b1, blue, EndArrow, Margins); label("$g$", a0--b1, dir(-50), blue); draw(a1--b2, blue, EndArrow, Margins); label("$g$", a1--b2, dir(-50), blue); draw(a2--midpoint(a2--b3), blue, EndArrow, Margins); label("$g$", a2--midpoint(a2--b3), dir(-50), blue); [/asy][/asy] The problem is essentially trying to decompose our two copies of ${\mathbb Z}$ into multiple squaretooth waves. We expect for this to be possible, the ``width'' of the waves on the top and bottom must be the same --- i.e., that $|a| = |b|$. Crap I was literally like 2 lines away from having a full proof...

We claim that $a = \pm b.$ When $a = b,$ take $f(x) = x$ and $g(x) = x + a.$ When $a = -b,$ take $f(x) = -x$ and $g(x) = -x-a.$ WLOG, $|a| \le |b|;$ otherwise we can swap $f$ and $g.$ Plugging in $x = f(x),$ we get $g(x+a) = g(x) + b.$ Plugging in $x = g(x),$ we get $f(x+b) = f(x) + a.$ Hence we can take the domain and codomain of $f$ mod $b$ and $a$ respectively, and vice versa for $g;$ the rest is decided for us. Therefore, our modded function $f'$ maps $\mathbb{Z}_b$ to $\mathbb{Z}_a,$ where $\mathbb{Z}_p$ denotes the integers mod $p,$ in particular $\{0,1,2,\dots, p-1\}.$ Similarly, the modded function $g'$ maps $\mathbb{Z}_a$ to $=\mathbb{Z}_b.$ However, the function $g' \circ f' \colon \mathbb{Z}_b \to \mathbb{Z}_b$ is a self-involution and hence a bijection, since $g'(f'(x)) = x$ mod $b.$ Hence the function $g'$ must have RANGE $\mathbb{Z}_b$ on that matter, and hence the size of $\mathbb{Z}_a$ is greater than or equal to that of $\mathbb{Z}_b.$ Consequently, $|a| \ge |b|,$ so $|a| = |b|.$ This means that $a = \pm b,$ as desired. I like to visualize the last paragraph with the diagram attached.

By simple induction we can get that for any $n\in\mathbb{Z_0^+}$, we have $g(i+na)=k+nb,f(k+nb)=i+a(n+1)$ for some pre determined i,k. Assume $a\neq b$, so WLOG let $a<b$. From above we can see that for any 2 numbers x,y with $x\equiv y(\mod a)$, we have $g(x)\equiv g(y)(\mod b)$. Since $a<b$ and there are only $a$ residue classes $\mod a$ but $b$ residue classes $\mod b$, we have at least 1 residue class $\mod b$ not in range of function $g(x)$. Setting $z$ to be a number in such a residue classes, we find that $g(f(z-b))=z$ is impossible, contradiction, giving that $a=b$ is reqired. Full proof here: https://infinityintegral.substack.com/p/usajmo-2019-contest-review

Cool problem, mods were nice. We claim that the only satisfactory pairs $(a, b)$ are of the form $(\pm x, \pm x)$. It is easy to check that these work. Begin by noting that both $f$ and $g$ are injective which is easy to prove from the given. Also $f(g(f(x)))$ gives $f(x + b) = f(x) + a$. Similarly we find $g(x+a) = g(x) + b$. Now assume that $\lvert a \rvert > \lvert b \rvert$. Taking $\text{mod } a$ we find, \begin{align*} f(x+b) \equiv f(x)\pmod{a}, \end{align*}which implies that $f(x)$ is periodic $\text{mod } a$ with period $b$ and that there exist $p$ and $q$ such that they are bounded between consecutive multiples of $a$ and that $f(x + p) \equiv f(x + q) \pmod{a}$. We can similarly conclude $g(x)$ is periodic $\text{mod } b$ with period $a$. In particular we have, $f(p) \equiv f(q) \pmod{a}$ $p \equiv q \pmod{b}$ $p - q < \lvert a \rvert$ However noting that $g(p+a) = p + b$ and that $g(q+a) = q + b$ we conclude that $p \equiv q \pmod{a}$ which is our desired contradiction.

We will start the solution off with a claim. Claim: $f$ and $g$ are both bijective Proof: It is obvious that $f$ and $g$ are surjective, so it suffices to prove that they are injective. If $f(x)=f(y)$, we have $x+b=g(f(x))=g(f(y))=y+b \implies x=y$. If $g(x)=g(y)$, we have $x+a=f(g(x))=f(g(y))=y+a \implies x=y$. Thus, both $f$ and $g$ are injective. $\square$ Since $g$ is bijective, it must cover all residues modulo $b$. Then, we note that if $x \equiv y \pmod a$, $g(x) \equiv g(y) \pmod b$. Thus, there are at most $a$ residues mod $b$, so $|a| \ge |b|$. Since $f$ is bijective, it must cover all residues modulo $a$. Then, we note that if $x \equiv y \pmod b$, $f(x) \equiv f(y) \pmod a$. Thus, there are at most $b$ residues mod $a$, so $|b| \ge |a|$. $\implies$ We must have $|a|=|b|$. Hence, $\boxed{b=\pm a}$. Quick check that they work: If $a=b$, $f(x)=x+a$ and $g(x)=x$ works. If $-a=b$, $f(x)=-x+a$ and $g(x)=-x$ works.

Posting for storage

cool problem We claim the answer is all $a$ and $b$ such that $|a|=|b|$. This clearly works through: \[a=b:f(x)=x, g(x)=x+a,\] \[a=-b:f(x)=-x+a ,g(x)=-x.\] Claim: Both functions are bijective. Proof: It is clear that they are surjective. We assume $f(u)=f(v)$. Then: \[g(f(u))=u+a=v+a=g(f(v)),\]so they are injective (it is the exact same approach for $g(x)$) $\square$ Now, note that: \[g(f(g(x)))=g(x+a)=g(x)+b,\]\[f(g(f(x)))=f(x+b)=f(x)+a.\]If one of $a$ or $b$ is $0$, the other must also be, so henceforth, assume $a,b\neq 0$. Basically, $g$ can be looked at modulo $a$ in its domain and modulo $b$ in its range. We can also say that $f$ can be looked at modulo $b$ in its domain and modulo $a$ in its range. FTSOC, assume $|a|>|b|$. Due to this, in $g(0),g(1),\dots,g(a-1)$, there must be two $g(u),g(v)$ such that $g(u)\equiv g(v)\pmod{|b|}$. Substituting this into the first equation, we get that there must be two $x_1,y_1$ such that $g(x_1)=g(y_1)$ and such that $x_1$ and $y_1$ are different modulo $a$. This contradicts the injectivity condition. Analogously, this does not work for $|a|<|b|$, so $|a|=|b|$, as desired $\blacksquare$.

Claim The only pairs of $(a,b)$ are $a = -b$ and $a = b$ We take $f(x) = -x+a$, $g(x) = -x$ for case 1 and $f(x) = x+a$,$g(x) = x$ for case 2. Clearly both functions are surjective as x+b can take any integer value by varying x. The function is also injective by wrapping it in $g$ and substituting in the expressions of the function to obtain equality. From this we have the equations: \begin{align*} f(x+b) &= f(g(f(x))) = f(x) + a \tag{1}\\ g(x+a) &= g(f(g(x))) = g(x) + b. \tag{2}\\ \end{align*}We now assume that $a$,$b \neq$ 0. From the two equations above it is clear that, $f$ maps residue classes from $\mod b$ to $\mod a$, implying that $|a| = |b|$, which is isomorphic to our Claim $\square$

Answer: All pairs $(a, b)$ satisfying $|a| = |b|$. Assume the contrary, $|a| > |b|$. Note that $f(x) + a = f(g(f(x))) = f(x + b)$, thus $f(x + b) = f(x) + a$. Similarly we get $g(x + a) = g(x) + b$. For every $1 \le i \le a - 1$ we have $f(g(i)) = i + a$ and since $|a| > |b|$ pigeonhole principle yields there exist $i \neq j$ such that $b \mid g(i) - g(j)$. Note that $g(i) \neq g(j)$, otherwise we get $i + a = j + a$, a contradiction. Hence $a-1 \ge |i-j| = |f(g(i)) - f(g(j))| \ge a$, a contradition. Thus $|a| = |b|$. If $a = b$, take $f(x) = x$ and $g(x) = x + a$ and if $b = -a$, then take $f(x) = -x$ and $g(x) = -x + a$. This completes proof. $\blacksquare$

The solutions are $(a,b) = (t,-t)$ and $(t,t)$ for $t\in \mathbb Z$. The construction for $(a,b) = (t,-t)$ is as follows, \[ f(x) = -x + \left\lfloor \frac{t}{2} \right\rfloor,\qquad\ g(x) = -x + \left\lfloor \frac{t+1}{2} \right\rfloor. \] The construction for $(a,b) = (t,t)$ is as follows, \[ f(x) = x + \left\lfloor \frac{t}{2} \right\rfloor,\qquad\ g(x) = x+\left\lfloor \frac{t+1}{2} \right\rfloor. \] Now we show that these are the only ones. Otherwise FTSOC assume WLOG $|b|>|a|$. Now $g(f(g(x))) = g(x) + b = g(x+a) \implies g(x+a) = g(x) + b$. Similarly $f(x+b) = f(x) + a$. Now note that $f$ and $g$ both are bijective. Also note that $a=0 \implies b=0$. So assume $a,b\neq 0$. Consider the following set, $\left\{f(b-1),f(b-2),\ldots, f(0)\right\}$. It has $|b|$ elements. So by PHP, there exists two elements with the same modulo $\pmod{a}$. Let these elements be $f(i)$ and $f(j)$. So we have $f(i) \equiv f(j) \pmod{a}$. But note that $f(i+b) = f(i)+a$ and $f(i+2b) = f(i) + 2a$. So we can generate the entire set $\left\{a\mathbb Z + f(i)\right\}$ of numbers that are $\equiv f(i) \pmod{a}$ like this. But hen we must have that $f(j) \in \left\{a\mathbb Z + f(i)\right\}$. So let $f(j) = f(i) + ka = f(i+kb)$. Now since $f$ is injective, we must have $j = i + kb\implies j\equiv i \pmod{b} \implies b\mid j - i \implies b \le |i-j|$ as $i\neq j$. Now note that $i\neq j \implies 0 < |i-j| < b$ which is a contradiction and we are done.

We claim the only solutions are $(a, b) = (t, t)$ and $(a, b) = (t, -t)$, obtained from the functions $(f(x), g(x)) = (x+1, x+t-1), (-x+1, -x-t+1)$ respectively. Now we prove $(t, t)$ and $(t, -t)$ are the only possibilities. Observe that clearly $f$ and $g$ are surjective. Also observe that $$g(f(g(x))) = g(x+a) = g(x) + b \cdots (1)$$and $$f(g(f(x))) = f(x+b) = f(x) + a \cdots (2)$$. Clearly if $a = 0$ then $b= 0$, so assume this to not be the case. Let us analyse $(1)$; particularly $$g(x+a) = g(x) + b.$$Observe that each residue of $x$ mod $|a|$ corresponds to a (not necessarily distinct) residue of $g(x)$ mod $|b|$. As $g$ is surjective, all residue classes of $g(x)$ mod $|b|$ have to be accounted for, so $|a| \ge |b|$. From similar analysis of $(2)$ we get that $|b| \ge |a|$. Therefore $|a| = |b|$, leading to the above pairs. $\square$

Hypothetically: Would proving a=b, but being an absolute idiot and neglecting: 1) a=-b 2) saying a must be even (and providing a construction for a=b=2k) give 5 points?

Yeah I think they would give 5 points.

We will show that only a = b and a = -b work. If a = b we can take $f(x) \equiv x+a$ and $g(x) \equiv x$ and if a = -b we can have $f(x) \equiv -x+a$ and $g(x) = -x$. Now we should prove these are the only ones that work. Obviously f and g are surjective since x+a and x+b go trough all values. Now we will prove that f and g are injective too. Let $f(c) = f(d)$ $\Rightarrow$ $g(f(c)) = g(f(d))$ $\Rightarrow$ c+b = d+b $\Rightarrow$ c = d $\Rightarrow$ f is injective. The same way let $g(c) = g(d)$ $\Rightarrow$ $f(g(c)) = f(g(d))$ $\Rightarrow$ c+a = d+a $\Rightarrow$ c = d $\Rightarrow$ g is injective $\Rightarrow$ we get that f and g are bijective. Now using this, we get that $f(x+b) = f(g(f(x))) = f(x) + a$ and similarly $g(x+a) = g(f(g(x))) = g(x) + b$. If a = 0, or b = 0, then a = b = 0. Since g is surjective, g covers all residues $\pmod b$. Also if $x\equiv y\pmod a$, then $g(x)\equiv g(y)\pmod b$ since if otherwise there exist k such that $k \equiv x\pmod b$ for which $f(k) = f(y)$, which violates the injectivity $\Rightarrow$ g covers max a residues $\pmod b$ $\Rightarrow$ $|a|\ge |b|$. Similarly since f is surjective, f covers all residues $\pmod a$. If $x\equiv y\pmod b$, then $f(x)\equiv f(y)\pmod a$ $\Rightarrow$ f covers max b residues $\pmod a$ $\Rightarrow$ $|b|\ge |a|$ $\Rightarrow$ by $|a|\ge |b|$ and $|b|\ge |a|$ we get that $|a|=|b|$ must be true $\Rightarrow$ a = b and a = -b are the only solutions and we showed they work so we are ready.

I initially forgot about $a = -b$

We claim that the only possible solutions are $|a|=|b|$. Note that $a=0$ iff $b=0$. Notice that: $f, g$ are injective and surjective functions. Therefore, $f, g$ are bijective functions also. Notice that: $f(g(f(x)) = f(x)+a = f(x+b)$. Thus, $f$ maps bijection from $\{0, 1 , \cdots, |b|-1 \}$ to $\{0, 1, \cdots, |a|- 1\}$. Thus: $|a|=|b|$. Extension: For $|a|=|b|=n \neq 0$, the value of $f$ is uniquely determined by $f(0), f(1), \cdots, f(n-1)$. Note that $f$ is invertible and thus: $g(x)=f^{-1}(x)+b$.