black squares on infinite cross-lined paper 
Some $n$ squares of the infinite cross-lined sheet of paper are painted black (all others are white). Every move all the squares of the sheet change their color simultaneously. Each square gets the color that appeared on the majority of the square itself, the square to the right, and the square above it.
a) Prove that after a finite number of moves all the black squares will disappear.
b) Prove that it will happen not later than on the $n^\text{th}$ move.
(Source: All Soviet Union Math Olympiad in 1973)

For part b, I'm trying to use strong induction. However, I don't know how to account for the fact that the number of black squares in an arrangement might increase on the next move. Help?
 A: As Will Orrick notes, any row or column with no black squares in at the start will never have black squares in it. So each set of black squares that can be fenced off by non-black rows and columns into an active area is a distinct population, and will be gone with the number of turns for that population.
The diagonals within an active area are the key. At the start of the process with $n$ black squares, there are no more than $n$ NW-SE diagonals containing a black square ("occupied"). The assertion here is that the maximum number of occupied diagonals shrinks at each turn (not the actual number occupied; the maximum possible from the initial black square count).
Consider the effect of one turn. The furthest NE occupied NW-SE diagonal is cleared, losing one diagonal, as it cannot have majority support for any square on that diagonal. New diagonals can be occupied, but the only way this can happen is if there was already more than one square on one of the existing diagonals, and this is true for each new diagonal occupied. So the maximum limit has still reduced by $1$, because there were fewer diagonals than the maximum possible occupied to start with.
The upper bound of $n$ turns is tight, because we can exhibit a set of adjacent black squares in a row that takes $n$ turns to clear.
A: I will introduce some definitions to proof these claims.
The set of squares labeled as $x$ or $X$ in the following picture is called a triangle of size $4$. We denote a set consisting of all squares labled $l_1, l_2, \ldots, l_m$  as set $S(l_1,l_2,\ldots, l_m)$.
. . . . . . . .
. v u . . . . .
. v X u . . . .
. v x X u . . .
. v x x X u . .
. v x x x X u .
. . w w w w w .
. . . . . . .

So $S(x)$ is a triangle containing $6$ squares, $S(x,X)$ is a triangle containing $10$ squares. $S(x,X,u)$, $S(x,X,v)$ and  $S(x,X,w)$ are triangles containing $15$ squares.
By adding the squares labeled $u$ or the squares labeled $v$ or or the squares labeled $w$ to the triangle $S(x,X)$ we get a triangle of size $5$,  $S(x,X,u)$ or  $S(x,X,v)$ or  $S(x,X,w)$. In this way we define a triangle of size $k$ for every integer $k$.
We augment  the triangle $S(x,X)$ at the hypothenuse to get triangle $S(x,X,u)$. We augment it at the bottom to get the triangle $S(x,X,w)$ and we augment it at the  left to get the triangle $S(x,X,v)$.
The size of a triangle is the length of its cathetus.
By adding the squares labeled $u$ or the squares labeled $v$ or or the squares labeled $w$ to $S(x,X)$ we get a triangle of size $5$,  triangle $S(x,X,u)$ or  $S(x,X,v)$ or  $S(x,X,w)$. In this way we define a triangle of size $k$ for every integer $k$.
A square is a triangle of size $1$ and I think it is clear what a triangle of size $2$ and $3$ is.
If we remove the hypothenuse $S(X)$ from the triangle $S(x,X)$ we get  the  reduced triangle $S(x))$ of the triangle $S(x,X)$.
If the squares $u$, $v$ and $w$ do not contain a black squares, we call the triangle $S(x,X)$ a fencing triangle. If there are black squares labeled $u$,$v$ or $w$ we say these black squares $touch$ the triangle.
If in the following picture the square $a$ is black  after a move
. . . .
. b . .
. a c .
. . . . 

then this happens exactly because at least two of $\{a,b,c\}$ where black before the move.
If $x\in \{a,b,c\}$ was black before the move we say that $a$ was generated by $x$.
We call a black square $s_1$ a successor of a square $s_2$ if either $s_1$ is generated by $s_2$ or if $s_1$ is generated by a successor of $s_2$.

The following 4 statements I state without proof.
Statement 1:
If we have a fencing triangle  then after a move all squares generated by the squares of this fencing triangle are contained in the reduced triangle of this fencing triangle. The reduced triangle again is a fencing triangle.
Statement 2:
Given $n$ black squares we can always find a fencing triangle.
Statement 3:
If we have a fencing triangle  then after a move all squares generated by the squares of this fencing triangle are contained in the reduced triangle of this fencing triangle. The reduced triangle again is a fencing triangle.
Statement 4:
If a fencing triangle $T$ has size $k$ then after $k$ moves there are no successors of the black squares of the initial triangle $T$.
So we have shown claim a).  Now we proof claim b).
Statement 5: Given $n$ black squares We can find at most $n$ fencing triangle such that the size of each triangle is at most $n$.
Proof: Take an arbitrary black square. This is a triangle of size $1$. If it is fencing then we are done. If not there is at least one black square outside of the triangle that touches the triangle. We select such a point and if it touches the triangle at the left, the bottom or the hypothenuse  we augment the triangle at the left, the bottom or the hypothenuse. The size of the triangle is increased by 1, the number of black squares inside this new triangle is at least increased by 1. We stop if the triangle is fencing. This happens after at most $n$ steps, because each step adds at least one black square to the new triangle and there are not more than $n$ black triangles to add.
We repeat this process for another black square that is not already contained n a fencing triangle until no blck square is left.
These triangles can fencing overlap but that does not matter for  our proof.
Statement 6: After at most $n$ moves there are no black square in the grid.
Proof: We can find a finite number of fencing triangles of size at most $n$ that contain all black squares. After a move the black squares are contained in the reduced triangles that are still fencing. After at most $n$ moves these triangles are all empty.
Edit:
I tried to improve the answers based on suggestion by @WillOrrick
A: Warning: as pointed out by Joffan, the observations in this post aren't strong enough to prove the desired result. I was going to delete the post, but have decided to leave it, as Joffan's post somewhat depends on it. I recommend the reader take a look at the simple inductive argument in Mike Earnest's answer to the duplicate target he links to in a comment. I like miracle173's answer answer even better since it gives a very concrete picture of exactly how the black squares disappear, which I feel is somewhat missing from the simple inductive proof.
Observe that if a row or column contains no black squares, then that row or column will not contain black squares in any subsequent update. Let's assign coordinates to our grid. Label rows by integers, increasing from top to bottom, with $0$ labeling the topmost row containing a black square in the initial configuration. Similarly, label columns by integers, increasing from right to left, with $0$ labeling the rightmost column containing a black square in the initial configuration. Let row $r-1$ be the bottommost row containing a black square and let column $c-1$ be the leftmost column containing a black square (both in the initial configuration). Because of our observation about rows and columns that contain no black squares, no square of the grid with row coordinate outside the interval $[0,r-1]$ or column coordinate outside the interval $[0,c-1]$ will contain a black square in any update. In other words, the black squares remain inside a fixed bounding box of $r$ rows and $c$ columns.
Now look at the $45^\circ$ diagonals that pass from the top left to the bottom right. The sum of the row and column coordinates of every square of such a diagonal is constant, and we assign this sum as a coordinate to the diagonals. If a diagonal contains no black squares then the adjacent diagonal below that one will become empty on the next update. Because of this, diagonal $0$ will become empty (if it isn't already) on the first update, diagonal $1$ will become empty on the second update (and diagonal $0$ will remain empty), and so on. Therefore the bonding box will become completely empty by the $((r-1)+(c-1)+1)^\text{th}$ update. This update number is the half-perimeter of the bounding box minus $1$. So now you only need to show that the maximum rectangular half-perimeter enclosing $n$ squares is $n+1$.
Added: Joffan points out a problem with my original discussion. If in the initial configuration every diagonal in the bounding box contains at least one black square then the number of black squares is at least the number of diagonals, and we have the desired result without further ado. (In particular we don't need to discuss the maximum perimeter enclosing $n$ squares, which is a dubious approach anyway since most of the time the $n$ black squares won't be arranged contiguously in a rectangular block.)
But in configurations with empty diagonals, $n$ can easily be less than $r+s-1$. For example, if all $n$ black squares are arranged consecutively along a single diagonal, then $r=s=n$, and the argument above only implies disappearance after $2n-1$ steps. In actual fact, however, disappearance occurs in $n$ steps.
A: If you imagine enclosing the black squares into a finite region, the outside of which is white, then the way to maximise the number of black squares and their survival is to completely colour the interior in black. A single white square might be coloured black if placed right in the middle among them, but the top right corner must vanish. If two white squares are introduced, then they will be coloured black but the top corner will vanish, followed by two corners. Keep going and you will find that no configuration consistently increases the number of squares very far.
Edit: I may have been thinking about this the wrong way, this is sensitive to areas and not numbers of squares. At best it would give a rough estimate. From reading the comments I may suggest applying the induction to solid rectangles forming the total picture. In the end probably @Xander Henderson is right, diagonals are the way to go.
Edit 2: @miracle173 has done it, the key was to use triangles, not rectangles, and to iterate on the size of the diagonal.
