AUT_ABooklet_2020

We construct a bijection between possible combinations in Oddland and possible combinations in Squareland. Suppose we have a combination of Squareland stamps that sum to $n$ cent, consisting of $a_1$ stamps of value $1$ cent, $a_2$ stamps of value $4$ cent, ..., $a_M$ stamps of value $M^2$ cent, so that $$n=\sum _{k=1}^M{k}^2{a}_k.$$ Now we express $k^2$ as ${\sum }_{j=1}^k(2j-1)$ and interchange the order of summation, which yields $$n=\sum _{k=1}^M\sum _{j=1}^k(2j-1)a_k=\sum _{j=1}^M(2j-1)\sum _{k=j}^M{a}_k.$$ This gives us a possible combination of Oddland stamps: By setting $b_j={\sum }_{k=j}^M{a}_k$, we have $$n=\sum _{j=1}^M(2j-1)b_j.$$ This can be interpreted as a collection of $b_1$ stamps of value $1$ cent, $b_2$ stamps of value $3$ cent, ..., $b_M$ stamps of value $(2M-1)$ cent. We have $b_1\ge b_2\ge \cdots \ge b_M$ by definition, so this is a legal combination in Oddland.

Conversely, if a combination in Oddland is given by the values $b_1,b_2,\dots ,b_M$, we can use the identities $a_1=b_1-b_2,a_2=b_2-b_3,\dots ,a_{M-1}=b_{M-1}-b_M,a_M=b_M$ to recover the corresponding combination in Squareland. (Note that these values are nonnegative whenever $b_1\ge b_2\ge \cdots \ge b_M$.)

Since these two operations obviously are inverse to one another, we have found a bijection, which proves the statement.