IMO-1959

1. Prove that the fraction \(\frac{21n+4}{14n+3}\) is irreducible for every natural number \(n\).
• To show that a fraction is irreducible, we need to prove that the numerator and denominator are relatively prime. Note that we have \(3 (14n+3) - 2 (21n+4) = 1\), \(\forall n \in \mathbb{N}\). Let \(d\) be the g.c.d of \(21n+4\) and \(14n+3\). Hence, \(d | \left( 3 (14n+3) - 2 (21n+4) = 1 \right) \). Hence, \(d | 1 \implies d = 1\). Hence, \(21n+4\) and \(14n+3\) are relatively prime. Hence, the fraction \(\frac{21n+4}{14n+3}\) is irreducible for every natural number \(n\).
2. For what real values of \(x\) is \[\sqrt{\left( x + \sqrt{2x-1} \right)} + \sqrt{\left( x - \sqrt{2x-1} \right)} = A,\] given (a) \(A = \sqrt{2} \), (b) \(A = 1\), (c) \(A = 2\), where only non-negative real numbers are admitted for square roots?
• Only non-negative real numbers are admitted for square roots, we need \(2x-1 \geq 0\) and \(x \geq \pm \sqrt{2x-1}\). The two conditions yield us \(x \geq \frac12\). Squaring both sides, we get, \[\left( x + \sqrt{2x-1} \right) + \left( x - \sqrt{2x-1} \right) + 2 \sqrt{\left( x + \sqrt{2x-1} \right)\left( x - \sqrt{2x-1} \right)} =A^2\] \[2x + 2 \sqrt{x^2 -2x + 1} = A^2\] \[2x + 2 \left \lvert x - 1 \right \rvert = A^2 \]
• If \(x \geq 1\), we get \[2x + 2x - 2 = A^2 \implies 4x = A^2 + 2 \implies x = \frac{A^2 + 2}{4}\] Hence, if \(A \geq \sqrt{2}\), we have \(x = \frac{A^2 + 2}{4}\).
• If \(\frac12 \leq x \leq 1\), we get \(2x + 2 - 2x = A^2 \implies 2 = A^2\), \(\forall x \in \left[\frac12,1\right]\).
• So the solution can be written as follows: \(x = \left \{ \begin{array}{lr} \frac{A^2+2}{4} & \text{If } A \gt \sqrt{2}\\ \text{Any value }\in \left[\frac12,1\right] & \text{If } A = \sqrt{2} \\ \text{No solution } & \text{If }A \lt \sqrt{2} \end{array} \right. \)
• For the current problem, we get \(x = \left \{ \begin{array}{lr} \frac{3}{2} & \text{If } A = 2 \\ \text{Any value }\in \left[\frac12,1\right] & \text{If } A = \sqrt{2} \\ \text{No solution } & \text{If }A = 1 \end{array} \right. \)
3. Let \(a,b,c\) be real numbers. Consider the quadratic equation in \(\cos(x)\) : \[ a \cos^2(x) + b \cos(x) + c = 0. \] Using the numbers \(a,b,c \) form a quadratic equation in \(\cos(2x)\), whose roots are the same as those of the original equation. Compare the equations in \(\cos(x)\) and \(\cos(2x)\) for \(a=4\), \(b=2\) and \(c=-1\).
• We have \(\cos^2(x) = \frac{1 + \cos(2x)}{2}\). Hence, the equation becomes \[\displaystyle a \left( \frac{1 + \cos(2x)}{2} \right) + b \sqrt{\frac{1 + \cos(2x)}{2}} + c = 0\] Rearranging and squaring both sides, we get \[\left( a \left( \frac{1 + \cos(2x)}{2} \right) + c \right)^2 = b^2 \left( \frac{1 + \cos(2x)}{2} \right) \] \[ a^2 + a^2 \cos^2(2x) + 4c^2 + 2a^2 \cos(2x) + 4ac + 4ac \cos(2x) = 2b^2 + 2b^2 \cos(2x)\] \[a^2 \cos^2(2x) + (2a^2 + 4ac -2 b^2) \cos(2x) + (a^2 + 4c^2 + 4ac - 2b^2) = 0\] Plugging in \(a = 4, b=2\) and \(c=-1\), we get the equation in terms of \(\cos(x)\) as \[4 \cos^2(x) + 2 \cos(x) - 1 = 0\] and the equation in terms of \(\cos(2x)\) as \[16 \cos^2(2x) + 8 \cos(2x) - 4 = 0.\] Hence, \(\cos(x)\) and \(\cos(2x)\) satisfy the same quadratic equation.

Algorithms - Exercises from Chapter 0

1. In each of the following situations, indicate whether \(f = \mathcal{O}(g)\) (or) \(f = \Omega(g)\) or both (in which case \(f = \Theta(g)\)).
• \(n-100 = \Theta(n-200)\)
• \(n^{1/2} = \mathcal{O}(n^{2/3})\)
• \(100n + \log n = \mathcal{O}(n + (\log n)^2)\)
• \(n \log n = \Theta (10n \log 10n)\)
• \(\log 2n = \Theta (\log 3n)\)
• \(10 \log n = \Theta (\log \left( n^2 \right))\)
• \(n^{1.01} = \Omega (n \log^2 n)\)
• \(n^2 / \log n = \mathcal{O}(n (\log n)^2)\)
• \(n^{0.1} = \mathcal{O}(\left( \log n \right)^{10})\)
• \((\log n)^{\log n} = \Omega(n / \log n\))
• \(\sqrt{n} = \Omega ((\log n)^3)\)
• \(n^{1/2} = \mathcal{O}(5^{\log_2n})\)
• \(n2^n = \mathcal{O}(3^n)\)
• \(2^n = \Theta (2^{n+1})\)
• \(n! = \Omega (2^n)\)
• \(\left(\log n \right)^{\log n} = 2^{\left(\log_2 n \right)^2}\)
• \(\sum_{i=1}^{n} i^k = \Theta (n^{k+1})\)
2. Show that, if \(c\) is a positive real number, then \(g(n) = 1 + c + c^2 + \cdots + c^n\) is:
• \(\Theta(1) \) if \(c \lt 1\)
• \(\Theta(n) \) if \(c = 1\)
• \(\Theta(c^n) \) if \(c \gt 1\)
• Solution: We have that \(g(n) = \frac{c^{n+1}-1}{c-1}\) whenever \(c \neq 1\). Note that \(g(n)\) is a monotonously increasing function for all positive real \(c\) i.e. we have \(g(n+1) \gt g(n)\).
• If \(c \lt 1\), we have \(1 \leq g(n) \lt \frac1{1-c}\), for all \(n \in \mathbb{Z}^+\). Hence, we get \(g(n) = \Theta(1)\).
• If \(c = 1\), we have \(g(n) = n+1\). Hence, we have that \(g(n) = \Theta(n)\).
• Since \(c \in \mathbb{R}^+\), we have \(g(n) \gt c^n, \forall n \in \mathbb{Z}^+\). For \(c \gt 1\), choose \(k = \frac{c}{c-1}\). We have \(1 + c + c^2 + \cdots + c^n =\frac{c^{n+1}-1}{c-1} \lt \frac{c^{n+1}}{c-1} = \frac{c}{c-1} c^n = k c^n\). Hence, we have for any \(n\), \[c^n \lt 1 + c + c^2 + \cdots + c^n \lt k c^n.\] Hence, we get \(g(n) = \Theta(c^n)\).
3. The Fibonacci numbers are defined by the rule \[F_0 = 0, F_1 = 1, F_{n} = F_{n-1} + F_{n-2}, n \geq 2.\] In this problem, we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.
• Use induction to prove that \(F_n \geq 2^{0.5n}\) for \(n \geq 6\).
• We have \(F_6 = 8 = 2^{0.5 \times 6}\) and \(F_7 = 13 \gt 12 \gt 8 \times 1.5 \gt 8 \times \sqrt{2} = 2^{3.5}\). Assume that for all \(k\) such that \(6 \leq k \leq m\), we have \(F_k \geq 2^{0.5k}\). We have \(F_{m+1} = F_{m} + F_{m-1} \gt 2^{0.5 m} + 2 ^{0.5 (m-1)} = 2 ^{0.5 m} \left(1 + \frac1{\sqrt{2}} \right) \gt 2^{0.5 m} \sqrt{2} = 2^{0.5 (m+1)}.\) We have checked the base cases for \(k=6\) and \(k=7\) and hence by induction we have \(F_n \geq 2^{0.5n}\). Hence proved.
• Find a constant \(c \lt 1\) such that \(F_n \leq 2^{cn}\) for all \(n \geq 0\). Show that the answer is correct.
• We need \(2^{c(n+1)} \geq 2^{cn} + 2^{c(n-1)}\) i.e. we need \(2^c \geq 1 + \frac1{2^c}\). Setting \(2^c = x\), we need \(x\) such that \(x \geq 1 + \frac1x\) i.e. we need \(x\) such that \(x^2 \geq x + 1\). Since we have \(x = 2^c\) and \(0 \leq c \lt 1\), we need \(x\) such that \(1 \leq x \lt 2\). Setting \(x^2 - x - 1 = 0\), we get \(x = \frac{1 \pm \sqrt{5}}{2}\). Since \(1 \leq x \lt 2\), we get \(x = \frac{1 + \sqrt{5}}{2}\). Hence, set \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\). We shall now check that setting \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\), we have \(F_n \leq 2^{cn}\). Clearly, we have \(F_0 = 0 \lt 1 = 2^{c \times 0}\). Similarly, we have \(F_1 = 1 \lt \frac{1 + \sqrt{5}}{2} = 2^{\log_2 \left(\frac{1 + \sqrt{5}}{2}\right)}\). Assume that we have \(F_k \leq 2^{ck}\) for all \(k \leq m\). Hence, we get \(F_{m+1} = F_m + F_{m-1} \leq 2^{cm} + 2^{c(m-1)} = 2^{cm} \left(1 + \frac1{2^c} \right) = 2^{cm + c} = 2^{c(m+1)}\). Hence, \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
• What is the largest \(c\) you can find for which \(F_n = \Omega (2^{cn})\)?
• By a similar argument as above, we get that \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
4. Is there a faster way to compute the \(n^{th}\) Fibonacci number? One idea involves \(matrices\). We start by writing the equations \(F_1 = F_1\) and \(F_2 = F_0 + F_1\) in matrix notation: \[ \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] Similarly, \[\begin{pmatrix}F_2 \\ F_3 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^2 \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] and in general, we have \[\begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] So, in order to compute \(F_n\), it suffices to raise this \(2 \times 2\) matrix, call it \(X\), to the \(n^{th}\) power.
• Show that two \(2 \times 2\) matrices can be multiplied using \(4\) additions and \(8\) multiplications.
• \[\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} e & f \\ g & h \end{pmatrix} = \begin{pmatrix} a \times e + b \times g & a \times f + b \times h \\ c \times e + d \times g & c \times f + d \times h \end{pmatrix}\] Hence, it is clear that we need \(4\) additions and \(8\) multiplications.

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

This post contains the solution to the exercises of the book by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani named "Algorithms". This post is a work in progress.

1. Exercises in Chapter 0
2. Exercises in Chapter 1

Elementary Number Theory - 1 Problems

1. Suppose that \(a,b,c \in \mathbb{N}\). Prove each of the following:
• If \(a|b\) and \(b|c\), then \(a|c\).
• Since \(a|b\) and \(b|c\), we have \(b= ak_1\) and \(c = b k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, we get \(c = b k_2 = a k_1 k_2 = a (k_1 k_2)\). Since \(k_1,k_2 \in \mathbb{Z}\), we get \(k_1 k_2 \in \mathbb{Z}\). Hence, we get \(a | c\).
• If \(a|b\) and \(a|c\), then \(a| (bx+cy)\) for every \(x,y \in \mathbb{Z}\).
• Since \(a|b\) and \(a|c\), we have \(b = a k_1\) and \(c = a k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, \(bx + cy = a k _1 x + a k_2 y = a \left(k_1 x + k_2 y \right)\). Note that since \(k_1,k_2,x,y \in \mathbb{Z}\), we have \(k_1 x + k_2 y \in \mathbb{Z}\). Hence, we get \(a | \left( bx + cy \right)\).
2. Prove that if \(n \in \mathbb{N}\) is composite, then it has a prime factor not exceeding \(\sqrt{n}\).
• Let \(n = p_1 p_2 \ldots p_r\) where \(p_i\)'s are prime not necessarily distinct. Further we are given that \(n\) is composite. Hence, we have \(r \geq 2\). Now assume the contrary that all the prime factors of \(n\) exceed \(\sqrt{n}\) i.e. \(p_k > \sqrt{n}\), \(\forall k \in \{1,2,\ldots,r \}\). Then \(n = p_1 p_2 \ldots p_r > \left(\sqrt{n} \right)^r = n^{r/2}\). Hence, we have \(n > n^{r/2}\). This implies \(r < 2\). This contradicts the fact that \(r \geq 2\). Hence there is at-least one prime factor not exceeding \(\sqrt{n}\).
3. Prove that \(n^4 + 4\) is composite for every natural number \(n > 1\).
• \(n^4 + 4 = n^4 + 4n^2 + 4 - 4n^2 = \left(n^2+2 \right)^2 - \left( 2n \right)^2 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\). Note that \(n^2+2 + 2n > n^2 + 2 -2n\), \(\forall n \in \mathbb{N}\). For \(n > 1\), we have \(n^2 + 2 -2n = (n-1)^2 + 1 > 1\). Hence, \(n^4 +4 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\) where \(\left( n^2+ 2 + 2n \right) \in \mathbb{Z}\) and \(\left( n^2 + 2 - 2n\right) \in \mathbb{Z}\). Further for \(n > 1\), we have \(\left( n^2+ 2 + 2n \right) > \left( n^2+ 2 - 2n \right) > 1\). Hence, \(n^4 +4\) is a product of two natural numbers greater than \(1\). Hence, \(n^4+4\) is composite for every natural number \(n > 1\).

Elementary Number Theory - 1.3 Definitions and Propositions

Theorem: (Euclid)
There are infinitely many primes.


Proof:
This is a classic proof by contradiction. Assume that there are only finitely many primes, say \(n\) of them and denote them by \(\mathbb{P} = \{p_1,p_2,\ldots,p_n\}\). Consider the number \(m = p_1p_2 \ldots p_n +1\). If \(m\) is a prime, we have \(m \neq p_l\) for any \(l \in \{1,2,\ldots,n\}\). Hence, we have constructed a new prime not in \(\mathbb{P}\). This means either \(m\) is not a prime (or) there are infinitely many primes. Hence, if \(m\) is a prime, we have proved that there are infinitely many primes. If \(m\) is not a prime, then since \(m\) is also not an irreducible, and since we have assumed that only finitely many primes exist, we have that \(p_i | m\) for some \(p_i\). But we have \(m - p_1p_2 \ldots p_n = 1\). This means the \(p_i | 1\). CONTRADICTION. Hence, there are infinitely many primes.

Definition:
The greatest integer part of a real number \(\alpha\), denoted by \(\lfloor \alpha \rfloor\), is the greatest integer less than or equal to \(\alpha\) i.e. the unique integer \(m \in \mathbb{Z}\) such that \(m \leq \alpha \lt m+1\).


Proposition:
Suppose \(\alpha,\beta \in \mathbb{R}\).

1. We have \(\alpha-1 \lt \lfloor \alpha \rfloor \leq \alpha\) and \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\).
• By definition, we have that \(\lfloor \alpha \rfloor \in \mathbb{Z}\) such that \(\lfloor \alpha \rfloor \leq \alpha \lt \lfloor \alpha \rfloor + 1\). Rearranging the inequalities, we get \(\alpha - 1 \lt \lfloor \alpha \rfloor \leq \alpha\). Again by rearranging, we get \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\).
2. If \(\alpha \geq 0\), then \(\lfloor \alpha \rfloor\) counts the number of positive integers not exceeding \(\alpha\). In other words, \[\lfloor \alpha \rfloor = \sum_{1 \leq n \leq \alpha} 1.\]
• \(\sum_{1 \leq n \leq \alpha}\) 1 = \(\sum_{1 \leq n \leq \lfloor \alpha \rfloor} 1 + \sum_{\lfloor \alpha \rfloor \lt n \leq \alpha} 1\). Since we have \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\), the contribution of the second term is zero as there is no integer \(n\) such that \(\lfloor \alpha \rfloor \lt n \leq \alpha\). The first term is nothing but \(\lfloor \alpha \rfloor\).
3. For every \(n \in \mathbb{Z}\), we have \(\lfloor \alpha + n \rfloor = \lfloor \alpha \rfloor + n\).
• Let \(\lfloor \alpha \rfloor = m \in \mathbb{Z}\). We have that \(m \leq \alpha \lt m+1\). Hence, we have \(m + n \leq \alpha + n \lt (m+n) + 1\). Hence, we get \(\lfloor \alpha +n \rfloor = m + n = \lfloor \alpha \rfloor + n\).
4. We have \(\lfloor \alpha \rfloor + \lfloor \beta \rfloor \leq \lfloor \alpha + \beta \rfloor \leq \lfloor \alpha \rfloor + \lfloor \beta + 1\).
• Let \(\lfloor \alpha \rfloor = m\) and \(\lfloor \beta \rfloor = n\). This means \(m \leq \alpha \lt m + 1\) and \(n \leq \beta \lt n + 1\). Adding the two, we get \(m + n \leq \alpha + \beta + m + n + 2\). Hence, we get \(\lfloor \alpha \rfloor + \lfloor \beta \rfloor \leq \lfloor \alpha + \beta \rfloor \leq \lfloor \alpha \rfloor + \lfloor \beta + 1\).
5. If \(\alpha \in \mathbb{Z}\), then \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = 0\). If \(\alpha \not \in \mathbb{Z}\), then \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = -1\).
• If \(\alpha \in \mathbb{Z}\), then \(-\alpha \in \mathbb{Z}\). Hence, we have \(\lfloor \alpha \rfloor = \alpha\) and \(\lfloor -\alpha \rfloor = - \alpha\). Hence, \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = \alpha + (- \alpha) = 0\). If \(\alpha \notin \mathbb{Z}\), then let \(m = \lfloor \alpha \rfloor\). Since \(\alpha \notin \mathbb{Z}\), we get \(m \lt \alpha \lt \alpha + 1\). Multiplying by negative one, we get \(-m-1 \lt -\alpha \lt -m \). This means \(\lfloor \alpha \rfloor = - m - 1\). Hence, we get \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = m + (-m-1) = -1\).
6. The number \(- \lfloor -\alpha \rfloor\) is the smallest integer not less than \(\alpha\).
• Let \(m = \lfloor \alpha \rfloor\). If \(\alpha \in \mathbb{Z}\), then \(m = \alpha\). We get \(-\alpha = -m \in \mathbb{Z}\). Hence, \(- \lfloor -\alpha \rfloor = m\) which is nothing but the smallest integer not less than \(\alpha\). If \(\alpha \notin \mathbb{Z}\), then \(m \lt \alpha \lt m + 1\). Hence, \(-m - 1 \lt -\alpha \lt -m \). Hence, we get \(\lfloor -\alpha \rfloor = - m - 1\). Hence, we get \(- \lfloor -\alpha \rfloor = m + 1\) which is nothing but the smallest integer not less than \(\alpha\).
7. If \(n \in \mathbb{Z}^+\), then \(\lfloor \lfloor \alpha \rfloor / n \rfloor = \lfloor \alpha/n \rfloor\).
• If \(\alpha \in \mathbb{Z}\), then it follows trivially since \(\lfloor \alpha \rfloor = \alpha\). If \(\alpha \notin \mathbb{Z}\), let \(m = \lfloor \alpha \rfloor\). We then have \(m = qn + r\) where \(r \in \{0,1,2,\ldots,n-1\}\). Hence, \(\alpha = qn + r + \{\alpha\}\) where \(\{\alpha\} \in [0,1)\). Note that \(r + \{\alpha\} \in (0,n)\). We then get \(\lfloor \lfloor \alpha \rfloor / n \rfloor = \lfloor \frac{qn+r}{n} \rfloor = q\). We also get \(\lfloor \alpha/n \rfloor = \lfloor (qn + r + \{\alpha\})/n \rfloor\) = q. Hence, we get the desired result.
8. The number \(\lfloor \alpha + \frac12 \rfloor\) is one of the two nearest integers to \(\alpha\). Furthermore, if these two integers differ from \(\alpha\) by the same value, then \(\lfloor \alpha + \frac12 \rfloor\) is the larger of these two integers.
• Follows immediately from the definition.
9. If \(\alpha \gt 0\) and \(n \in \mathbb{N}\), then \(\lfloor \frac{\alpha}{n} \rfloor\) is the number of positive integers not exceeding \(\alpha\) and which are multiples of \(n\).
• Follows from the second part of this problem.

Theorem:

Suppose that \(n \in \mathbb{N}\) and \(p\) is a prime. Then the largest integer \(k\) such that \(p^k | n!\) is given by \[k = \sum_{j=1}^{\infty} \left \lfloor \frac{n}{p^j} \right \rfloor .\]
Proof:
Let \(r_m\) be the highest power of \(p\) dividing \(m\). Then we get \(k = \displaystyle \sum_{m=1}^{n} r_m\). We have \(r_m = \displaystyle \sum_{l=1}^{\infty} 1_{\{p^l | m\}} \). Hence, we get \(k = \displaystyle \sum_{m=1}^{n} \sum_{l=1}^{\infty} 1_{\{p^l | m\}} = \sum_{l=1}^{\infty} \sum_{m=1}^{n} 1_{\{p^l | m\}} = \sum_{l=1}^{\infty} \left \lfloor \frac{n}{p^l} \right \rfloor\). Hence, the largest integer \(k\) such that \(p^k | n!\) is given by \[k = \sum_{j=1}^{\infty} \left \lfloor \frac{n}{p^j} \right \rfloor .\]