Fix grammar + formatting errors in 4 files (cp-algorithms#494)

AbhijeetKrishnan · jakobkogler · commit 376b308ef50e · 2019-11-29T11:51:06.000+01:00
diff --git a/src/game_theory/sprague-grundy-nim.md b/src/game_theory/sprague-grundy-nim.md
@@ -3,20 +3,20 @@
 
 ## Introduction
 
-This theorem describes the so-called **impartial** two-player games,
-that is those in which the available moves and winning/losing depends only on the state of the game.
+This theorem describes the so-called **impartial** two-player game,
+i.e. those in which the available moves and winning/losing depends only on the state of the game.
 In other words, the only difference between the two players is that one of them moves first.
 
-Additionally, we assume that the game has **perfect information**, i.e. no information is hidden from the players (they know the rules and the possible move).
+Additionally, we assume that the game has **perfect information**, i.e. no information is hidden from the players (they know the rules and the possible moves).
 
-It is assumed that the game is **finite**, i.e. sooner or later a player will come to a losing position — from which he can't move to another position.
+It is assumed that the game is **finite**, i.e. after a certain number of moves, one of the players will end up in a losing position — from which they can't move to another position.
 On the other side, the player who set up this position for the opponent wins.
 Understandably, there are no draws in this game.
 
-Such games can be completely described by an *directed acyclic graph*: the vertices are game states, the edges are transitions (moves).
-A vertex without outgoing edges is a losing one (a player who must make a move from this vertex loses).
+Such games can be completely described by a *directed acyclic graph*: the vertices are game states and the edges are transitions (moves).
+A vertex without outgoing edges is a losing vertex (a player who must make a move from this vertex loses).
 
-Since there are no draws, we can classify all game states as either **winning or losing**.
+Since there are no draws, we can classify all game states as either **winning** or **losing**.
 Winning states are those from which there is a move that causes inevitable defeat of the other player, even with their best response.
 Losing states are those from which all moves lead to winning states for the other player.
 Summarizing, a state is winning if there is at least one transition to a losing state and is losing if there isn't at least one transition to a losing state.
@@ -27,8 +27,8 @@ The theory of such games was independently developed by Roland Sprague in 1935 a
 
 ## Nim
 
-This game falls under the restrictions above.
-Moreover, **any** perfect-information impartial two-player game can be reduced to the game of Nim.
+This game obeys the restrictions described above above.
+Moreover, *any* perfect-information impartial two-player game can be reduced to the game of Nim.
 Studying this game will allow us to solve all other similar games, but more on that later.
 
 Historically this game was popular in ancient times.
@@ -40,7 +40,7 @@ The name was given by Charles Bouton, who in 1901 published a full analysis of t
 
 There are several piles, each with several stones.
 In a move a player can take any positive number of stones from any one pile and throw them away.
-A player loses if he can't make a move — all the piles are empty.
+A player loses if they can't make a move, which happens when all the piles are empty.
 
 The game state is unambiguously described by a multiset of positive integers.
 A move consists of strictly decreasing a chosen integer (if it becomes zero, it is removed from the set).
@@ -54,16 +54,16 @@ The current player has a winning strategy if and only if the xor-sum of the pile
 The xor-sum of a sequence $a$ is $a_1 \oplus a_2 \oplus \ldots \oplus  a_n$, where $\oplus$ is the *bitwise exclusive or*.
 
 **Proof.**
-The main point of the proof is the presence of a **symmetric strategy for the opponent**.
+The key to the proof is the presence of a **symmetric strategy for the opponent**.
 We show that a once in a position with the xor-sum equal to zero, the player won't be able to make it non-zero in the long term —
-if he transitions to a position with a non-zero xor-sum, the opponent will always have a move returning the xor-sum back to zero.
+if they transition to a position with a non-zero xor-sum, the opponent will always have a move returning the xor-sum back to zero.
 
 We will prove the theorem by mathematical induction.
 
 For an empty Nim (where all the piles are empty i.e. the multiset is empty) the xor-sum is zero and the theorem is true.
 
 Now suppose we are in a non-empty state.
-Using the assumption of induction (and the acyclicity of the game) we believe that the theorem is proven for all states reachable from the current one.
+Using the assumption of induction (and the acyclicity of the game) we assume that the theorem is proven for all states reachable from the current one.
 
 Then the proof splits into two parts:
 if for the current position the xor-sum $s = 0$, we have to prove that this state is losing, i.e. all reachable states have xor-sum $t \neq 0$.
@@ -72,33 +72,37 @@ If $s \neq 0$, we have to prove that there is a move leading to a state with $t
 * Let $s = 0$ and let's consider any move.
 This move reduces the size of a pile $x$ to a size $y$.
 Using elementary properties of $\oplus$, we have
-$$t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y. $$
+
+$$t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y$$
+
 Since $y < x$, $y \oplus x$ can't be zero, so $t \neq 0$.
 That means any reachable state is a winning one (by the assumption of induction), so we are in a losing position.
 
 * Let $s \neq 0$.
 Consider the binary representation of the number $s$.
 Let $d$ be the number of its leading (biggest value) non-zero bit.
-Our move will be on a pile whose size's bit number $d$ is set (It must exist, otherwise the bit wouldn't be set in $s$).
+Our move will be on a pile whose size's bit number $d$ is set (it must exist, otherwise the bit wouldn't be set in $s$).
 We will reduce its size $x$ to $y = x \oplus s$.
 All bits at positions greater than $d$ in $x$ and $y$ match and bit $d$ is set in $x$ but not set in $y$.
 Therefore, $y < x$, which is all we need for a move to be legal.
 Now we have:
-$$ t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0. $$
+
+$$ t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0$$
+
 This means we found a reachable losing state (by the assumption of induction) and the current state is winning.
 
 **Corollary.**
 Any state of Nim can be replaced by an equivalent state as long as the xor-sum doesn't change.
 Moreover, when analyzing a Nim with several piles, we can replace it with a single pile of size $s$.
 
-## The equivalence of impartial games and Nim. Sprague-Grundy theorem
+## The equivalence of impartial games and Nim (Sprague-Grundy theorem)
 
 Now we will learn how to find, for any game state of any impartial game, a corresponding state of Nim.
 
-### Lemma about Nim with increasing
+### Lemma about Nim with increases
 
 We consider the following modification to Nim: we also allow **adding stones to a chosen pile**.
-The exact rules about how and when increasing is allowed **do not interest us**, however the rules should keep our game **acyclic**. In later sections example games are considered.
+The exact rules about how and when increasing is allowed **do not interest us**, however the rules should keep our game **acyclic**. In later sections, example games are considered.
 
 **Lemma.**
 The addition of increasing to Nim doesn't change how winning and losing states are determined.
@@ -110,14 +114,14 @@ Since the game is acyclic, sooner or later the current player won't be able to u
 
 ### Sprague-Grundy theorem
 
-**Sprague-Grundy theorem.**
-Let's consider a state $v$ of a two-player impartial game and let $v_i$ be the states reachable from it
-(where $i \in \\{ 1, 2, \dots, k \\} , k \ge 0$ ).
-To this state we can assign a fully equivalent game of Nim with one pile of size $x$.
+Let's consider a state $v$ of a two-player impartial game and let $v_i$ be the states reachable from it (where $i \in \{ 1, 2, \dots, k \} , k \ge 0$).
+To this state, we can assign a fully equivalent game of Nim with one pile of size $x$.
 The number $x$ is called the Grundy value or nim-value of state $v$.
 
 Moreover, this number can be found in the following recursive way:
-$$ x = \text{mex} \\{ x_1, \ldots, x_k \\}, $$
+
+$$ x = \text{mex} \{ x_1, \ldots, x_k \}, $$
+
 where $x_i$ is the Grundy value for state $v_i$ and the function $\text{mex}$ (*minimum excludant*) is the smallest non-negative integer not found in the given set.
 
 Viewing the game as a graph, we can gradually calculate the Grundy values starting from vertices without outgoing edges.
@@ -129,18 +133,18 @@ We will use a proof by induction.
 For vertices without a move, the value $x$ is the $\text{mex}$ of an empty set, which is zero.
 That is correct, since an empty Nim is losing.
 
-Now consider any other vertex.
-By induction, we assume the values $x_i$ corresponding to the reachable vertices are already calculated.
+Now consider any other vertex $v$.
+By induction, we assume the values $x_i$ corresponding to its reachable vertices are already calculated.
 
-Let $p = \text{mex} \\{ x_1, \ldots, x_k \\} $.
+Let $p = \text{mex} \{ x_1, \ldots, x_k \}$.
 Then we know that for any integer $i \in [0, p)$ there exists a reachable vertex with Grundy value $i$.
-This means $v$ is **equivalent to a state of the game of Nim with increasing with one pile of size $p$**.
+This means $v$ is **equivalent to a state of the game of Nim with increases with one pile of size $p$**.
 In such a game we have transitions to piles of every size smaller than $p$ and possibly transitions to piles with sizes greater than $p$.
 Therefore, $p$ is indeed the desired Grundy value for the currently considered state.
 
 ## Application of the theorem
 
-Finally, we describe an algorithm determining the winning/losing status applicable to any impartial two-player game.
+Finally, we describe an algorithm to determine the win/loss outcome of a game, which is applicable to any impartial two-player game.
 
 To calculate the Grundy value of a given state you need to:
 
@@ -160,18 +164,18 @@ We can xor-sum them just like usual Nim according to Bouton's theorem.
 
 ## Patterns in Grundy values
 
-Very often when solving specific tasks using Grundy values it may be beneficial to **study the table of the values** in search of patterns.
+Very often when solving specific tasks using Grundy values, it may be beneficial to **study the table of the values** in search of patterns.
 
 In many games, which may seem rather difficult for theoretical analysis,
 the Grundy values turn out to be periodic or of an easily understandable form.
 In the overwhelming majority of cases the observed pattern turns out to be true and can be proved by induction if desired.
 
-However, Grundy values are far from *always* containing such regularities and for some even very simple games
-the problem if those regularities exist is still open (eg. "Grundy's game").
+However, Grundy values are far from *always* containing such regularities and even for some very simple games, the problem asking if those regularities exist is still open (e.g. "Grundy's game").
 
 ## Example games
 
 ### Crosses-crosses
+
 **The rules.**
 Consider a checkered strip of size $1 \times n$. In one move, the player must put one cross, but it is forbidden to put two crosses next to each other (in adjacent cells). As usual, the player without a valid move loses.
 
@@ -184,14 +188,9 @@ into two strips of length $i-2$ and $n-i-1$ i.e. we go to the sum of games $i-2$
 For the edge case of the cross being marked on position $1$ or $n$, we go to the game $n-2$.
 
 Thus, the Grundy value $g(n)$ has the form:
-$$ g(n) = \text{mex} \Bigl( \\{ g(n-2) \\} \cup \\{g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1\\} \Bigr) . $$
+
+$$g(n) = \text{mex} \Bigl( \{ g(n-2) \} \cup \{g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1\} \Bigr) .$$
 
 So we've got a $O(n^2)$ solution.
 
 In fact, $g(n)$ has a period of length 34 starting with $n=52$.
-
-
-
-
-
-
diff --git a/src/num_methods/roots_newton.md b/src/num_methods/roots_newton.md
@@ -2,19 +2,19 @@
 
 # Newton's method for finding roots 
 
-This is an iterative method invented by Isaac Newton around 1664. However, sometimes this method is called the Raphson method, since Raphson invented the same algorithm a few years after Newton, but his article was published much earlier.
+This is an iterative method invented by Isaac Newton around 1664. However, this method is also sometimes called the Raphson method, since Raphson invented the same algorithm a few years after Newton, but his article was published much earlier.
 
 The task is as follows. Given the following equation:
 
 $$f(x) = 0$$
 
-We want to solve the equation, more precisely, to find one of its roots (it is assumed that the root exists). It is assumed that $f(x)$ is continuous and differentiable on an interval $[a; b]$.
+We want to solve the equation. More precisely, we want to find one of its roots (it is assumed that the root exists). It is assumed that $f(x)$ is continuous and differentiable on an interval $[a, b]$.
 
 ## Algorithm
 
 The input parameters of the algorithm consist of not only the function $f(x)$ but also the initial approximation - some $x_0$, with which the algorithm starts.
 
-Suppose we have already calculated $x_i$, calculate $x_{i+1}$ as follows. Draw the tangent to the graph of the function $f(x)$ at the point $x = x_i$, and find the point of intersection of this tangent with the $x$-axis. $x_{i+1}$ is set equal to the $x$-coordinateof the point found, and we repeat the whole process from the beginning.
+Suppose we have already calculated $x_i$, calculate $x_{i+1}$ as follows. Draw the tangent to the graph of the function $f(x)$ at the point $x = x_i$, and find the point of intersection of this tangent with the $x$-axis. $x_{i+1}$ is set equal to the $x$-coordinate of the point found, and we repeat the whole process from the beginning.
 
 It is not difficult to obtain the following formula:
 
diff --git a/src/num_methods/simpson-integration.md b/src/num_methods/simpson-integration.md
@@ -10,18 +10,17 @@ The solution described here was published in one of the dissertations of **Thoma
 
 ## Simpson's formula
 
-Let $n$ be some natural number. We divide the integration segment $[a; b]$ into $2n$ equal parts:
+Let $n$ be some natural number. We divide the integration segment $[a, b]$ into $2n$ equal parts:
 
 $$x_i = a + i h, ~~ i = 0 \ldots 2n,$$
 $$h = \frac {b-a} {2n}.$$
 
 Now we calculate the integral separately on each of the segments $[x_ {2i-2}, x_ {2i}]$, $i = 1 \ldots n$, and then add all the values.
 
-
 So, suppose we consider the next segment $[x_ {2i-2}, x_ {2i}],  i = 1 \ldots n$. Replace the function $f(x)$ on it with a parabola $P(x)$ passing through 3 points $(x_ {2i-2}, x_ {2i-1}, x_ {2i})$. Such a parabola always exists and is unique; it can be found analytically.
 For instance we could construct it using the Lagrange polynomial interpolation.
 The only remaining thing left to do is to integrate this polynomial.
-If you do this for a general function $f$, you receive a remarkable simple expression:
+If you do this for a general function $f$, you receive a remarkably simple expression:
 
 $$\int_{x_ {2i-2}} ^ {x_ {2i}} f (x) ~dx \approx \int_{x_ {2i-2}} ^ {x_ {2i}} P (x) ~dx = \left(f(x_{2i-2}) + 4f(x_{2i-1})+(f(x_{2i})\right)\frac {h} {3} $$
 
@@ -40,7 +39,7 @@ The error is asymptotically proportional to $(b-a)^5$. However, the above deriva
 
 ## Implementation
 
-Here $f(x)$ is some user function.
+Here, $f(x)$ is some user-defined function.
 
 ```cpp
 const int N = 1000 * 1000; // number of steps (already multiplied by 2)
diff --git a/src/num_methods/ternary_search.md b/src/num_methods/ternary_search.md
