4
$\begingroup$

Anna and Boris play a game with the numbers from 1 to 100 written in order in a row. Anna goes first, and turns alternate thereafter. In each move, a player puts one of the operation signs +, − and × between any two numbers which do not already have an operation sign in between them. After 99 operation signs have been placed, the value of the expression is computed. Anna wins if this value is odd, and Boris wins if it is even. Prove that Anna has a winning strategy.


Clarifications:

The operation signs always go between numbers and NOT in the middle of a number. For example, for the given number 91, you can’t put an operation sign between the 9 and the 1. Also, normal mathematical order of operation is used.


This puzzle is from a Leningrad Mathematical Olympiad.

$\endgroup$

2 Answers 2

8
$\begingroup$

On her first move, Anna can

Put a + between 1 and 2.

Anna's subsequent moves depend on Boris' subsequent moves.

* If Boris put a + or - to the right of an odd number with no operator to its left, Anna can put a × to the left of this number

* If Boris put a + or - the the left of an odd number with no operator to its right, Anna can put a × to the right of this number

In all other cases, Anna can put a × in any available spot.

This works because

Anna's first move results in an odd number (1) plus some other number

Each of Anna's subsequent moves work to ensure that "some other number" will be even

$\endgroup$
0
3
$\begingroup$

Starting with the sequence 1,2,3,...,99,100, every move reduces two numbers to one.

Here are a player's possible moves and outcomes:

Move Outcome
odd +- even odd
odd × even even
odd +- odd even
odd × odd odd
even +-× even even

Sorry, I couldn't figure out how to get a table in spoilertext.

Anna is 1st and play alternates, so she will also be 99th (last).

On the final turn she will be faced with two numbers. If they are odd,odd or even,odd she can choose her outcome and win, so she must make sure Boris cannot present her with even,even on his last turn.

Boris can produce even,even if there is an even on the right or left on his turn: leaving it untouched, he can reduce the other two numbers to an even.

But if she can guarantee that

he is presented with an odd on the left and the right, his move will have to leave one odd untouched.

She can do this by guaranteeing that

she always ends her turn with odds on the ends. On her first turn, the sequence alternates, and begins odd,even,.... She can place a + or - by the 100 to make the sequence end ...,even,odd.

Faced with an odd-sandwiched alternating sequence, Boris only has two options. He can convert one of the odd ends to an even (leaving Anna an alternating sequence). Or produce a pair of same-parity numbers somewhere in the sequence.

If he converts one of the odd ends, Anna can change it back, leaving him with an odd-sandwiched alternating sequence. If he produces a pair of same-parity numbers, Anna can reduce those to 1 number (odd,odd, she can place × between them; even,even, she can place any operation between them) to restore alternation and leave him with an odd-sandwiched alternating sequence.

Thus, she can

force Boris to be faced with an odd-sandwiched alternating sequence every turn, which only gives him options that allow her to end her turn with odds on both ends.

In short, Anna's strategy:

If the first or last number is even, place + or - next to it.
If there is a pair of consecutive odd numbers, place × between them.
If there is a pair of consecutive even numbers, place +, -, or × between them.

Following this strategy,

she will always end her turn with an alternating sequence with odds on the ends, so that Boris cannot produce a sequence that does not fall under the rules in her strategy. The sequence will be reduced one by one until Boris is ultimately forced to produce odd,odd or odd,even, which Anna can reduce to odd by following her rules.

$\endgroup$
1
  • $\begingroup$ I just realized I didn't consider "normal order of operations" in my answer. I treated each move as if it replaced the involved numbers with the result of its operation, like it was done with parentheses. And my brain's too tired to figure out if my strategy no longer works. kyle's approach though cleverly mitigates this issue by locking in a number each time Anna moves. $\endgroup$ Feb 3 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.