2017 Canadian Senior
Mathematics Contest
Solutions

The following table shows how Joe can win the game in three turns:

On Joe’s first turn, he turns over the first 4 cards.
On Joe’s second turn, he turns over cards 2 through 5.
On Joe’s third turn, he turns over the four red cards.

There are many sequences of moves in which Joe can win.
Suppose that Joe takes 9 turns. On turn 1, he turns over cards 1, 2, 3, 4, 5. On turn 2, he turns over cards 2, 3, 4, 5, 6.
He continues in this way so that, on each turn, he turns over five consecutive cards starting with the \(t\)th card on turn \(t\), with the understanding that card 1 comes after card 9. This means, for example, that on turn 7, Joe turns over cards 7, 8, 9, 1, 2.
In this way, each of the 9 cards is turned over 5 times (once as each of the 1st, 2nd, 3rd, 4th, 5th card in the sequence).
Since each card is turned over an odd number of times, its final colour is the opposite of the starting colour, and so it is green.
We demonstrate this in the following chart:

Joe can actually finish in as few as three turns:

Suppose that \(n=2017\). This means that Joe has 2017 cards.
We show that Joe can win the game when \(k\) is odd and cannot win the game when \(k\) is even.
Suppose that \(k\) is odd.
Suppose that Joe takes 2017 turns.
For each \(t=1,2,3,\ldots,2016,2017\), Joe turns over the \(k\) cards starting at card \(t\), and with the understanding that card 1 comes after card 2017.
In this way, each of the 2017 cards is turned over \(k\) times, once for each “position” in a sequence of \(k\) consecutive cards.
Since \(k\) is odd, then the colour of each of the 2017 cards is reversed at the end, and so each is green.
In this way, Joe wins the game when \(k\) is odd.
Suppose that \(k\) is even.
For Joe to win the game, each of the 2017 cards must be turned over an odd number of times in order to reverse its colour.
This means that the total number of card flips is odd, since this total is the sum of 2017 odd integers (the number of flips for each of the 2017 cards).
For any positive integer \(t\), after \(t\) turns, Joe has flipped a total of \(tk\) cards (\(k\) on each of \(t\) turns).
Since \(k\) is even, then \(tk\) is even.
Therefore, after any number of turns, the total number of card flips is always even and so cannot be the odd number of flips necessary to reverse the colour of all of the cards.
Therefore, when \(k\) is even, Joe cannot win the game.
In summary, when \(n=2017\), Joe can win the game for all odd \(k\) with \(1 \leq k < 2017\) and cannot win the game for all even \(k\) with \(1 \leq k < 2017\).

Continuing to substitute values of \(n\) back into \(f(n)\), we obtain: \[\begin{aligned} n=2: \qquad f(f(2)) & = f(2)+3\cdot 2 \\ f(5) & = 5 + 6 = 11 \\[3mm] n=5: \qquad f(f(5)) & = f(5)+3\cdot 5 \\ f(11) & = 11 + 15 = 26 \\[3mm] n=11: \qquad f(f(11)) & = f(11)+3\cdot 11 \\ f(26) & = 26 + 33 = 59\end{aligned}\] Therefore, \(f(26)=59\).

We show that there is no such function \(g\) by using the given information to derive two different outputs for a single input, which will give a contradiction of the important property of a function that there is only one output for a given input.
At each step, we use values of \(m\) and \(n\) for which we already know the values of \(g(m)\) and \(g(n)\), which limits our options at each step.
Assume that there exists a function \(g\) with \(g(1)=2\) and \(g(g(n)+m)=n+g(m)\).

• If \(n=1\) and \(m=1\), then \(g(g(1)+1)=1+g(1)\) or \(g(2+1)=1+2\) and so \(g(3)=3\).

• If \(n=1\) and \(m=3\), then \(g(g(1)+3)=1+g(3)\) or \(g(2+3)=1+3\) and so \(g(5)=4\).

• If \(n=3\) and \(m=1\), then \(g(g(3)+1)=3+g(1)\) or \(g(3+1)=3+2\) and so \(g(4)=5\).

• If \(n=3\) and \(m=2\), then \(g(g(3)+2)=3+g(2)\) or \(g(3+2)=3+g(2)\).
  Since \(g(5)=4\), then \(4=3+g(2)\) or \(g(2)=1\).

• If \(n=2\) and \(m=4\), then \(g(g(2)+4)=2+g(4)\) or \(g(1+4)=2+5\) and so \(g(5)=7\).

Since \(g(5)=4\) and \(g(5)=7\), we have a contradiction.
Therefore, there does not exist such a function \(g\).

Solution 1
First, we show that the function \(h(n)=n+1\) for each positive integer \(n\) satisfies the conditions.
We note that this function satisfies the first two conditions.
Thus, if \(h(n)=n+1\) for each positive integer \(n\), \[h(h(n)+m)=h(n+1+m)= (n+1+m)+1 = n+m+2\] and \[1+n+h(m) = 1+n+m+1 = n+m+2\] and so the third condition is satisfied.
Next, we show that there is no other such function.
Suppose that the function \(h\) satisfies the three conditions and that \(h(1)=k\).
Step 1: Show that \(h(a+rk)=h(a)+2r\) for each integer \(r \geq 1\)
Using the functional equation with \(n=1\) and \(m=a\), we obtain \(h(h(1)+a)=1+1+h(a)\) or \(h(a+k)=h(a)+2\).
Using the functional equation with \(n=1\) and \(m=a+k\), we obtain \[h(h(1)+a+k) = 1+1+h(a+k)\] or \(h(a+2k)=2+h(a)+2=h(a)+4\).
Using the functional equation with \(n=1\) and \(m=a+2k\), we obtain \[h(h(1)+a+2k) = 1+1+h(a+2k)\] or \(h(a+3k)=2+h(a)+4=h(a)+6\).
Assume that \(h(a+(r-1)k)=h(a)+2(r-1)\) for some integer \(r \geq 2\).
Using the functional equation with \(n=1\) and \(m=a+(r-1)k\), we obtain \[h(h(1)+a+(r-1)k) = 1+1+h(a+(r-1)k)\] or \(h(a+rk)=2+h(a)+2(r-1)=h(a)+2r\).
Step 2: Show that if \(h(b)=h(c)\), then \(b=c\)
In other words, we show that the function \(h\) is one-to-one.
Suppose that \(h(b)=h(c)\).
Then for each positive integer \(d\), \(h(h(b)+d)=1+b+h(d)\) and \(h(h(c)+d) = 1+c+h(d)\).
Since \(h(b)=h(c)\), then \(h(h(b)+d)=h(h(c)+d)\) and so \(1+b+h(d)=1+c+h(d)\) or \(b=c\).
Step 3: Show that \(k \leq 2\)
From Step 1, \(h(a+rk)=h(a)+2r\) for all positive integers \(a\) and \(r\).
Suppose that \(k \geq 3\).
When \(a=1\), we obtain \(h(1+rk)=h(1)+2r\) for each positive integer \(r\).
The values of \(h\) here form an infinite set of positive integers starting with \(h(1)+2\) which are spaced 2 apart.
When \(a=2\), we obtain \(h(2+rk)=h(2)+2r\) for each positive integer \(r\).
The values of \(h\) here form an infinite set of positive integers starting with \(h(2)+2\) which are spaced 2 apart.
When \(a=3\), we obtain \(h(3+rk)=h(3)+2r\) for each positive integer \(r\).
The values of \(h\) here form an infinite set of positive integers starting with \(h(3)+2\) which are spaced 2 apart.
Since \(k \geq 3\), then the inputs in these three sets are all distinct, since those in the first family give remainder 1 when divided by \(k\), those in the second family give remainder 2 when divided by \(k\), and those in the third family give remainder 3 (or possibly 0 if \(k=3\)).
But the three sets of outputs \(h(1)+2r\), \(h(2)+2r\), \(h(3)+2r\) must overlap eventually, as there can be only two disjoint infinite sets with common difference 2.
This is a contradiction, so we cannot have \(k \geq 3\), which means that \(k \leq 2\).
Step 4: Show that \(k=2\)
We know that \(k=1\) or \(k=2\).
If \(h(1)=k=1\), the equation \(h(1+rk)=h(1)+2r\) becomes \(h(1+r)=1+2r\).
Substituting \(n = 1+r\) (or \(r = n-1\)) gives \(h(n)=1+2(n-1)=2n-1\).
In this case, \[h(h(n)+m)=h(2n-1+m)= 2(2n-1+m)-1 = 4n+2m-3\] and \[1+n+h(m) = 1+n+2m-1 = n+2m\] These two expressions are not always equal for all \(n\) and \(m\) (for example, when \(n=m=2\)).
Therefore, we cannot have \(k=1\). Thus, \(k=2\).
Step 5: \(h(n)=n+1\) when \(n\) is odd
From \(h(1+rk)=h(1)+2r\) and \(k=2\), we obtain \(h(1+2r)=2+2r=(2r+1)+1\) and so \(h(n) = n+1\) when \(n\) is odd.
Step 6: \(h(n)=n+1\) when \(n\) is even
From \(h(2+rk)=h(2)+2r\), we obtain \(h(2+2r)=h(2)+2r\).
If we can show that \(h(2)=3\), then we will obtain \(h(2+2r)=3+2r\) as required.
Since \(h(x)\) is even when \(x\) is odd and since \(h\) is one-to-one, then \(h(x)\) must be odd when \(x\) is even.
In particular, \(h(2)\) is odd.
From \(h(h(n)+m)=1+n+h(m)\) with \(n=2\) and \(m=1\), we get \(h(h(2)+1)=1+2+h(1)\) and so \(h(h(2)+1)=5\).
When \(n\) is even, the values of \(h(n)\) form an increasing sequence of odd positive integers.
This is because \(h(2)\) is odd and so \(h(2)+2r\) is odd and increasing as \(r\) increases, and so \(h(2+2r)=h(2)+2r\) is odd and increasing as \(r\) increases.
Therefore, \(h(h(2)+1)=5\) has to be the third smallest, or second smallest, or smallest value of \(h(n)\) when \(n\) is even.
Since \(h(2+2r)=h(2)+2r\), then the values of \(h(x)\) when \(x\) is even increase when \(x\) increases by 2.
This means that we must have \(h(6)=5\) or \(h(4)=5\) or \(h(2)=5\).
If \(h(6)=5\), then \(h(h(2)+1)=5\) gives \(h(2)+1=6\) or \(h(2)=5\), which cannot be the case, since \(h\) is one-to-one.
If \(h(2)=5\), then \(h(h(2)+1)=5\) gives \(h(2)+1=h(2)\) which cannot be the case.
Therefore, \(h(4)=5\) and so \(h(2+2)=h(2)+2\) which gives \(h(2)=5-2=3\).
We have shown that the function \(h(n)=n+1\) satisfies the given condition and that no other function does, as required.

Solution 2
Let \(h\) be a function that satisfies the given properties, and consider the infinite set of lattice points of the form \((m,h(m))\), for \(m=1,2,3,\ldots\).
Let \(a\) be a positive integer.
When \(n=a\) and \(m=h(a)\), the functional equation is \(h(h(a)+h(a))=1+a+h(h(a))\) or \(h(2h(a))=1+a+h(h(a))\).
Thus, the point \((2h(a),1+a+h(h(a)))\) is on the graph of \(y=h(x)\).
When \(n=a\) and \(m=2h(a)\), the functional equation becomes \[h(h(a)+2h(a))=1+a+h(2h(a))\] or \(h(3h(a))=1+a+1+a+h(h(a))=2+2a+h(h(a))\).
Thus, the point \((3h(a),2+2a+h(h(a)))\) is on the graph of \(y=h(x)\).
Suppose that \(r\) is a positive integer and assume that \(h(rh(a))=(r-1)+(r-1)a+h(h(a))\).
When \(n=a\) and \(m=rh(a)\), the functional equation becomes \[h(h(a)+rh(a))=1+a+h(rh(a))=1+a+(r-1)+(r-1)a+h(h(a))=r+ra+h(h(a))\] or \(h((r+1)h(a))=r+ra+h(h(a))\).
Thus, if the point \((rh(a),(r-1)+(r-1)a+h(h(a)))\) is on the graph of \(y=h(x)\), then the point \(((r+1)h(a),r+ra+h(h(a)))\) is on the graph of \(y=h(x)\).
This shows that the infinite set of points of the form \((sh(a),(s-1)+(s-1)a+h(h(a)))\) for integers \(s \geq 2\) all lie on this graph.
Note that to get from one point in this set to the next, we move \(h(a)\) units to the right and \(a+1\) units up.
In other words, this infinite set of points on the graph forms a line with slope \(\dfrac{a+1}{h(a)}\).
Call this line \(L_a\).
Suppose that \(b\) is a positive integer with \(b \neq a\).
A similar argument shows that the set of points \((th(b),(t-1)+(t-1)b+h(h(b)))\) for integers \(t \geq 2\) all lie on this graph, which thus form a line \(L_b\) with slope \(\dfrac{b+1}{h(b)}\).
Now consider the points \((n,h(n))\) on the graph of \(y=h(x)\) where \(n\) is a positive integer that is a multiple of \(h(a)\) and is also a multiple of \(h(b)\).
There are infinitely many such points (for example, \(n=wh(a)h(b)\) for positive integers \(w\)).
These points lie on both \(L_a\) and \(L_b\), and so the slopes of these two lines must be equal.
But this is true for every possible pair of distinct positive integers \(a\) and \(b\).
Therefore, the quantity \(\dfrac{a+1}{h(a)}\) must be constant for all positive integers \(a\). (Another way to see this is to let \(a=1\) and let \(b\) range through all positive integers greater than 1.)
In other words, \(\dfrac{a+1}{h(a)} = \dfrac{1}{c}\) for some constant \(c\) or \(h(a)=ca+c\) for all positive integers \(a\).
If \(a=1\), then \(h(1)=c+c=2c\).
Setting \(n=m=1\) in the equation \(h(h(n)+m)=1+n+h(m)\), we obtain \(h(h(1)+1)=1+1+h(1)\) which gives \(h(2c+1)=2+2c\).
Since \(h(a)=ca+c\), then setting \(a=2c+1\) gives \(c(2c+1)+c=2+2c\) or \(2c^2+2c=2+2c\) and so \(c^2=1\).
Since \(c>0\), then \(c=1\) and so \(h(n)=n+1\).
(Solution 1 shows us that the function \(h(n)=n+1\) does satisfy the requirements.)