Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 212 2 Solution Created 2026-10-03 Updated 2026-10-06
Use the usual finite binary encoding of integer or rational input data. NP consists of decision problems whose yes-instances have polynomial-length certificates in computational complexity verifiable in polynomial time. A decision problem is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP. An optimization problem is NP-hard when computing its optimum would solve every NP decision problem through a polynomial-time reduction and an optimum-value query; membership in NP applies directly to decision problems, not to an unqualified optimization task.
Reduce subset sum to the 0-1 knapsack problem by setting and . Every feasible value is at most , and the optimum equals exactly when the subset sum answer is yes. The transformation and final comparison take polynomial time. Since subset sum is assumed NP-complete, exact knapsack optimization is NP-hard.
For the half-approximation algorithm for knapsack, use nonnegative weights and profits. Delete overweight items and nonpositive-profit items; take all positive-profit zero-weight items for free. On the remaining positive-weight items, sort decreasing . Take the maximal initial prefix fitting the capacity, and stop at the first item that would overflow. Let be the prefix profit, and let be the largest profit of any individually feasible remaining item. Return the better of the prefix and that singleton, together with the free items. If every item fits, take them all.
The fractional knapsack problem fills exactly that prefix and a fraction of the first excluded item. Its optimum bounds the integer optimum, and without the free items its value is at most . ThusWith total free profit , the same inequality is . This gives an approximation ratio of in sorting time, with polynomial bit complexity for rational data. Nonnegative weights and capacity are the standard knapsack problem assumptions; unrestricted negative weights would not support this argument.
For the quadratic knapsack problem and its fractional row bound for quadratic knapsack, multiply the capacity inequality by the binary and use :Remove items with first. If , the remaining coordinates are feasible in the fractional problem defining , so . If , that row's contribution is zero. Hence, with ,The double sum counts each symmetric interaction twice; there is no factor in this problem. Each is a fractional knapsack problem, computable by sorting positive ratios, also handling zero weights separately. This takes polynomial time even when some interactions are negative, because an optional fractional item with negative profit is omitted.
The resulting 0-1 knapsack problem need not be solved exactly. Relax its capacity constraint with a Lagrange multiplier . Its Lagrangian knapsack bound isFor feasible , adding only increases its objective, and maximizing over independent binary choices produces the displayed expression. It is a convex piecewise-linear function with breakpoints at positive . Evaluate those breakpoints and zero, or use the fractional knapsack problem ordering; the best bound is computable in polynomial time. Thus computing all and one additional Lagrangian relaxation gives the requested upper bound.
For the numerical example, the problem has capacity and item ratios and . Select and . This givesAn exchange argument justifies optimality: capacity used on the lower-ratio item can be transferred to the higher-ratio item until the latter is full. The stated and similarly follow from residual capacities and . Therefore , with ratios . The fractional solution takes items and one-third of item , yielding . At the Lagrangian knapsack bound gives the same value:The fractional solution attaining proves that this is the best bound from this auxiliary Lagrangian relaxation, though it need not be the exact quadratic optimum.
For branch and bound, branch on whether an unresolved is zero or one. If the selected set is , subtract its weight from the residual capacity and retain its exact objective as a constant. For each remaining item replace by , preserving the original interactions between remaining items. Recompute the fractional row bounds and the Lagrangian knapsack bound for that residual problem. Maintain an incumbent from genuine feasible binary solutions evaluated with the quadratic objective; prune infeasible nodes and nodes whose bound is no better than the incumbent. For example, selecting items gives the feasible value . A finite binary branching tree eventually certifies the optimum, but worst-case running time is exponential, as expected for an NP-hard problem.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 306 1 i Solution Created 2026-10-03 Updated 2026-10-06
Work away from , where the inverse-square potential is singular. Variation of the phase-space action givesThe last equation is the constraint imposed by the Lagrange multiplier . The canonical momentum conjugate to is , not . Consequently the nonzero canonical Poisson brackets areIn particular,With the convention , the Noether charge generating is . Equivalently, the conserved physical energy is ; a convention that calls the energy the time-translation charge absorbs this minus sign into its parameter.
For the dilation charge,on the constraint surface. Its infinitesimal canonical transformations areFor constant , extending this by preserves the action: the kinetic terms are invariant and scales oppositely to . Thus the dilation acts on time and position with their nonrelativistic relative scaling. Its Poisson bracket with the energy is
Put . Direct variation of the Hamiltonian givessoThe supplied transformations are generated by the special conformal charge of inverse-square mechanicsChooseThen even for a time-dependent parameter. Expanding the kinetic-term variation, keeping the terms in , givesHenceFor a constant parameter only the boundary term remains, identifying as the Noether charge. Independently, the equations of motion giveUsing the same canonical Poisson bracket convention,Together, , and form the sl2R Lie algebra of conformal mechanics. These are time translation, dilation and special conformal transformation. A useful normalization check is the Casimir elementon the constraint surface.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 311 3 a i Solution Created 2026-10-03 Updated 2026-10-06
There are no or terms in the displayed Einstein-Hilbert action, so the lapse function and shift vector have zero canonical momenta. Their equations impose constraint equations in field theory rather than independent propagation; they are Lagrange multipliers in the Hamiltonian formulation of general relativity.
With the question's positive sign for , vary at fixed . Since ,Thus the canonical momentum of the spatial metric is a weight-one tensor density. Write ; in three spatial dimensions , soThe action has suppressed its overall , and this normalization is retained here. Reversing the sign convention for extrinsic curvature would reverse the momentum relation; the calculation uses exactly the convention supplied in this question.
Past exam of the mathematics course of the University of Cambridge 2017 ib Paper 3 6D a Solution Created 2026-09-24 Updated 2026-10-05
For the boundary constraint , the Lagrange multiplier equations for areNeither coordinate can vanish at a stationary point. Substitution gives . For , and ; for , and . The constraint circle is compact, its gradient is nowhere zero, and every extremum must occur among these stationary points. ThusThe paired signs in each expression are linked. The inequality also confirms the global values.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 216 2 Solution Created 2026-10-03 Updated 2026-10-06
Write for the directed edges from parent to child and for the state at site . The global Markov property for an undirected graph on this tree, together with the specified parent transitions, gives the complete-data likelihood functionOne can obtain the factorization by successively removing terminal subtrees: after conditioning on their parent, each subtree is independent of the rest. The root factor and transition products also show that different sites are independent. Only ancestral states are latent variables.
At the current Markov kernel , define expected transition countsThe E-step of the expectation-maximization algorithm isMaximize separately for each row under and . For , the Lagrange multiplier equation is , with zero-count entries set to zero at a boundary maximum. Thus the EM transition-count update on a tree isIf , that row does not occur in ; any row probability distribution, including its previous value, maximizes the objective.
The expected counts can be computed exactly by the Felsenstein pruning algorithm and an outward belief propagation pass. For one site, let be the conditional probability of observations in the subtree below , given state . For a leaf with observed state , . For an internal vertex,Define as the joint mass of state at and all observations outside its subtree. The root has . For a child of , putThe edge posterior probability required above isMultiply the inside and outside factors to obtain the joint mass of the observations and endpoint states; division by the site likelihood function proves this expression. Sum over edges and sites to form . The two passes take operations on a binary tree. Scaling messages or computing them logarithmically avoids underflow.
A strictly positive initial Markov kernel ensures for every observed leaf pattern, so every E-step is defined. At a later boundary iterate, require positive likelihood for the actual data and restrict the conditional distribution to its support. EM likelihood monotonicity proves that the update cannot decrease observed-data likelihood function. It is a maximum-likelihood iteration, not a guarantee of finding the global maximum-likelihood estimate; different initial kernels may lead to different stationary points.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 331 4 a Solution Created 2026-10-03 Updated 2026-10-06
Use , , , and . Work along a sufficiently regular direct trajectory satisfying the given constraints. The zero spatial mean of the scalar field is conserved by incompressible flow, impermeable walls and zero scalar flux, so minimizing is equivalent to minimizing scalar variance, up to the fixed domain volume.
The printed functional fixes the initial state to a candidate ; it contains no term that enforces its kinetic energy. For the optimization over that candidate, add the real Lagrange multiplier constraintEquivalently, one can restrict all control variations to the sphere in a normed vector space of fixed kinetic energy. This term changes the initial-control optimality condition, not the interior adjoint equations.
Let , and . Linearization of the momentum and scalar transport residuals givesBoth appearances of the perturbation velocity in the nonlinear momentum term have been differentiated. In particular, the coefficient is the gradient of the total velocity, not just the base shear.
For the negative-constraint convention of the functional, integration by parts gives the interior coefficients of asThus the adjoint equations for Boussinesq scalar mixing areThe transpose is essential: the th component of is . The coupling transposes advection of the scalar by a velocity perturbation; transposes buoyancy feedback. Dropping the latter would give a passive scalar adjoint, not the active scalar problem.
These equations are integrated backward, not forward. If , they readwith direct coefficients evaluated at . Both terms from the diffusion equation now have the usual forward sign in . A direct-adjoint looping method stores or reconstructs the forward trajectory, solves these equations backward, and uses the initial adjoint as the control gradient. The endpoint and fixed-energy conditions below give necessary conditions for a local optimizer, not a global optimality theorem.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 343 1 i Solution Created 2026-10-03 Updated 2026-10-06
The term means that the generator is the grand potential, rather than just the physical energy. With boundary variations vanishing, the Hamiltonian functional isIts functional derivative isso the Gross–Pitaevskii equation is . Treating and as independent variables in this variation gives the factor , not .
For repulsive interactions and , complete the square in the local energy:The gradient contribution is nonnegative, so the homogeneous ground state has arbitrary constant complex argument andThe infinite-volume constant may be subtracted to define a relative grand potential; it does not affect the functional derivative. At fixed particle number one instead minimizes the physical energy , with as its Lagrange multiplier. For , the grand-potential minimum over is the vacuum . For the displayed unconstrained functional is unbounded below; the positive-density stable uniform state assumed in the following parts requires repulsion.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 343 1 iv Solution Created 2026-10-03 Updated 2026-10-06
Suppress tildes in the normalized equation and let . A Gross–Pitaevskii solitary wave stationary in these translating coordinates obeysThe boundary fixes the bulk complex argument and describes a localized disturbance with zero net vortex winding number; a vortex pair is possible. No extra plane-wave factor is needed when only the coordinates are changed. A full Galilean transformation of the field would additionally change the bulk flow and its complex argument convention.
Subtract the uniform background from the grand potential. A convenient dimensionless energy and the renormalized momentum of a condensate areThe subtraction in removes the troublesome background complex argument gradient. In particular, for the usual subsonic localized far field , , and , the energy density is and the momentum integrand is , both integrable in two dimensions. Merely writing without sufficient decay is not by itself a convergence proof. The common solitary-wave branch is subsonic: linearizing this normalization gives and speed of sound .
Integration by parts, with decaying variations and their boundary terms vanishing, givesThus the translating equation is precisely . Along a differentiable family with fixed bulk normalization, evaluate this stationarity on to obtainwhere . This energy–momentum slope of a solitary wave does not require differentiating the Lagrange multiplier inside the field variation. At a turning point the parametrized identity remains true, while need not be a single-valued function of locally. The chosen factors make , consistent with the normalized equation; changing the normalization of alone would change the claimed slope.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 1 8E Solution Created 2026-09-24 Updated 2026-11-05
Assume the holonomic constraints have linearly independent gradients, so their common level set is locally a smooth constraint manifold parametrized by . The multiplier form of the Euler-Lagrange equations isAt fixed time . The chain rule for the reduced Lagrangian givesConversely, if these reduced equations hold, the Cartesian Euler-Lagrange residual annihilates every tangent direction. Linear independence of the constraint gradients implies that it is a linear combination of those gradients, giving the required Lagrange multipliers. This proves the local equivalence, including time-dependent constraints; singular constraints would need separate analysis.
For the bead, , soThe autonomous conservation of energy gives . If , the motion has a fixed sign andThe integral is the signed arc length divided by the constant speed, and is locally invertible. The special solution is a stationary bead, for which writing time as a function of its unchanging position is not meaningful.
Past exam of the mathematics course of the University of Cambridge 2018 ib Paper 1 4B Solution Created 2026-09-24 Updated 2026-10-03
For and , the Lagrange multiplier equations areThe four constrained stationary points areOn the constraint, with . The two -axis points are global minima, while the -axis points are saddles: motion along the waist decreases , whereas motion away from it increases . There is no maximum.
If instead is optimized on , the stationary points are all six coordinate-axis points. The -axis points are maxima with value , the -axis points are minima with value , and the -axis points are saddles with value .
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 219 1 iii Solution Created 2026-10-03 Updated 2026-10-05
Unbiasedness requires . Let and minimize . The Lagrange multiplier equations for are , so normalization gives . HenceThe gradient at this point is , whose inner product with every feasible displacement satisfying is zero. The Hessian matrix is , and for every nonzero feasible . These are the first- and second-order constrained minimum conditions. Strict convexity also proves global uniqueness of this inverse-variance weighted mean; normal errors are not needed.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 306 1 i Solution Created 2026-10-03 Updated 2026-10-05
Use the Minkowski metric and units with speed of light one. The contractions are and ; and pair a vector with a covector without another metric. The Lagrange multipliers impose the two first-class constraintsThey generate worldsheet diffeomorphisms, so the phase space contains both constrained directions and gauge redundancy. Two first-class constraints remove two canonical pairs, leaving physical degrees of freedom per point.
In Monge gauge, and . Write the transverse canonical variables as and . Solving the first-class constraints givesThe negative root selects positive energy. Substitution into the phase-space action gives the Hamiltonian reductionFor a static segment, , its proper length element is , and . Thus the string tension is the rest energy per unit proper length. In particular a straight resting segment has . Monge gauge is a local choice on a string embedding map for which is a valid coordinate; it need not cover folded strings or all endpoint configurations.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 306 2 i Solution Created 2026-10-03 Updated 2026-10-05
The real canonical variables describe the center-of-mass position and total momentum of the open string. The nonzero string oscillators are complex Fourier modes with ; the Lagrange multipliers obey . The Virasoro constraints satisfy , so the multiplier term is real.
For each , the oscillator kinetic term differs from the manifestly real expressionby . Thus the written action is real up to a boundary term, which does not change its symplectic form or bulk dynamics. Adding the corresponding endpoint term makes reality exact.
The independent nonzero Poisson brackets areAll brackets between these independent center-of-mass and oscillator variables vanish. The dependent zero mode is , so, if it is used, .
The Fourier coefficients of the Virasoro constraints areTheir Poisson brackets areThey form the classical Witt algebra, with no Virasoro central extension. In particular they are first-class constraints, closing on the constraint surface, and generate the remaining worldsheet diffeomorphisms rather than independent physical excitations.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 311 1 i Solution Created 2026-10-03 Updated 2026-10-05
The action contains neither nor , so their conjugate momentum vanishes. They impose constraints rather than independent evolution equations: after the Legendre transform in mechanics, the lapse function and shift vector are Lagrange multipliers in the Hamiltonian formulation of general relativity.
Use precisely the paper's sign convention for extrinsic curvature, . At fixed ,Consequently the canonical momentum of the spatial metric isThis is a weight-one tensor density, with indices raised and lowered using . Its trace and inverse relation areThe sign of used here is opposite to the convention in extrinsic curvature of a spatial hypersurface; mixing the two conventions would reverse the momentum formula.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 339 1 b ii Solution Created 2026-10-03 Updated 2026-10-05
Associate nonnegative Lagrange multipliers with and with . The Lagrangian dual problem is obtained fromIts infimum over unrestricted is finite exactly when . Thus the dual isThe precise finiteness condition is . If , then on the feasible set. The primal is feasible and bounded below, and splitting into positive and negative parts makes the dual feasible. Linear programming duality therefore gives attained equal finite optima. Equivalently, the strictly feasible point satisfies the Slater condition, with the required finiteness hypothesis. This is strong duality in the usual finite sense.
If , there is with . Every , , is feasible and the objective tends to . The dual is then infeasible. Equality of extended values still holds if its supremum over the empty feasible set is defined as , but there are no finite optimizers. The paper does not assume full column rank of , so this qualification is necessary. The same calculation gives the support function of an inverse image of an infinity-norm ball, for finite decisions.
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 2 8B Solution Created 2026-09-24 Updated 2026-11-05
In Cartesian coordinates the Lagrangian isIntroduce a Lagrange multiplier for . The Euler-Lagrange equations becomeorDifferentiating the constraint twice givesTaking the scalar product of the vector equation with therefore yieldsSubstitution gives
For , the equations have the first integralsWriting and gives and . Hence every trajectory isThese are helices of unit angular frequency about a line parallel to the axis, including circles when and a straight line when .
Past exam of the mathematics course of the University of Cambridge 2019 ib Paper 1 4A Solution Created 2026-09-24 Updated 2026-09-29
Introduce the orthogonal coordinatesThen the constraint and objective becomeThe Lagrange multiplier equations for a stationary point areIf , then and , givingIf , then . The first two equations and the constraint implyConverting back to gives the other four points. Therefore all stationary points arewith matching signs, together withThe middle pair has , the last pair has , and the first pair has .
Past exam of the mathematics course of the University of Cambridge 2019 ib Paper 2 9H Solution Created 2026-09-24 Updated 2026-09-29
The Lagrange sufficiency theorem for maximizing subject to and states that if a feasible point and multipliers satisfy complementary slackness and globally maximizes the Lagrangian function in constrained optimizationthen globally maximizes on the feasible set.
For the equality constraint, takeThe Lagrange multiplier equations giveso positivity and the constraint implyFor this multiplier, is a strictly concave function on the positive octant and its stationary point is its unique global maximum. The sufficiency theorem therefore proves that the constrained maximum is
For , use . The same point and multiplier satisfy feasibility, stationarity, , and complementary slackness, and they again globally maximize the Lagrangian. Hence the answer is unchanged. Equivalently, any point with strict inequality can be radially scaled outward, increasing all three positive coordinates and therefore increasing .
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 334 2 a Solution Created 2026-10-03 Updated 2026-10-05
The first term is the local viscous force per unit length from resistive-force theory. With unit tangent vector , the drag tensor gives , where is velocity relative to the fluid.
The second term is the bending force of an inextensible filament. Varying its energy gives bulk force density . The final term, , is the force density from filament tension; is the Lagrange multiplier enforcing . At low Reynolds number, these forces balance without a filament acceleration term.
With mass, length, and time dimensions , the coefficients haveThus the drag coefficients have the dimensions of dynamic viscosity, the filament bending modulus has dimensions force times length squared, and tension has dimensions force.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 339 1 c Solution Created 2026-10-03 Updated 2026-10-05
Keep as the domain restriction, introduce nonnegative Lagrange multipliers for , and introduce a free multiplier for . The maximizing Lagrangian isIts supremum over is finite exactly when , and then equals . By linear programming duality, since the primal is feasible and bounded,Minimizing over for fixed gives , the positive part of a real-valued function. Thus the threshold formula for the sum of the largest components isFor a direct attainment check, order the coordinates . Any is optimal for , while any is optimal for .