Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Use the PDF's entry , rather than the TeX aid's . To check nondegeneracy of a bimatrix game, every opponent strategy of support size must have at most pure best responses. Against each pure column, the unique best rows are respectively . Against each pure row, the unique best columns are respectively .
The only mixture making all three rows indifferent solves and , giving , which has support size three. Thus no two-column-support mixture has three best rows. For the other player, column strictly dominates column , because their payoff difference is , so three best columns are impossible. These observations cover all support sizes, proving the game is nondegenerate.
For the Lemke-Howson algorithm, use unnormalized strategy vectors in the polytopesA row label occurs at in or at in . A column label occurs at in or at in . The origin pair has all six labels.
Drop row label by increasing . Column is the first binding payoff constraint, at , so label becomes duplicated. Drop in by increasing ; row binds first, at , duplicating label . Drop in by increasing while keeping and the column- constraint binding. Since that constraint does not involve , stays . Column binds at , duplicating label .
Now drop in by increasing . Keep and row binding, so . Row reaches payoff at , earlier than row , which would bind at . The missing label returns, terminating the path. The successive vertex-label pairs areThe final pair is completely labelled and nonzero. Normalize each vector by its own sum to obtainThe row payoffs against are and the column payoffs against are . Both supported actions are best responses, so this is a Nash equilibrium, with payoffs .
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The intended deletion theorem starts from the full action set . Under that interpretation, each player's surviving action set remains nonempty: with only one action, no mixed strategy can weakly improve it and improve it strictly somewhere. Let the final reduced bimatrix game have a Nash equilibrium, which exists by Nash's theorem.
Restore the deleted actions in reverse order. Consider a row action when it is restored. At its deletion it had a weakly dominating mixed strategy in the then-current game. If , remove that self-weight and renormalize: the strict-improvement clause guarantees , and dividing the payoff comparison by gives a weakly dominating strategy supported on the other then-current row actions. Those other actions have already been restored in the reverse process. The chosen Nash equilibrium's column support lies in the final surviving set, so the dominance comparison applies to its column strategy .
If the row player's Nash equilibrium payoff in the restored game so far is , every currently available pure row payoff against is at most . The dominating mixture therefore has payoff at most , and the restored action has payoff no greater than that mixture. It cannot improve the payoff. Column deviations are unchanged by adding a row action, since the actual Nash equilibrium strategy remains fixed. The analogous argument works when restoring a column action. Induction restores the full game while preserving the final reduced Nash equilibrium and its support.
Thus iterated deletion of weakly dominated actions preserves at least one Nash equilibrium supported entirely on surviving actions. It need not preserve every Nash equilibrium or give an order-independent reduced game.
The literal printed use of an arbitrary initial needs qualification. For example, take row payoffs and column payoffs . On the restricted set containing both rows but only column , row is strictly dominated by row . Yet in the full game column is strictly dominant and its unique Nash equilibrium uses row . Deleting row based only on that restricted leaves no full-game Nash equilibrium with the requested support. The proven equilibrium preservation under iterated weak dominance therefore requires initial , or concludes only about the initially restricted game.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 3 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Let be an optimal metric tour. Removing any one of its edges gives a spanning tree, so the minimum spanning tree satisfies . The handshaking lemma shows that its odd-degree set has even size.
Follow and retain only vertices of , shortcutting between consecutive retained vertices. This produces a cyclic order on of total cost at most . If is nonempty, the alternating edges of that cyclic order form two perfect matchings; their costs sum to the cycle cost. One has cost at most , so a minimum-weight perfect matching hasFor , count the same undirected edge twice in the cyclic order; each alternating matching consists of one copy. For , use the empty matching.
The multigraph with edges is connected because it contains . Each odd-degree vertex receives exactly one matching edge, and the other degrees are unchanged, so every degree is even. It therefore has an Euler circuit. Constructively, follow unused edges until returning to the starting vertex; parity prevents getting stuck elsewhere. If unused edges remain, connectivity supplies a vertex of the current circuit incident with one, and its additional closed trail can be spliced into the circuit. Repetition gives a circuit using every edge exactly once, including parallel copies.
Shortcut repeated vertices of this Euler circuit to obtain a metric tour. Its cost is at mostComputing a minimum spanning tree, a minimum-weight perfect matching, an Euler circuit and the shortcut tour is polynomial-time; weighted perfect matching is a standard polynomial-time graph optimization problem. Thus the Christofides algorithm is a -approximation algorithm for symmetric metric tours.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Reduce the Hamiltonian cycle decision problem to the metric travelling salesman problem. Given a simple graph on vertices, form the complete graph with distance on original edges and distance on nonedges. These symmetric distances satisfy the triangle inequality, since a direct distance is at most and any two positive edge distances sum to at least .
A tour has edges, each of cost at least . It has cost at most exactly when every edge is an original graph edge, that is, exactly when the original graph has a Hamiltonian cycle. The construction and threshold are polynomial in the input size. Thus the metric travelling salesman problem is NP-hard; its rational-cost threshold version is also in NP because a tour is a polynomial-size certificate.
Allowing repeated vertex visits does not reduce the optimum for a complete metric instance. Given a closed walk visiting every vertex, keep the vertices in order of first appearance and shortcut the portions between them, including the final return. The triangle inequality makes the resulting Hamiltonian tour no more expensive. Conversely a Hamiltonian tour is an allowed closed walk. Hence the two optimal costs are equal, and the repeated-visit metric version remains NP-hard. If travel is described on a sparse graph, taking its shortest-path metric gives the corresponding closed-walk formulation rather than an easier exact problem.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 3 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A decision problem belongs to NP if every yes-instance has a polynomial-length certificate verifiable by a deterministic polynomial-time algorithm. It 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.
A polynomial-time algorithm for any NP-complete problem would therefore give one for every problem in NP, implying . Conversely, if , all NP-complete decision problems have polynomial-time algorithms. NP-completeness does not unconditionally prove that polynomial-time solution is impossible. Optimization problems such as minimum tour cost are described as NP-hard, while their threshold decision versions can be NP-complete.
For a minimization problem with nonnegative costs, an approximation algorithm of ratio is a polynomial-time algorithm returning a feasible solution of cost at most times the optimum on every instance. For maximization, one often uses with value at least ; an equivalent convention uses ratios at most one. The metric-tour question uses the minimization convention.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
If are integral, the derived surplus and slacksare also nonnegative integers. Therefore an all-integer Gomory fractional cut can be taken from the final tableau's slack rowFor a nonnegative integer dictionary row , the quantity is an integer at most , so it is at most . Subtracting from the row proves the cut . Applying it here givesBut the original row and give . Nonnegativity then givesThis contradicts the valid cut. Therefore the integer program is infeasible, certified by one Gomory fractional cut. It is essential to use the PDF's constraint: the altered TeX problem would have feasible integer points.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Use the PDF's first constraint, ; the TeX aid substitutes a different inequality. Introduce a surplus , slacks , and one artificial variable , all nonnegative. The initial simplex dictionary isThe initial basis is , with values . In two-phase simplex, Phase I maximizes . We use the Bland pivoting rule: the smallest-index nonbasic variable with positive reduced cost enters, and among minimum-ratio ties the smallest-index basic variable leaves.
First enters. The ratios for are , so leaves in a degenerate pivot. The resulting dictionary isNext enters. It reduces and with ratios and , while increases. Thus leaves. The Phase I maximum is , with a feasible original basis; remove and obtainIn Phase II the original objective is . Bland's rule makes enter, and leaves at ratio . This givesFinally enters. The decreasing basic variables have ratios and , so leaves. The final tableau, with the basic columns suppressed, isEach row means its row variable plus the displayed nonbasic terms equals the right side. Since , no nonnegative choice of nonbasic variables improves the objective. ThusThe slacks are , .
A different entering rule is faster here. Selecting the largest eligible index in the initial Phase I objective makes enter and leave. The dictionary then has and . Entering makes leave at , directly reaching the final original basis . Hence two pivots suffice instead of Bland's four, and Phase II needs no further pivot. This comparison concerns this instance, not a general superiority of that entering rule.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 1 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Introduce a free scalar . The epigraph reformulation is the linear programFor each fixed , the smallest feasible equals the maximum of the affine expressions, so the reformulation preserves the optimum.
Associate nonnegative multipliers with these inequalities. Its optimization Lagrangian isBecause and are unrestricted, the infimum is finite precisely when the coefficients of both vanish. Therefore the Lagrangian dual problem isA feasible dual vector is a convex combination of the slopes whose mean slope is zero. It gives a constant lower bound on the maximum of the affine functions. The primal is always feasible, by taking and sufficiently large . If it has a finite optimum, linear programming duality gives attainment and equality with this dual; otherwise the dual is infeasible and the primal is unbounded below.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 42 1 b Solution by
Codex 0 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 42 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For a minimization problem on a domain , write the equality constraints as and the inequality constraints as . Define the optimization LagrangianThe Lagrangian sufficiency theorem states that a feasible is globally optimal if it globally minimizes on for some multipliers with and satisfies complementary slackness, for every . Equality multipliers have unrestricted signs.
For any feasible , the multiplier sign gives . Feasibility and complementary slackness at give . HenceThis proves sufficiency. Global Lagrangian minimization, rather than stationarity alone, is the certificate. No convexity or constraint qualification is needed for this implication; convexity is one way to verify the required global minimum.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 5 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A frailty model uses an unobserved nonnegative random hazard multiplier to represent variation in individual risk. In a proportional frailty model, conditional on the cumulative hazard function is , giving survivor . Averaging over the frailty random variable by the law of total probability yieldsthe Laplace transform of the frailty distribution evaluated at the baseline integrated hazard. This also applies to atoms by integration against the probability measure; the printed Dirac expression is not an ordinary continuous density.
In the given two-atom case, the Dirac delta function notation assigns probabilities and to and . These have mean one, fixing the frailty scale relative to the baseline hazard. With , the two conditional integrated hazards are and . ThereforeThe frailty distribution among survivors shifts toward the smaller multiplier over time, reproducing the declining population hazard and limit one without changing either individual's constant conditional hazard.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 5 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A survivor function is . For a nonnegative event time it is nonincreasing and right-continuous, with values between zero and one; a proper finite event time has as . Here , , , and for . Extending it by one for supplies a valid continuous survivor function.
The density is , so the hazard function isIn particular and . The survivor is a mixture of rate-one and rate-two exponential distributions with weights and . Among long-term survivors the rate-one component dominates, explaining the limiting hazard. More generally the hazard derivative for a mixture of exponential distributions is minus the variance of the component rate among survivors; the decreasing hazard is selection, not an individual component's changing hazard.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 4 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Only sets 4, 5, 7 and 8 have an earlier failure with both members at risk. Sets 4 and 8 have B fail first and favor A, giving informative pairs. Sets 5 and 7 have A fail first and favor B, giving . Both-censored pairs contribute zero; in sets 3 and 6 the earlier observation is censoring, so the later failure occurs with no remaining comparator and also contributes zero.
There are thus 36 informative independent strata. The stratified log-rank statistic, its null variance, and its standardized value areEquivalently the squared statistic is nine. The normal approximation gives a two-sided p-value using the stated bound. The exact conditional sign test instead gives ; the slight difference is discreteness rather than a different direction of effect. There is strong evidence favoring Method B, which is associated with the later failure in three quarters of the informative pairs, under the test assumptions.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 4 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A nonzero contribution occurs when a failure, rather than a censoring, is the earlier observation while both members remain at risk. By the paired log-rank reduction to a sign test, the two possible contributions are for an earlier A failure and for an earlier B failure. Under the exchangeable null and the usual independent censoring assumptions they are equally likely, conditional on being informative. HenceOnce the first member leaves the risk set, the second member's later observation adds no group-comparison information within this stratum.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Use the A-group observed-minus-expected convention for the stratified log-rank statistic. At the first failure both teeth are at risk, so A has one observed event and null expectation , giving . At the later B failure, A is no longer at risk; the A contribution is zero. This patient's contribution is , favoring B. The opposite group convention reverses the sign but gives the same test.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
No: with one pair per stratum, the statistic uses failure order but discards the size of the time difference. The paired log-rank reduction to a sign test assigns the same contribution when A fails just before B as when A fails much earlier. This deliberately avoids a model for the failure-time distances, but it does not extract every kind of evidence in the recorded times. An accelerated failure time model, for example, could use log-time differences in uncensored pairs under additional distributional assumptions.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 2 e Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Use a subgroup analysis in meta-analysis comparing studies before and after 2000, with a direct test of the between-subgroup effect difference. Alternatively use meta-regression with year, or the before/after indicator, as a study-level predictor. Compare the effect estimates themselves: significant and nonsignificant results need not differ significantly.
Two reasons for caution are that the proposed contrast was selected after examining the results, creating a multiple testing issue, and that only six studies supply an observational comparison of study characteristics. Year can be confounded with dose, participant populations, follow-up or design, so an apparent year effect need not be caused by time itself. The small number of studies also makes these comparisons imprecise. These would be exploratory findings rather than confirmation of an effect-modification hypothesis.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 2 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The additional estimate points in the same direction as the pooled effect: its odds ratio is about , compared with the original pooled value about . Its standard error is relatively large, and the approximate two-standard-error interval for its log odds ratio is , or about on the odds-ratio scale. This interval includes both no effect and the existing pooled effect. Thus it supplies compatible but imprecise evidence and would tend to pull the pooled estimate somewhat toward one while adding information. A change in the main conclusion is unlikely.
For scale, a conventional inverse-variance common-effect fit to the six rounded tabulated estimates can be updated by , with new weight . This gives the new study roughly eleven percent of the combined weight, a modest effect on the estimate. An exact update of the supplied Mantel–Haenszel pooled odds ratio needs the new two-by-two table, which the reported log ratio and standard error do not uniquely specify. The qualitative compatibility conclusion does not depend on pretending that the supplied plot used inverse-variance weights.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 2 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The I-squared statistic of is a small estimate of excess variation on the heterogeneity scale. It does not mean that of studies are different, nor that this percentage of patients responds differently. The Cochran's Q statistic compares the observed variation with that expected from the studies' sampling errors; its approximate null distribution has five degrees of freedom here. A heterogeneity-test p-value of provides no rejection of the common-effect hypothesis.
The individual confidence intervals in the forest plot overlap substantially, although some point estimates are larger than others. Taken together, there is little evidence of between-study heterogeneity in these six studies. Neither the nonsignificant test nor the small I-squared statistic proves equal effects: with only six studies, detecting moderate heterogeneity can be difficult. A study being individually significant while another is not is also not itself a test of their difference.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 41 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A fixed-effect meta-analysis models the studies as estimating a common underlying treatment effect. In a generic inverse-variance version, independent log odds ratios have approximate distributions and are pooled with weights . The supplied forest plot instead has the Mantel–Haenszel pooled odds ratio weights: for event/nonevent cells and total , the normalized weights are proportional to . They reproduce the printed percentages and yield a pooled odds ratio about . This is still a common-effect analysis; the two weighting methods should not be silently identified.
A random-effects meta-analysis allows different true effects: with . The between-study heterogeneity variance adds to sampling variance, giving marginal variance . Its pooled estimate targets the mean of the study-effect distribution rather than one identical effect. Uncertainty about heterogeneity must also be considered.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact






