Haydn and Beethoven are celebrating Mozart's birthday

Question

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$.

Answer 1

Completing Rosie's answer:

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!

Answer 2

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.

Answer 3

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.