Question

A [i]Nim-style[/i] game is defined as follows. Two positive integers \(k\) and \(n\) are specified, along with a finite set \(S\) of \(k\)-tuples of integers (not necessarily positive). At the start of the game, the \(k\)-tuple \((n, 0, 0, ..., 0)\) is written on the blackboard.
A legal move consists of erasing the tuple \((a_1,a_2,...,a_k)\) which is written on the blackboard and replacing it with \((a_1+b_1, a_2+b_2, ..., a_k+b_k)\), where \((b_1, b_2, ..., b_k)\) is an element of the set \(S\). Two players take turns making legal moves, and the first to write a negative integer loses. In the event that neither player is ever forced to write a negative integer, the game is a draw.
Prove that there is a choice of \(k\) and \(S\) with the following property: the first player has a winning strategy if \(n\) is a power of 2, and otherwise the second player has a winning strategy.

Answer 1

this is trivial

Answer 2

trivial because alecks bad

Answer 3

couldn't make mop you can only mop the floors

Answer 4

so bad imagien making mops

Answer 5

you could only make mops

Answer 6

bad!!!!!!38>37

Answer 7

ok but when 7<8

Answer 8

every time

Answer 9

bruh but imagien \(11^{\frac{1}{7}}>13^{\frac{1}{8}}\)

Answer 10

where is your solution

Answer 11

please solve the 2015 tstst problem 6 or bad

Answer 12

We have $k=9$, and $S$ consists of
$S_1=$ (-1,0,0,1,0,0,0,0,0) and (-1,1,0,-1,0,0,0,0,0)
$S_2=$ (0,-1/-2/-3,0,-1,0,0,1,0,0) and (0,-1,1,0,-1,0,-1,0,0)
$S_3=$ (-1,0/-1/-2,0,0,-1,0,0,0,0) and (-2,1,0,0,-1,0,0,0,0)
$S_4=$ (0/-1,0,0,-1,-1,0,0,0,0)
$S_5=$ (-1,0/-1/-2,0,0,0,0,-1,0,0) and (-2/-3,0,0,0,0,0,-1,0,0)
$S_6=$ (-1/-2,0,0,-2,0,0,0,0,0) and (0,0/-1/-2,0,-2,0,0,0,0,0)
and for each of the above 9-tuple also take the two other "cyclic within triplet" permutations, i.e.: (123456789) $\rightarrow$ (312645978) and (231564897). The / above means "and". So for example $S_4$ consists of 6 elements (0,0,0,-1,-1,0,0,0,0); (-1,0,0,-1,-1,0,0,0,0); (0,0,0,0,-1,-1,0,0,0); (0,-1,0,0,-1,-1,0,0,0); (0,0,0,-1,0,-1,0,0,0); (0,0,-1,-1,0,-1,0,0,0).

more intuitive description of each set

Firstly we note that (1,0,0...) is winning, since P1 (player 1) can play the first k-tuple in $S_1$ to reach (0,0,0,1,0...), and P2 has no legal move.

Next we proceed inductively in a few parts. In all inductions we induct by decreasing the total sum of all elements in the k-tuple. Note that since our construction is "cyclic within triplet", all induction statements are also true for "cyclic within triplet" permutations.

Part 1: (a,b,0,0...) is losing for player 1 when a is odd, except for when (a,b) = (1,0).
Proof: All the k-tuples in $S$ decrease some of the 4th to 9th number in the k-tuple except for those in $S_1$. So P1 only has two possible choices:
Case 1: He goes to (a-1,b,0,1,0...). If $a\ge 3$ P2 then plays from $S_1$ to reach (a-2,b+1,0,0...) and we are done by induction. If $a=1$ then P2 plays from the first k-tuple in $S_2$ to reach (0,c,0,0,0,0,1,0,0) where c<b is either 0 or any odd number $\ge 3$ (possible as P2 can choose to decrease b by 1,2 or 3, and $b\neq 0$ as a=1). Now P1 has lost when c=0 & otherwise can only play from $S_1$ to reach (0,c-1,0,0,1,0,1,0,0). P2 plays from 2nd k-tuple in $S_2$ to reach (0,c-2,1,0,0...) and by induction this is losing.
Case 2: He goes to (a,b-1,0,0,1,0...). If $a=1$ P2 plays from the first k-tuple in $S_3$ to reach (0,c,0,0...) where c<b is either 0 or any odd number $\ge 3$, and by induction this losing. If $a\ge 3$ then P2 plays from the second k-tuple in $S_3$ to reach (a-2,b,0,0...) and we are done by induction (note b$\neq 0$ is implied in case 2).

Part 2: (a,b,0,0...) is losing for player 1 when a is even, $a\ge 2$ and $a+2b$ is not a power of 2.
Proof: Similarly, we know that P1 must play some k-tuple in $S_1$, so there are two possible options:
Case 1: He goes to (a-1,b,0,1,0...). P2 plays from $S_1$ again to reach (a-2,b+1,0,0...). If $a\ge 4$ we are done by induction as a+2b remains not a power of 2. If $a=2$ and b+1 is odd we are done by part 1 (note $b\neq0$ as a+2b not power of 2), while when b+1 is even we know that $\frac{a+2b}2=b+1$ is also not a power of 2 and we are done by induction.
Case 2: He goes to (a,b-1,0,0,1,0...). P2 plays from first k-tuple in $S_3$ to reach (a-1,b-1,0,0...) and by part 1 we are done (note (a,b) is not (2,1) as that gives a+2b=4).

Part 3: (a,b,0,0...) is winning for player 1 when a is even, $a\ge 2$ and $a+2b$ is a power of 2.
Proof: P1 plays from $S_1$ to reach (a-1,b,0,1,0...). P2 has four options.
Case 1: He plays from $S_1$ to reach (a-2,b+1,0,0...). We are done by induction since either $a\ge 4$ and a+2b remains a power of 2, or a=2 and b+1 is a power of 2 (b=0 reduces to trivial base case as well)
Case 2: He plays from $S_1$ to reach (a-1,b-1,0,1,1,0...). P1 now plays from $S_4$ to reach (a-1,b-1,0,0...) and by part 1 we are done. If a=2,b=1, player 1 goes to (a-2,b-1,0,0...) instead.
Case 3: He plays from $S_1$ to reach (a-2,b,0,2,0...). If $a\ge 4$ P1 plays from first k-tuple of $S_6$ to reach (a-3,b,0,0...) and we are done by part 1, except when a=4,b=0 where he goes to (a-4,b,0,0...) instead. If $a=2$ he plays from second k-tuple in $S_6$ to reach (0,c,0,0...) where c$\le$b is either 0 or an odd number $\ge 3$ and we are done by part 1.
Case 4: He plays from $S_2$ to reach (a-1,b-1/2/3,0,0,0,0,1,0,0). If $a\ge 4$ P1 plays from the second k-tuple in $S_5$ to reach (a-3,b-1/2/3, 0,0...) and we are done by part 1, except when a=4 and b-1/2/3=0, where he goes to (0,0,0...) instead. If $a=2$ P1 plays from the first k-tuple in $S_5$ to reach (0,c,0,0...) where c<b is either 0 or an odd number $\ge 3$ and we are done by part 1.

Answer 13

sobad not even \(\LaTeX\)

Answer 14

also he copy pasted the solution from aops lol imagine not even solving 55 mohs so bad

Answer 15

alecks bad

Answer 16

oren bad you couldn't even copy paste the latex correctly