# Haydn and Beethoven are celebrating Mozart's birthday

They decided the following game is suitable to the occasion:
taking alternating turns they say numbers, keeping the following rules:

• In the first turn, Haydn says the number $2$.
• After that, the player on turn says a number which is either the sum or the product of two (not necessarily distinct) previously appeared numbers.
• The number which he says should differ from all the previously mentioned ones, and cannot be greater than $1756$.

For clarification: as a second move, Beethoven can say only $4$, which can be composed as $2+2$ or $2\times2$. After that, Haydn has a real choice answering either $6$ ($2+4$), $8$ ($4+4$ or $2\times4$), or $16$ ($4\times4$).

The winner is the one that says $1756$ - the birthyear of Mozart.
Which of the two players has a winning strategy?

I'm not the original author of this puzzle. It was a problem more than 10 years ago at a mathematics competition for Hungarian high school students.

Furthermore, I'll reward an additional 50-point bounty for a general answer, that is determining the winning player and strategy if the target number (and also the upper limit of numbers) is $n$.

• I'm not a native English speaker. If my grammar and words are vague, don't hesitate to ask or even edit the question to improve it. Also it is my first question here, so every feedback is welcome. Thanks! – elias Jul 26 '16 at 13:30

Because $1756=2\cdot2\cdot439$, we see that a player can win if and only if two numbers from one of the following sets are picked: $\{2, 1754\}, \{4, 1752\},\dots,\{876,880\}$, or 878 is picked.

Since there are $438$ sets, if a number from every set is eventually picked, Haydn will be forced to pick 878 or one number from an already selected set and lose. So as long as Beethoven can always move into a non-previously selected set, he will win. Let's prove that Haydn can't stop him.

Beethoven's strategy is to always pick the smallest $2n$ such that none of $\{2n, 1756-2n\}$ have been picked yet. We can see $2n$ can be formed in $\lfloor \frac{n}{2} \rfloor$ ways ($2 + (2n-2)$, $4 + (2n-4)$, ...).

But Haydn has at most $\lfloor \frac{n}{2} \rfloor - 1$ moves available to block sets from Beethoven before he gets to $2n$. That's not enough to block all pairs, so Haydn can never stop Beethoven from following his strategy.

A fun fact is that this proof also shows that Haydn could have the ability to pick any number from any set and he still would lose. As for Beethoven, he doesn't even need his multiplication option!

• can you please clarify the part about what is a blocking move? I'm not sure I get it right. thanks in advance! – elias Jul 26 '16 at 22:24
• @elias Note that because Beethoven goes from the sets from low to high, for every 2m smaller than 2n, either 2m or 1756-2m has already been selected. Blocking move is picking the "large" element of a set (1756-2m) so Beethoven can't use 2m to form the sums he wants. – ffao Jul 26 '16 at 23:07
• thanks, this is clear now. but I still have a question: why is the number of blocking moves at most floor(n/2)-1? – elias Jul 26 '16 at 23:11
• @elias The first two sets cannot be blocked (because 2 and 4 are forced moves). For every one of the remaining sets that Haydn blocks, Beethoven will make a set unblocked, meaning Haydn can only block at most half of the remaining sets. – ffao Jul 26 '16 at 23:38
• great answer! sounds correct, and now it is detailed enough for me to understand all your explanation. – elias Jul 26 '16 at 23:59

I haven't done a complete analysis but here are my thoughts. All numbers played are even positive integers. $1756=2\cdot2\cdot439$, so there isn't any danger in playing a number which allows your opponent to reach $1756$ by multiplication -- the only number that could help is $878=2\cdot439$. But if $878$ has been played, $1756$ can be reached as $878+878$ anyway. So $1756$ will be reached by addition. So the players think of the numbers as being grouped into the following sets: $\{2, 1754\}, \{4, 1752\},\dots,\{876,880\},\{878\}$, and never take from a set that has previously been played from. There are $439$ such sets. Haydn took the 1st move, and will thus take the 439th, letting Beethoven win. The game might go H:2, B:4,..., H:878, B:1756.

• I think the game can go on forever since once the numbers get big enough, you can always avoid saying the second number in a pair. – Trenin Jul 26 '16 at 14:35
• @Trenin Each number played cannot be greater than 1756. – Rosie F Jul 26 '16 at 14:36
• Right... didn't see that part. – Trenin Jul 26 '16 at 14:41
• I think this is a good direction, but some details need to be addressed. Is it possible for Haydn to somehow make some of the sets totally unplayable, i.e. no number of the yet unused sets can be composed as product or sum after an earlier move? – elias Jul 26 '16 at 14:44

As there is still no post that attempts to answer the generalized version, and the bounty period is at halftime, I'm showing a possible direction towards the solution.

As I mentioned in the bounty, it is obvious that the question makes sense only for a positive even $n$.
The general answer has two cases which are quite different.

1st case:

If $n$ is not divisible with $4$.
This is easier than the already discussed example of $1756$, as in this case $n$ cannot be composed as a product of two even numbers. The only way someone can reach it is via addition.
Again, there are some pairs of numbers that being summed together give $n$. Both player should avoid saying a number from a pair where the other number was already told.
It is worth to mark down these pairs, however, I suggest using a different representation than the one that was used by RosieF and ffao: I recommend to draw a graph, where the nodes are the even numbers from $2$ to $n-2$, and two of them are connected if they sum up to $n$. (This representation is a little hint towards the 2nd case.)
Our representation will look like this:

     2 --- n-2
4 --- n-4
6 --- n-6
...
n/2-1 --- n/2+1

Note that there are $\frac{n-2}4$ pairs, so if there can be one number chosen from every pair, the winner can be determined based on the parity of this number, i.e. if $n=8k+6$ for some integer $k$, Haydn has this kind advantage, for $n=8k+2$, Beethoven has - the only exception being $n=2$, where the forced move allows Haydn to say $2$, even if it cannot be composed as sums of previous numbers.
The reasoning in ffao's answer works: the one with the advantage can make the game to reach a point, where one number from every pair will be said if he keeps saying the lowest possible number which is not connected to any already said number.

2nd case:

If $n$ is divisible with $4$.

I'll still leave this part open, and will award the bounty to the one that answers it correctly.