Past exam of the mathematics course of the University of Cambridge 2011 ii Paper 1 29J ii Solution Created 2026-09-24 Updated 2026-09-24
Past exam of the mathematics course of the University of Cambridge 2011 ii Paper 1 35D Solution Created 2026-09-24 Updated 2026-09-24
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 1 b Solution Created 2026-10-03 Updated 2026-10-07
Use the Lagrange multiplier with the sign conventionFor every , this is a strictly convex quadratic in , with unique global minimizerThese formulas follow by setting the three partial derivatives of the optimization Lagrangian to zero; its Hessian is , which is positive-definite.
Choose to make this minimizer feasible. Its constraint value is , so the scalar equation isThe left side of the first equation is strictly decreasing on , with limits and . Thus exactly one positive multiplier exists and can be obtained by a bracketed scalar root search. The Lagrangian sufficiency theorem proves that its associated feasible point is the global optimum; strict Lagrangian convexity makes that optimum unique.
Consequently the unique solution isIts objective value is . This scalar multiplier certificate for a quadratic equality constraint does not require finding the multiplier in radicals, and does not mistake the nonconvex equality surface for a convex set.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 44 2 d Solution Created 2026-10-03 Updated 2026-10-07
The stated portfolio has initial wealth and terminal payoffs and . For CRRA utility, . The market is complete, and an interior optimum in its positive payoff domain has marginal utility proportional to the unique state-price density. ThereforeThe Lagrange multiplier is , and both state equations are satisfied. Part (b) verifies sufficiency and strict concavity gives uniqueness of the optimal payoff. This illustrates risk aversion recovered from an optimal two-state payoff.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 51 4 Solution Created 2026-10-03 Updated 2026-10-07
The ungauge-fixed Polyakov action has worldsheet diffeomorphism and Weyl transformation symmetries. They must survive quantization so that conformal gauge remains a valid gauge choice. In a curved target, the string nonlinear sigma model has a field-dependent coupling . Its worldsheet Weyl anomaly is controlled by the renormalization of this coupling, the sigma-model beta function.
Restore the Euclidean normalization . Use a covariant background field expansion of a string sigma model, with geodesic fluctuations about a slowly varying embedding. The quadratic fluctuation operator contains the target Riemann curvature tensor coupled to two background embedding derivatives. The ultraviolet coincident propagator is : the kinetic operator supplies , and the two-dimensional momentum integral supplies . Contracting the curvature vertex with this propagator gives a logarithmic metric counterterm proportional to . The resulting one-loop metric counterterm givesThe trace of the worldsheet stress tensor contains this coefficient multiplying , together with the curvature anomaly controlled by total central charge. Thus, with zero antisymmetric background, constant dilaton, and the critical matter/ghost system,The central-charge condition also requires if there is no extra internal conformal theory. This is a leading-order equation: higher-curvature terms enter the beta function at higher orders in , so a Ricci-flat metric alone is not a general all-orders quantum consistency criterion.
To derive the local T-duality, work where the spacelike Killing vector has nonzero norm . Use dimensionless coordinates and units for the duality formulas. The isometry makes the action depend on only through its derivatives. Replace those derivatives by an independent worldsheet one-form , and enforce its flatness with a Lagrange multiplier . With and , the relevant first-order worldsheet duality action isVarying sets . Locally , recovering the original theory. For the other elimination, integrate the multiplier term by parts. Varying gives , orSubstituting into the entire first-order worldsheet duality action, including the multiplier term, givesThe multiplier contribution is necessary for the sign of the dual kinetic term. This is the first-order action for Abelian worldsheet duality, with Buscher rulesThe coordinate map is , . The original equation is precisely the integrability condition for ; conversely the original identity becomes the dual equation. Thus this transformation exchanges an equation of motion with the Bianchi identity for an Abelian p-form. It reverses one chiral derivative and preserves the other.
For full closed-string equivalence, the local derivation must include the global data. For a free compact circle isometry, the period of and the allowed gauge-field holonomies are chosen so that the Polyakov path integral exchanges momentum and winding modes. A circle of radius becomes a circle of radius when dimensions are restored. A spacelike Killing field alone does not fix these periods or ensure a free global circle action; the global qualifications of Abelian T-duality are additional to the local field transformation.
At the quantum level integrating out also gives a regulated functional determinant. The Buscher dilaton shift isin the stated units and conventional Euclidean dilaton normalization. It generates the dilaton curvature coupling even though the original dilaton vanished. The dilaton curvature coupling is defined before fixing conformal gauge; its metric variation improves the worldsheet stress tensor even when the reference worldsheet is flat. As a normalization check, for this block-diagonal background. The local dual metric by itself is therefore only part of the equivalent quantum background.
With a nonconstant dilaton and no antisymmetric field, the leading metric-dilaton Weyl condition istogether with the scalar dilaton anomaly condition. It does not demand separately. The new Ricci tensor can be nonzero while the Hessian of the shifted dilaton compensates it.
For a direct example, take flat polar coordinates away from the origin, with and flat spectator directions. The polar-coordinate T-dual background isHereBoth metric equations vanish. In critical dimension the scalar equation also holds: . The example is local on ; the circle degenerates at the excluded origin.
Nonzero dual Ricci curvature is consistent because quantum T-duality transforms the dilaton as well as the metric. The displayed curvature equations and classical Buscher rules are interpreted at their stated leading derivative order; higher-order renormalized descriptions require the corresponding corrections and field-redefinition conventions. A constant is a special case in which the dual metric may also remain Ricci-flat.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 38 1 a Solution Created 2026-10-03 Updated 2026-10-07
Let . The feasible probability simplex is a nonempty compact convex set, so the extreme value theorem guarantees a minimizer. Its Hessian matrix is diagonal with positive entries , making a strictly convex function. Hence the minimizer is unique.
Use the Lagrange multipliers for the sum constraint and for . The Lagrangian isThe KKT conditions areA strictly positive feasible allocation exists, so the Slater condition holds. These conditions are necessary and sufficient for this convex optimization. At least one coordinate is positive, giving . Put . For a positive coordinate, complementary slackness gives . At a zero coordinate, stationarity gives , or . ThusHere . This logarithmic water filling raises the smaller baseline values to a common level. The scalar left side is a continuous function and strictly increasing above , starts at zero, and tends to infinity, so exactly one solves it. One can find it by interval bisection, or sort the baseline values increasingly and find an index for whichusing . Equality at the next baseline simply gives a zero allocation. Sorting and a running sum implement the water-filling algorithm in time.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 46 1 Solution Created 2026-10-03 Updated 2026-10-06
Use the mostly-plus Minkowski metric, and write for equality on the constraint surface. Assume that the mechanical constraints are locally independent. They are first-class constraints whenThus their Poisson brackets vanish on the constraint surface, and their Hamiltonian flows preserve that surface. The structure functions of a constraint algebra may depend on the phase space point. The finite real span of the constraints is a Lie algebra if it closes with constant structure coefficients, in a suitable choice of generators. The Jacobi identity then gives the usual conditions on the structure constants of a Lie algebra. With general structure functions the finite real span need not close, even though the Poisson bracket of all smooth functions is itself a Lie bracket.
To see the gauge invariance directly, let generate a canonical gauge transformation:The variation of the phase-space action integrand isThe second term cancels without using the equations of motion. Taking to vanish at the temporal boundaries leaves the action invariant. Arbitrary functions therefore relate different descriptions of the same physical motion. This reasoning also works with structure functions; constant structure coefficients are only needed for the finite-dimensional Lie algebra claim.
For a closed string, choose and periodic fields. A convenient Nambu-Goto phase-space action isHere and are Lagrange multipliers. The Nambu–Goto phase-space constraints are and , with canonical Poisson bracketsLet . Differentiating the periodic Dirac delta function givesThe opposite signs in and cancel these terms, so . Replace the original constraints by the equivalent chiral densitiesTheir mixed Poisson brackets vanish. Choose opposite Fourier orientations for the two sectors:The chiral constraint algebra of a closed string isEach is the Witt algebra: the vector fields on a circle satisfy . Fourier expansion identifies each real algebra, with , with the Lie algebra of vector fields on the circle. The two commuting copies give , not a quantum central extension.
For an open string, allowed boundary conditions must remove the endpoint term in the variation of the action, consistently with the allowed endpoint variations. The spatial boundary term isIt expresses the open-string endpoint momentum flux. In the temporal gauge for a string , take a boundary-adapted parametrization with at the ends. Fixing gives , a Dirichlet boundary condition. At the other end allow arbitrary spatial variations; for nonzero these require , a Neumann boundary condition. Also in this temporal gauge for a string, so . The constraint at this free-end string boundary condition reduces to . Hamilton's equation consequently gives there. Since , the free endpoint has spatial speed one. This is the null motion of a free string endpoint.
A straight rotating string with one fixed endpoint supplies the required solution in at least two spatial dimensions. Set , , andTake . The Hamilton's equations become , which holds because both second derivatives give . The Nambu–Goto phase-space constraints are satisfied byThe endpoint at stays at the origin, while at and the endpoint moves around a circle of radius with angular speed . At each time the whole string lies on a straight radial segment. Its spatial proper length isThe velocity is everywhere perpendicular to the segment, so this also equals the sum of local rest-frame lengths. The induced worldsheet metric becomes degenerate at the null free endpoint, as expected for the limiting free-end solution.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 46 2 Solution Created 2026-10-03 Updated 2026-10-06
Use , transverse coordinates , , and the Minkowski metricThe relativistic particle phase-space action becomesIn the light-cone gauge , solve the mass-shell condition for , assuming . The reduced phase-space action is , withThe last equality selects the future-directed momentum sector and makes positivity transparent. With and , the Schrodinger equation isThe inverse acts only on Fourier modes with nonzero . Multiplication by gives . ThereforeThe light-cone Hamiltonian thus gives the same Klein-Gordon equation as covariant quantization.
For the massive two-form field, take . Apply to its field equation. Antisymmetry of makes , soExpanding , the other divergence terms vanish by this condition, leaving . The light-cone decomposition of a massive two-form makes its dependent components explicit. The divergence equation isTaking and , respectively, givesThe equation follows from these expressions: the two terms containing cancel and . Consequently and are independent, each satisfying the Klein-Gordon equation with mass . The number of independent particle polarizations isThis is the exterior square of the vector representation of the massive little group . In the analogous Proca equation, determines from and , leaving components. A massive field has no gauge freedom that would justify setting these longitudinal components to zero. If , instead use the two-form gauge field symmetry : the light-cone gauge for a two-form removes , leaving transverse particle polarizations. The massive and massless counts are different.
In the closed-string mode expansion, are center-of-mass canonical variables, while are independent left- and right-moving transverse string oscillators. Their complex conjugates are . The two zero-mode Lagrange multipliers impose the remaining mass-shell condition and closed-string level matching. The string level operators areTheir quantum definitions use normal ordering. The symplectic terms in the phase-space action givewith all brackets between distinct sectors zero. The nonzero-index string oscillators obey and similarly for the right-moving sector. Define the momentum-labelled oscillator vacuum byFor , has . HenceStarting with , a finite product with creation operators of mode has eigenvalue . The Fock space is generated by these products; both level operators have nonnegative integer eigenvalues. This establishes the integer string oscillator level property. Subtracting their physical zero-mode constraints enforces .
There is a distinction between the displayed classical zero modes and their quantum constraints. With the normal-ordering constant of a string , these areAt the massless first closed-string level, the states areTheir transverse polarization tensor splits into a symmetric trace-free part, an antisymmetric part, and its trace. These are the graviton, Kalb–Ramond field, and dilaton, with respective particle polarization counts , , and one. They have the transverse little group representations of massless particles. In a Lorentz-consistent bosonic string theory, the first chiral level is a massless vector, not a massive vector with one missing physical polarization; the closed-string products are therefore massless. This fixes . Equivalently, regularized transverse zero-point energy gives , and Lorentz consistency fixes the critical dimension of the bosonic string .
It follows that the bosonic string mass spectrum isThe ground state has and is a tachyon; level one is massless; for the mass is . The masslessness claim uses the consistent quantum theory, rather than an unshifted reading of the classical .
A massive two-form at closed-string level two is present. To see it without confusing it with the level-one massless Kalb–Ramond field, the level-two states in one chiral sector areThey have components and assemble into the symmetric traceless square of the massive little group vector space . The full closed-string level is . For two symmetric trace-free matrices , the mapis an equivariant map onto antisymmetric matrices. To verify surjectivity, take diagonal with distinct entries in positions and with only its symmetric entry nonzero. Their commutator gives the antisymmetric basis element. Finite-dimensional representations of the compact little group are completely reducible, so this quotient representation is also a subrepresentation. It has exactly particle polarizations and is described by the massive field equation with . At this gives 300 particle polarizations, consisting in light-cone coordinates of 24 components and 276 components .
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 46 3 Solution Created 2026-10-03 Updated 2026-10-06
For the relativistic particle phase-space action, the first-class constraint generatesIndeed the integrand varies by . The canonical gauge transformation is an invariance when the gauge parameter vanishes at fixed temporal endpoints, or when all fields and the parameter are periodic. The boundary restriction matters for the proper-time modulus.
Normalize the worldline interval to . Thenis invariant because . Every allowed in its orbit can be written : set . Thus remains a gauge-invariant integration variable, not another removable nonconstant mode. For a worldline circle the constant gauge parameter is a residual zero mode. Without the endpoint restriction, the assertion that is invariant would not hold.
The worldline gauge-orbit determinant is the Jacobian from gauge-orbit coordinates to the nonconstant part of is the Faddeev-Popov determinant of . Equivalently, the gauge-fixing identity has the formThe determinant is taken between the appropriate boundary-condition spaces, with the modulus removed; on a circle the prime also removes the constant parameter. Gauge fixing therefore leaves a factor and a modulus measure, after division by any residual gauge volume. Even though this determinant is field independent in the present Abelian example, it is the required change-of-variables Jacobian. A Grassmann integral over the Faddeev-Popov ghosts exponentiates it:The overall determinant phase depends on the integration convention and can be absorbed into normalization. Zero modes and the same endpoint restrictions must be treated separately rather than included in an invertible determinant.
For the free-ended open string, take . A canonical cosine expansion at a fixed time isIt implements the Neumann boundary conditions and has . With , its Nambu-Goto phase-space action, up to a total time derivative, isReality requires . Numerical factors can be absorbed into these Lagrange multipliers. In this covariant quantization of the bosonic string the oscillators retain all spacetime components, in contrast to the transverse oscillators in the preceding solution. The canonical commutation relations areThe oscillator vacuum is annihilated by for . Its momentum label will sometimes be suppressed.
Define the matter Virasoro algebra generators using normal ordering:No additive intercept is included in this definition of . For the indices of the two factors in each term add to ; they cannot both be negative. After normal ordering there is a positive-mode annihilation operator on the right, possibly accompanied by the zero mode. Hence for every . In , commuting positive modes past negative modes formally adds . This divergent constant needs a prescription, and a finite shift is an ordering ambiguity. Our convention instead puts the physical string intercept into the constraint .
With this convention the matter Virasoro algebra isA different additive constant in would change the linear-in- central term, so stating the convention is essential.
For the worldsheet ghost fields, useand choose a ghost oscillator vacuum withThen since . This choice specifies the ghost zero-mode doublet; it is not a claim that both zero modes annihilate one state. With the printed ghost Virasoro zero-mode convention, and for . The latter follows by putting positive ghost modes on the right; a possible contraction requires and is absent here.
Apply the supplied BRST charge to the matter state times this ghost oscillator vacuum. Terms with a rightmost , , vanish, as do the positive-mode ghost generators. ThusThese one-ghost states are independent, as can also be seen by applying . Therefore the BRST physical-state constraints of an open string areFor the matter oscillator vacuum, , so and : the physical ground state is a tachyon. The momentum must satisfy this equation; the zero-momentum oscillator vacuum by itself would not be BRST-closed.
Matter and ghost generators commute with one another. Add their two algebras and write . The given ghost constant must be retained:Define the shifted generators . ThenBRST nilpotence requires cancellation of the anomalous central term in this shifted constraint algebra, together with the intercept one already present in the charge. At the remaining anomalous coefficient is , so . At this value the shifted total generators obey the Witt algebra. The unshifted still have the displayed linear zero-mode shift; it must not be silently discarded.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 1 a Solution Created 2026-10-03 Updated 2026-10-06
For a maximization problem with and , use the optimization LagrangianThe Lagrangian sufficiency theorem says: if is feasible, globally maximizes over its original domain, and complementary slackness holds, , then globally maximizes over the feasible set. Equality Lagrange multipliers have no sign restriction. For every feasible ,which proves the theorem.
For a minimization problem, reverse the signs in the optimization Lagrangian: take , with . If a feasible globally minimizes this optimization Lagrangian and satisfies complementary slackness, thenThe hypothesis is a global extremum of the Lagrangian. Merely solving its stationarity equations is insufficient; no convexity assumption is needed when the global extremum itself has been proved.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 1 c Solution Created 2026-10-03 Updated 2026-10-06
For minimization, the optimization Lagrangian isIts coefficient of is , so its infimum over unrestricted is for every allowable Lagrange multiplier. There is no finite global minimizer of the optimization Lagrangian to which the Lagrangian sufficiency theorem could apply.
The primal minimization problem is also unbounded: set , and . These points are feasible, and . Hence
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 1 d Solution Created 2026-10-03 Updated 2026-10-06
For any feasible , increasing lowers the objective, so the additional upper bound makes . Feasibility then requires . The lowest feasible value of on the circle occurs at the lower intersection with . Solving gives the candidateA global certificate avoids relying on the circle sketch. Introduce Lagrange multipliers for , and :ChooseThe coefficient of vanishes, and , . Therefore completing the square yieldsThe candidate minimizes globally and satisfies both active inequality constraints, so complementary slackness and the Lagrangian sufficiency theorem give
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 49 1 Solution Created 2026-10-03 Updated 2026-10-06
Use Minkowski spacetime signature and a closed spatial parameter of period . Choose the future-directed branch with positive lapse .
Canonical dynamics and gauge freedom. Variation of momentum and embedding in the Nambu-Goto phase-space action givesThe Lagrange multipliers impose the Nambu–Goto phase-space constraints and . These two first-class constraints reflect freedom to relabel time and space on the same string worldsheet. The canonical Hamiltonian is a linear combination of constraints, with arbitrary multiplier functions. These functions specify a coordinate description rather than additional propagating fields. No explicit gauge transformation or Poisson-bracket calculation is required.
Eliminating auxiliary variables. Let . Eliminating momentum using leavesOn a patch with spacelike spatial tangent, variation of gives , hence . For the induced worldsheet metric , this gives . Variation of then gives on the positive branch. Substitution yieldsThis is minus string tension times Lorentzian worldsheet area. Vary the area using and integrate by parts. The Nambu–Goto equations of motion areThe auxiliary-variable elimination and this metric form apply on nondegenerate timelike patches.
Circular motion, length and energy. For the circular embedding, direct differentiation givesAway from collapse, , so the equations become . The time and out-of-plane coordinates satisfy them immediately. For , both and are . The relations and verify the Virasoro constraints. Equivalently, , , solve the phase-space equations and constraints at all times.
The ring stays in a fixed plane, with radius . It contracts to a point and re-expands. Each labeled point moves radially with speed in target time . The geometric ring repeats after target-time interval , although the labels have then shifted by half a circumference. It is not rigidly rotating. Velocity is perpendicular to the tangent, so simultaneous spatial arclength is also the local proper length along the string. Its length and conserved energy areAway from collapse, the same energy follows from . Increasing kinetic energy compensates the shrinking length. At collapse the induced metric degenerates; the area-form equation alone is undefined there. The regular phase-space solution supplies the continuation and the limiting constant energy. This is a pulsating circular string.
Endpoint variation. For an open string, integration by parts produces the boundary termIts coefficient is the open-string endpoint momentum flux. Evaluate this ungauge-fixed variation in a boundary-adapted temporal gauge for a string . Then and the time equation gives . The free variation of time forces , hence at each end. Since is nonzero, the remaining spatial term requiresFree variation in every spatial direction gives , and together with gives the free-end string boundary condition . The general starting condition is the flux condition; the shift term should not be silently discarded before choosing the gauge.
Target-space charges. The Noether charges for translations and Lorentz transformations are the target-space Noether charges of a stringWriting , the canonical equations implyFor the second identity, antisymmetry cancels the terms. Integration by parts then cancels the terms and the symmetric terms. For free ends individually, so both charges are constant. In conformal gauge, the same result follows from and . Target-space energy is .
Other possibilities fix selected spatial directions by Dirichlet boundary conditions, while leaving Neumann boundary conditions in the permitted tangent directions. These mixed conditions describe endpoints on a D-brane; the two ends can lie on different branes. Time stays free under the given assumption. Fixed supports may absorb momentum in their Dirichlet directions and break corresponding translations or Lorentz symmetries. More general force-law conditions require an additional boundary interaction.
Past exam of the mathematics course of the University of Cambridge 2016 ib Paper 4 16C a Solution Created 2026-09-24 Updated 2026-10-06
Take and a positive prescribed distance ; if , the zero-speed journey has zero cost. Minimize subject to and the isoperimetric constraint . Introduce a constant Lagrange multiplier and the integrand . For a variation with , integration by parts givesThe interior Euler-Lagrange equation isWhen terminal speed is free, the same calculation also imposes the natural boundary conditions for a free endpoint:One cannot drop this boundary term when interpreting an extremal as a genuine minimum. If , the interior condition makes constant; with a continuous zero initial speed and it cannot be attained. In that case Cauchy-Schwarz inequality gives the infimum , approached by speeds nearly constant except in a short initial layer. For , the derivative cost controls such layers and the natural terminal condition matters in parts (b) and (c).
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.