Arguments by Contradiction

Suppose not! Suppose to the contrary that there is such a polynomial \(f(x) = a_nx^n + \dotsb a_1x + a_0\). Then the output \(f(0)\) must be some prime number \(p\). Furthermore the outputs \(f(p), f(2p), \dotsc, f(kp), \dotsc\) are all also prime. But \(p\) divides each of these outputs, so the only possibility is that \[ f(0) = f(p) = f(2p) = \dotsb = f(kp) = \dotsc = p\,. \] But this cannot be! No polynomial can take on the same value infinitely many times; that would contradict the Fundamental Theorem of Algebra. Therefore no such polynomial function \(f\) can exist.

Suppose not! Suppose to the contrary that there are only finitely many prime numbers: \(p_1, p_2, \dotsc, p_n\). Then consider the number \(N = p_1 p_2 \dotsb p_n + 1\). Since every prime divides the product \(p_1 p_2 \dotsb p_n\) but no prime divides \(1\), no prime divides \(N\). So \(N\), being factorable into primes as all integers are, must be divisible by a prime not in our list! This contradicts our supposition that there are finitely many primes.

Suppose not! Suppose to the contrary that there exists some \(x\) in \([\pi/2, \pi]\) such that \(\sin(x) - \cos(x) \lt 1.\) This would mean that: \[\begin{align*} \big(\sin(x) - \cos(x)\big)^2 &\lt 1 \\ \sin^2(x) -2\sin(x)\cos(x) + \cos^2(x) &\lt 1 \\ \big(\sin^2(x) + \cos^2(x) \big) -2\sin(x)\cos(x) &\lt 1 \\ 1 -2\sin(x)\cos(x) &\lt 1 \\ -2\sin(x)\cos(x) &\lt 0 \\ \sin\!\big(2x\big) &\gt 0 \end{align*}\] but for every \(x\) in \([\pi/2, \pi]\), \(\sin\!\big(2x\big)\) will be negative. A contradiction! Therefore \(\sin(x) - \cos(x) \geq 1\) for all \(x\) in \([\pi/2, \pi].\)

Suppose not! Suppose to the contrary that \(\sqrt{2}\) is rational, and can be written as a reduced fraction \(\frac{a}{b}\) for some relatively prime integers \(a\) and \(b.\) Since

\[ \sqrt{2} = \frac{a}{b} \quad\implies\quad 2b^2 = a^2\,.\] we see that \(2\) divides \(a^2\). But since \(a^2\) is square, \(4\) must divide \(a^2\). This means \(2\) must divide \(b\) too. A contradiction since we assumed \(a\) and \(b\) are relatively prime! Therefore \(\sqrt{2}\) is not rational.

Suppose not! Suppose to the contrary that integers \(x\) and \(y\) exist such that \(21x + 30y = 1.\) Then \[3(7x + 10y) = 1\,.\] Since \(x\) and \(y\) are integers, this last equation implies \(3\) divides \(1\), a contradiction! Therefore no such integers \(x\) and \(y\) exist.

Suppose not! Suppose instead we have sets \(A\) and \(B\) and real number \(a\) such that \(B=A+a,\) \(A \cup B = [0,1],\) and \(A \cap B = \varnothing.\)

Without loss of generality, suppose \(0 \in A\). Since \(0 = \inf A\), \(0+a = \inf B\). And so \([0, a) \subset A\) and so \([a, 2a) \subset B\). This means \(2a \in A\). Repeating this argument inductively we conclude that \[ a \in B \quad 2a \in A \quad 3a \in B \;\; \dotsb \;\; (2n-1)a \in B \quad (2n)a \in A \;\; \dotsb \] for all positive integers \(n\). But for \(n = \lceil\frac{1}{2a}\rceil\), \((2n)a \gt 1\) and so \(A \not\subset [0,1]\). A contradiction! Therefore no such sets \(A\) and \(B\) can exist.

The answer is yes, all colors will be red after two iterations.

To see this, it’s helpful to establish the following fact: in any recoloring, if \(2y\) is blue, then \(y\) is red. Indeed this is true because in the coloring previous, \(0\) and \(2y\) would have to be different colors, leaving \(y\) to be distance \(y\) from each of them and the same color as one of them.

With this in mind, suppose for the sake of contradiction that \(2x\) is still blue after two iterations. This means in the previous iteration the numbers \(2x,\) \(4x,\) \(6x,\) \(8x\) alternate in color. Since \(8x\) and \(4x\) can’t both be blue by the established fact, they must both be red, and \(2x\) and \(6x\) blue. Because \(2x\) and \(6x\) are blue, by the fact, \(x\) and \(3x\) must be red. But \(x\) and \(3x\) are distance \(2x\) apart, meaning \(2x\) must be colored red in the next iteration, which is the contradiction that we sought.