Term 1 Week 8 Senior Problems
Problem 1
The numbers $1,2,3,\dots,2017$ are on the blackboard. Amelie and Boris take turns removing one of those until only two numbers remain on the board. Amelie starts. If the sum of the last two numbers is divisible by $8$, then Amelie wins. Else Boris wins. Who can force a victory?
Click to show solution
Solution 1
Amelie can force a victory. For the first number, she chooses 2017. After that, there are 252 numbers 1 mod 8, 2 mod 8, 3 mod 8, 4 mod 8... left.Then, whatever number Boris chooses, Amelie chooses the complement of Boris's number (Where the C(1) = 7, C(2) = 6, C(3) = 5, C(4) = 4, and C(8) = 8.)
Since there are an even number of elements for each complement, Amelie can use this strategy until the last two numbers. Furthermore, the last two numbers will be complements of each other, and their sum will be divisible by each other.
Solution 2
I think Amelie wins. First she removes $2017$ and now the "new game" is given the numbers $1,2,3,\dots,2016$, Boris starts and the winning conditions are the same.Divide the 2016 numbers into groups of 8 of the form $\{8k-7, 8k-6, \dots, 8k\}$ for each $k= \overline{1,252}$.
Now for each number $b$ Boris chooses, Amelie chooses the number $a$ such that $a \equiv -b \mod 8$ and both $a$ and $b$ are inside the same group. Notice that Amelie can do this whenever $b$ is different from $0,4 \mod 8$. In that case Amelie can just choose a number with the same properties as above, however in that case from a different group. Since the number of groups is even, Amelie can always do this.
Problem 2
Rosalind wants to join the Stepney Chess Club. In order to be accepted, she must play a
challenge match consisting of several games against Pardeep (the Club champion) and Quentin
(the Club secretary), in which she must win at least one game against each of Pardeep and
Quentin. From past experience, she knows that the probability of her winning a single game
against Pardeep is $p$ and the probability of her winning a single game against Quentin is $q$,
where $0 < p < g < 1$.
The challenge match consists of three games. Before the match begins, Rosalind must
choose either to play Pardeep twice and Quentin once or to play Quentin twice and
Pardeep once. Show that she should choose to play Pardeep twice.
Note: “she must win at least one game against each of Pardeep and Quentin” means that she needs to beat both opponents for at least one game.
Click to show solution
Solution
$\mathrm{P}\left(\mathrm{W}_{\mathrm{PPQ}}\right)=\mathrm{P}\left(\mathrm{W}_{\mathrm{P}} \mathrm{W}_{\mathrm{Q}}-\right)+\mathrm{P}\left(\mathrm{L}_{\mathrm{P}} \mathrm{W}_{\mathrm{Q}} \mathrm{W}_{\mathrm{P}}\right)=p \cdot q .1+(1-p) q p=p q(2-p)$.Similarly, $\mathrm{P}\left(\mathrm{W}_{\mathrm{PQQ}}\right)=p q(2-q)$ and $\mathrm{P}\left(\mathrm{W}_{\mathrm{PPQ}}\right)-\mathrm{P}\left(\mathrm{W}_{\mathrm{PQQ}}\right)=p q(q-p)>0$ since $q>p$. Thus, $\mathrm{P}\left(\mathrm{W}_{\mathrm{PPQ}}\right)>\mathrm{P}\left(\mathrm{W}_{\mathrm{PQQ}}\right)$ for all $p, q$ and "Ros plays Pardeep twice" is always her best strategy.
Problem 3
Prove that $x^2 + y^2 + 1 = z^2$ has infinitely many solutions.
Click to show solution
Solution
$(2m^2 + 1)^2 = 4m^4 + 4m^2 + 1$ $x^2 = 4m^4$ $y = 4m^2$ As $m$ could be any integer, there are infinitely many solutions.Problem 4
Click to show solution
Solution
