Assume head comparison and construction of one list cell take constant time. In the merge algorithm, every comparison removes one head from the recursive inputs, and evaluation stops as soon as either is empty. For lengths $m,n>0$, at most $m+n-1$ comparisons and the same number of newly constructed cells are required; the untouched suffix is shared. Inputs which keep both lists nonempty until the last comparison attain this bound. ThusAn initially empty input makes this particular implementation constant-time; not every pair requires linear work.

The balanced merge sort spends $\Theta (n)$ time per call on list length, splitting and merging. Hence its time complexity satisfiesAt each recursion level the lengths of its disjoint subproblems sum to $n$, so the work per level is $\Theta (n)$, and balanced splitting gives $\Theta (\log n)$ levels. ConsequentlyThe length and splitting traversals change the constant factor, not this asymptotic order; repeatedly inserting elements into a sorted list would not give the same complexity.

Split the list into two contiguous halves, sort each recursively, and use the merge algorithm from part (a):List.length counts elements, List.take(xs,k) returns the first $k$ elements and List.drop(xs,k) returns the remaining suffix. Since $0<k<n$ when $n\ge 2$, both recursive inputs are smaller and differ in length by at most one. Mathematical induction on length proves that each half is sorted without losing elements, and the correctness of the merge algorithm proves the same for the combined result. Contiguous splitting and left-biased equal-key merging preserve the original relative order of equal keys. This is a stable top-down merge sort.

For integer linked lists, compare their heads and copy the smaller head, retaining the other list for the next step:This merge algorithm preserves duplicates and chooses the left list on a tie, making it stable when elements have an ordering key. Each recursive step decreases the combined length. For correctness, the chosen head is no greater than either remaining head and therefore no greater than any remaining element; structural induction then proves that the result is ordered and contains exactly the elements of both inputs. For other element types, replace the integer comparison by a supplied ordering function. Merge repeatedly emits the smaller head and reuses the remaining list when the other becomes empty.

Along the holonomic constraint $z=x^2/(4a)$, we have $\dot{z}=x\dot{x}/(2a)$ and hence speed squared $(1+x^2/(4a^2)){\dot{x}}^2$. The smooth wire's normal reaction is perpendicular to the permitted velocity and does no work. Conservation of mechanical energy, with release from rest at height $h$, givesThe turning points are $x=\pm x_0$ with $x_0=2\sqrt{ah}$. One full oscillation has twice the travel time between them:Set $x=x_{0}u$ and $\beta =h/a$. After cancelling the scale factors,so the bead on a parabolic wire hasFor $\beta \ll 1$, expand the numerator uniformly on $[-1,1]$:The integrable endpoint weight gives ${\int }_{-1}^1(1-u^2{)}^{-1/2}du=\pi$ and ${\int }_{-1}^1{u}^2(1-u^2{)}^{-1/2}du=\pi /2$, for example by $u=\sin \theta$. Therefore the requested small-oscillation period isThe leading frequency is $\sqrt{g/(2a)}$, and the first finite-amplitude correction increases the period. At $h=0$ the ring is stationary; the expression is the limiting period of nonzero small oscillations.

The relevant parameters are $a,h,g$ and the ring mass $m$, with dimensions length, length, length/time${}^2$ and mass. The wire is fixed and smooth, so there is no additional friction parameter. Because $m$ is the only parameter carrying a mass dimension, it cannot enter a dimensionless group governing the period. Using $a$ and $g$ as the length and time scales, the independent dimensionless variables are $T\sqrt{g/a}$ and $h/a$. Dimensional analysis therefore givesThe physical mass cancellation also follows from the energy equation in part (ii), since kinetic and gravitational potential energy are both proportional to $m$.

The Fermat-Euler theorem states that, for a positive integer $q$ and an integer $a$ coprime to $q$, $a^{\phi (q)}\equiv 1(\mathrm{mod}q)$, where the Euler totient function $\phi (q)$ counts residue classes coprime to $q$. The case $q=1$ is trivial. For $q>1$, let $r_1,\dots ,r_{\phi (q)}$ be a reduced residue system. Multiplication by $a$ permutes it: equality of two resulting residues can be cancelled using the modular inverse of $a$, and the products remain coprime to $q$. Multiplying the residues before and after the permutation givesEvery factor on the right is a unit, so its product can be cancelled. This provesThe integer $359$ is prime: none of the primes $2,3,5,7,11,13,17$ up to $\sqrt{359}<19$ divides it. Therefore $\phi (359)=358$. Apply the theorem to $60$ and use the supplied congruence:To connect this to individual digits rather than merely assert periodicity, use long-division remainders $r_0=1$ andInduction gives $r_n\equiv 10^n(\mathrm{mod}359)$. Since $10$ is coprime to $359$, no remainder is zero. The congruence above therefore implies $r_{n+179}=r_n$ for every $n\ge 0$, using the unique representative in $1,\dots ,358$. In particularHenceThis is the mechanism of decimal period from multiplicative order: the period divides $179$.

If the prime $p$ does not divide $x$, then $\gcd (p,x)=1$. The Bezout identity gives integers $a,b$ with $ap+bx=1$. Multiplying by $y$ gives $apy+bxy=y$. If $p\mid xy$, both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma holds:For completeness, existence in the fundamental theorem of arithmetic follows by strong induction on a positive integer $n>1$. If $n$ is prime there is nothing to prove; otherwise $n=ab$ with $1<a,b<n$, and the inductive prime factorizations of $a,b$ give one for $n$. The integer $1$ has the empty factorization.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma shows that $p_1$ divides some $q_j$. Both are primes, so they are equal. Reorder the second list, cancel this equal factor, and repeat. All factors must be matched, including their multiplicities. Thus prime factorization exists and is unique up to the order of its factors. For nonzero negative integers one also records the sign.

Factor the expression as $n^3-n=(n-1)n(n+1)$. One of three consecutive integers is divisible by $3$, so $3\mid n^3-n$. If $n$ is odd, its neighbours $n-1$ and $n+1$ are consecutive even integers. One is divisible by $4$ and the other by $2$, so their product is divisible by $8$. Since $3$ and $8$ are coprime integers, their product divides the expression:The argument also includes negative odd integers and the zero product at $n=\pm 1$.

The Euclidean algorithm givesBack-substitution supplies the Bezout identityThus one solution is $(x,y)=(-5,2)$. If $(x,y)$ is any solution, subtraction gives $7(x+5)+18(y-2)=0$. Since $7$ and $18$ are coprime, $18$ divides $x+5$. Write $x+5=18t$; substitution then gives $y-2=-7t$. Conversely these values satisfy the equation for every integer $t$. Hence all solutions are

Let $r=|{\mathbf{r}}_1-{\mathbf{r}}_2|$ and $\hat{\mathbf{r}}=({\mathbf{r}}_1-{\mathbf{r}}_2)/r$. A differentiable central potential energy gives the internal forcesThere are no external forces. Differentiating the total kinetic energy and using Newton's second law therefore givesSince $\dot{r}=\hat{\mathbf{r}}\cdot ({\mathbf{v}}_1-{\mathbf{v}}_2)$, the last expression is $-U^{\prime }(r)\dot{r}=-dU/dt$. ThusThis conserves total mechanical energy, including the kinetic energy of centre-of-mass motion, not merely the relative kinetic energy.

Write ${\mathbf{r}}_i=\mathbf{X}+{\mathbf{r}}_i^{\prime }$ and ${\mathbf{v}}_i=\mathbf{V}+{\mathbf{v}}_i^{\prime }$, where $\mathbf{V}=\dot{\mathbf{X}}$. The definition of the centre of mass and its derivative giveExpand the total angular momentum:The two middle terms vanish. Thus the angular momentum decomposition about the centre of mass isThe first term is orbital angular momentum of the centre; the second is angular momentum about the centre of mass.

About a fixed inertial origin, the total angular momentum is $\mathbf{L}={\sum }_i{m}_i{\mathbf{r}}_i\times {\dot{\mathbf{r}}}_i$. Differentiation givesbecause ${\dot{\mathbf{r}}}_i\times {\dot{\mathbf{r}}}_i=0$. Separate the external and internal contributions. The combined torque of an internal pair isThe first equality uses Newton's third law, and the second uses the given central-force condition. All internal torques therefore cancel, leavingAn equal-and-opposite pair which is not central need not have zero combined torque; this explains why both internal-force hypotheses matter.

For constant particle masses define the centre of mass by $M\mathbf{X}={\sum }_i{m}_i{\mathbf{r}}_i$, with $M={\sum }_i{m}_i$. Summing Newton's second law over all particles givesEach pair of internal forces cancels by Newton's third law. HenceOnly the action-reaction condition is needed for this translation law; centrality of the internal forces is needed for the angular momentum result in part (ii).

Let $q(t)=\mathbf{r}(t)\cdot \mathbf{B}$. Since the field is constant, dotting the equation of motion with $\mathbf{B}$ eliminates the magnetic term:This is a harmonic oscillator with frequency $\omega =\sqrt{k/m}$. Initially $q(0)={\mathbf{r}}_0\cdot \mathbf{B}$ and $\dot{q}(0)=0$, because the particle starts at rest. ThereforeThe magnetic force modifies the transverse motion but not this projection. The formula also holds trivially when $\mathbf{B}=0$.

Write $\mathbf{v}=\dot{\mathbf{r}}$. The original PDF contains the cross product $\dot{\mathbf{r}}\times \mathbf{r}$; the TeX aid drops its velocity dot. Since $\mathbf{v}\times \mathbf{v}=0$, differentiation and the equation of motion giveThe radial restoring force contributes no torque. The vector triple-product identity yieldsMeanwhileThe derivatives cancel, provingThis is the magnetic axial angular-momentum invariant. Its first term is the negative of the ordinary angular momentum projected on $\mathbf{B}$; retaining that sign is essential.

Dot Newton's second law with $\dot{\mathbf{r}}$. The magnetic cross-product term is perpendicular to this velocity, soThusorThe two halves are the kinetic energy and the isotropic spring's potential energy. The expression in the question is twice their sum. The Lorentz force changes the direction of motion but supplies no power, because it is perpendicular to velocity; this explains why the magnetic field does not appear in the conserved mechanical energy. The sign corresponds to charge $-e$.

Assume $P,Q$ are continuously differentiable on a neighbourhood of a bounded region with a positively oriented piecewise smooth simple boundary. To prove Green theorem, first take a region between the graphs $y=f(x)$ and $y=g(x)$, $a\le x\le b$, with $f\le g$. Counterclockwise orientation traverses the lower graph to the right and the upper graph to the left; vertical end pieces contribute nothing to $Pdx$. Thus the fundamental theorem of calculus givesLikewise, for a region between graphs $x=u(y)$ and $x=v(y)$, the right boundary is traversed upwards and the left one downwards. Horizontal end pieces contribute nothing to $Qdy$, soFor a polygonal region, triangulate its interior. Each triangle is of both graph types with piecewise linear bounds, so adding the formulae gives the result: the double integrals add and the integrals on internal edges cancel because the adjacent triangles traverse them in opposite directions. For a regular piecewise smooth simple boundary, choose inscribed simple polygonal approximations to its piecewise smooth parametrization. Their line integrals converge to the original line integral, since the parametrizations converge uniformly and their piecewise constant tangent vectors converge in the integral norm on each smooth arc. Their regions converge in area: the symmetric difference lies in a shrinking neighbourhood of the original boundary, which has planar measure zero. Boundedness of the continuous integrand then gives convergence of the area integrals. Passing to the limit proves the formula for the stated boundary class. Combining the two identities givesPositive orientation is essential for the sign.

Choose $P=-y/2$ and $Q=x/2$, for which $Q_x-P_y=1$. The boundary formula for planar area isFor the ellipse, take $a,b>0$ so the given increasing-angle parametrization is counterclockwise. Then $dx=-a\sin \theta d\theta$ and $dy=b\cos \theta d\theta$, soIf signed nonzero parameters are allowed, the unsigned area is $\pi |ab|$, with orientation corrected accordingly.

A conservative vector field is the gradient of a single-valued differentiable scalar potential. Its line integral is path independent and equals the potential difference. If $\psi \mathbf{A}=\nabla F$ with a twice continuously differentiable potential, equality of mixed partial derivatives givesThe product rule then gives ${\psi }_y{A}_1+\psi A_{1,y}={\psi }_x{A}_2+\psi A_{2,x}$. Rearranging proves the integrating-factor equation for a planar vector field:This argument does not require division by $\psi$, so it remains valid even at its zeros. A nonvanishing integrating factor is normally sought when one wants to recover useful potential curves for the original field.

TakeThe real eigenvalues are one and two, with eigenlines spanned by $(1,0{)}^T$ and $(1,1{)}^T$ respectively. These independent vectors form a real eigenbasis, so $E$ is a diagonalizable matrix over $\mathbb{R}$. Their inner product is one, and any two nonzero vectors on those eigenlines have nonzero inner product. Rescaling can normalize their lengths but cannot make them orthogonal. Hence no orthonormal eigenbasis exists.

UseIt has independent complex eigenvectors $(1,-i{)}^T$ and $(1,i{)}^T$, with eigenvalues $i$ and $-i$. Taking these as columns gives an invertible complex matrix $P$ with $P^{-1}DP=\mathrm{diag}(i,-i)$, so $D$ is a diagonalizable matrix over $\mathbb{C}$. It cannot be diagonalized over $\mathbb{R}$, since a real diagonal matrix would have real eigenvalues, whereas similarity preserves the characteristic polynomial.