The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 4 Question 17

The figure shows a non-overlapping trace on a \(4\times4\) grid which visits all points exactly once. Imagine the same type of trace on an \(n\times n\) grid, where \(n\) can be arbitrarily large. Using the fact that \(\sum_{k=1}^\infty {1\over k}\) diverges to infinity, show that the sum of all acute angles of the trace also diverges to infinity when \(n\) tends to infinity, despite the angles tending to 0 the closer the path gets to the grid's diagonal.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. Let's prove that \(\sum_{k=1}^{\infty}{\frac{1}{k}}\) diverges. For each \(n,\) how many terms in the series are between \(\frac{1}{2^n}\) (inclusive) and \(\frac{1}{2^{n+1}}\) (exclusive)? By bounding each term \(\frac{1}{k}\) in the original series with the largest \(\frac{1}{2^n}\) such that \(\frac{1}{2^n} \leq \frac{1}{k},\) compute this new sum. Hence argue why \(\sum_{k=1}^{\infty}{\frac{1}{k}}\) diverges.

  2. (Source: Wikipedia) Using this diagram, express \(\sin \theta, \cos \theta\) and \(\tan \theta\) in terms of \(x.\) Hence show that \(\cos(\arcsin x) = \sqrt{1-x^2}.\) Find a similar expression for \(\cos(\arctan x).\)

Hints

  • Hint 1
    To show the sum of all the angles diverges, it suffices to show the sum of a subset of the angles diverges.
  • Hint 2
    Express the \(i^{th}\) largest angle \(\theta_i\) that touches the top of the square in terms of \(i\).
  • Hint 3
    The angle \(\theta_i\) can be expressed as the difference between two angles.
  • Hint 4
    The larger angle is \(\frac{\pi}{4}\), and the tangent of the smaller angle can be expressed as the ratio between the sides of the triangle along the grid.
  • Hint 5
    Remember that the function \(\tan x\) is concave in the region \((0,\frac{\pi}{4}).\)
  • Hint 6
    For positive integer \(i,\) \(0 < \frac{i}{i+1} < 1,\) so \(\arctan \frac{i}{i+1}\) will lie in the region \((0,\frac{\pi}{4}).\)
  • Hint 7
    By drawing the graphs \(y = ({\frac{\pi}{4}})^{-1}x\) and \(y = \tan x,\) you can see that \(\tan x\) lies below the line in the region \((0,\frac{\pi}{4}).\)
  • Hint 8
    This means that \(\arctan \frac{i}{i+1} \leq \frac{\pi}{4}\frac{i}{i+1}.\)

Solution

The full sum \(S\) is greater than the sum of only the angles that touch the top of the square. Call this subsequence of angles \(\theta_i\). By considering the right-angled triangles with sides \(i\) and \(i+1, \theta_i\) can be derived as: \[ \begin{align} \theta_i &= \frac{\pi}{4} - \arctan{\frac{i}{i+1}} \\ &\geq \frac{\pi}{4} - \frac{\pi}{4}\frac{i}{i+1} \\ &= \frac{\pi}{4}(\frac{1}{i+1}) \end{align} \] where the inequality is due to the concavity of \(\tan x\) in the region \((0, \frac{\pi}{4})\) and \(\tan \frac{\pi}{4}=1.\) We then have that: \(S \geq \sum_{i=0}^\infty \theta_i \geq \frac{\pi}{4}\sum_{i=0}^{\infty}\frac{1}{i+1},\) and the latter diverges. Hence \(S\) diverges.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.