Intereting Posts

What are the requirements for separability inheritance
How to prove $\frac{1}{2}f''(\xi) = \frac{f(a)}{(a-b)(a-c)}+\frac{f(b)}{(b-a)(b-c)}+\frac{f(c)}{(c-a)(c-b)}$
Prove $\sum_{i=1}^{n}\frac{a_{i}}{a_{i+1}}\ge\sum_{i=1}^{n}\frac{1-a_{i+1}}{1-a_{i}}$ if $a_{i}>0$ and $a_{1}+a_{2}+\cdots+a_{n}=1$
Sum of discrete and continuous random variables with uniform distribution
How many elements in a number field of a given norm?
Is there a set of all topological spaces?
Representation of quiver $1 \to 2 \to 3$
Power series summation
How prove this inequality $\sum\limits_{cyc}\frac{x^2}{(2x+y)(2x+z)}\le\frac{1}{3}$
Properties of homomorphisms of the additive group of rationals
Proof Using the Monotone Convergence Theorem for the sequence $a_{n+1} = \sqrt{4 + a_n}$
Isoperimetric inequality, isodiametric inequality, hyperplane conjecture… what are the inequalities of this kind known or conjectured?
Can a (rational coefficient) polynomial have roots with two radicals?
How much faster is the Trachtenberg system?
Reference request: Gronwall's inequality with negative sign(s)

Now this is a more of a computer science problem than a math problem but it is concerning game theory and it does seem a lot like nim (it’s from an online judge), so i’m kinda stuck on this one i’d really appreciate any help you could give me.

You have $n$ piles of stones, the $i$-th pile has $a_i$ stones on it; you also have a list of available moves, where moves are described by “remove $x_1$ stones from pile $1$, $x_2$ stones from pile $2$, $x_3$ stones from pile $3$, etc., etc.” ($x_i$ can be $0$). This is a two-player game where each player in his/her turn can choose one move and play it, and the player that can’t make any move loses. For a given configuration you should determine if the winner is the first or the second player.

- Explanation on arg min
- Fastest Square Root Algorithm
- Polynomial GCD in the presence of floating-point errors
- Why are Hornsat, 3sat and 2sat not equivalent?
- What algorithm is used by computers to calculate logarithms?
- Returning numbers included in a number

- Minimum Sum that cannot be obtained from the 1…n with some missing numbers
- Why does this algorithm to plot implicit equations work?
- What is the best way to factor arbitrary polynomials?
- Probability Calculations on Highway
- Accelerating Convergence of a Sequence
- How can $n \lg n = O(n^{log_3 4 - r})$?
- Efficiently finding two squares which sum to a prime
- Quick algorithm for computing orders mod n?
- Counting primes
- Sharing a pepperoni pizza with your worst enemy

You’re correct that this is a nim variant. More generally, all impartial games (those where both players have the same moves available to them) of this sort fall under the broad category of the Sprage-Grundy theorem which says that their values are equivalent to the value of some nim-pile.

But for determining who’s to win from a given ‘single-position’ configuration, you don’t need any of the broader information; instead, you just need the concepts of ‘next player wins’ ($\mathcal{N}$-positions) and ‘previous player has won’ ($\mathcal{P}$-positions), along with the rules for determining the value of a position from all of its options: if any of the moves available from a given position is to a $\mathcal{P}$-position, then that position is an $\mathcal{N}$-position (since the next player can win by moving to the $\mathcal{P}$-position). Otherwise (i.e., if all of the positions that can be reached from the given position are $\mathcal{N}$-positions), the position is a $\mathcal{P}$-position; there are no good moves available.

This evaluation can then be used in one of two ways; if you’re interested in the value of a single position then you can simply build the tree (more accurately, DAG — *Directed Acyclic Graph*) of moves from that position (being careful to cache ‘transpositions’ – e.g., since making move $m_1$ followed by $m_2$ leads to the same position $P_{12}$ as making move $m_2$ followed by $m_1$, you don’t want to compute the value of $P_{12}$ twice) and evaluate it.

If you’re going to be computing the value of many positions then it will generally be better to build a table of values, but in games which have many piles this is likely to be a very large table. Since all of the moves have to decrease one or more coordinates, the table can be built outwards from the origin in ‘shells’: first fill in the value for the origin (which by definition will be a $\mathcal{P}$-position, since there’s no legal move to make). Next, fill in the values for all cells with the sum of their pile-sizes equal to 1 (i.e., $(1,0,0,\ldots),\ (0, 1, 0, \ldots),\ (0, 0, 1,\ldots),\ \ldots$); since any move decreases one or more coordinates it has to decrease the sum of the pile-sizes and so you’ll already have processed all of the positions a given position’s value can depend on before you process that position itself. Note that for a fixed number of dimensions (i.e., piles), it’s easy to write the iteration over each shell as a series of nested loops with appropriate limits. For instance, the four-pile case would look like:

```
for ( totalSum = 0; totalSum <= 16; totalSum++ ) {
for ( pile0 = 0; pile0 <= totalSum; pile0++ ) {
for ( pile1 = 0; pile1 <= totalSum-pile0; pile1++ ) {
for ( pile2 = 0; pile2 <= totalSum-(pile0+pile1); pile2++ ) {
pile3 = totalSum-(pile0+pile1+pile2);
...
}
}
}
}
```

If the number of piles is given as part of the input you’ll have a bit more work to do, but there are still relatively straightforward ways of iterating over all combinations summing to a given number.

- Generalized Trigonometric Functions in terms of exponentials and roots of unity
- How to sort vertices of a polygon in counter clockwise order?
- A Problem in Elementary Number Theory and Prime Numbers
- Transcendental numbers involving primes?
- How do we know that certain concrete nonstandard models of the natural numbers satisfy the Peano axioms?
- $a+b+c+d+e=79$ with constraints
- Integrability of Maximal Convolution Operator
- Construction of special $\omega_1$-Aronszajn tree
- Transient diffusion with compact support throughout (not just initially)
- Difficulties in a proof by mathematical induction (involves evaluating $\sum r3^r$).
- What is the remainder when $1! + 2! + 3! +\cdots+ 1000!$ is divided by $12$?
- Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$
- A little integration paradox
- The Maximum possible order for an element $S_n$
- What is so special about $\alpha=-1$ in the integral of $x^\alpha$?