Learn the idea. Try it yourself.
Read the explanation or try 6 questions with hints. Free, untimed and no sign-in needed.
All lessons · Vietnam’s Olympiad route
Your goal: test a tempting “best next choice”, find a counterexample when it fails, and prove a safe choice by replacing part of an optimal solution.
Study plan: two sessions of about 60–75 minutes. First work through the diagnostic, four examples and their nearby tasks. Then write solutions to the nine graded problems. The short adaptive session checks particular decisions; it does not replace written proofs.
Preparation context: original combinatorial reasoning towards Vietnam’s national high-school mathematics competition, with accessible bridges before the proof problems. The released 2025–26 national paper includes an optimisation problem that tests a greedy rule. This lesson develops general proof skills through different settings; it is not an official paper, a reproduction of that problem or an exact national-difficulty simulation. The national competition and the later Olympic team-selection examination are separate stages. Confirm current entry and paper instructions through your school and the country guide.
Prerequisites: adding cumulative totals, comparing fractions, inequalities, and the difference between “some” and “every”. Use exact arithmetic, inequality rules and proof methods when needed. No programming or named optimisation theorem is assumed. Exchange arguments are developed below.
Three starting checks
Try each question before opening its explanation. If the model is unclear, repair that prerequisite before using a rule.
Diagnostic 1: what are we trying to minimise?
Three jobs take 2, 5 and 3 minutes. They run one at a time, starting at time 0, in that order. Find their three completion times and their sum.
Explanation and prerequisite route
The first job finishes at time 2. The second finishes at 2 + 5 = 7, and the third at 2 + 5 + 3 = 10. The sum of completion times is 2 + 7 + 10 = 19. It is not just the total working time, 10: time spent on an early job delays several completions. If cumulative sums are unfamiliar, revisit sequences and sums.
Diagnostic 2: what disproves an “always” claim?
A rule succeeds on 20 examples. Does this prove that it always gives the best answer? What would disprove the claim?
Explanation and prerequisite route
Twenty successes do not by themselves prove the claim, unless those 20 examples exhaust all allowed inputs. When other inputs are possible, they remain unchecked. One allowed input where the rule gives a worse result than another feasible choice disproves the claim. We must check that both choices obey the rules and compare the same objective. A counterexample disproves a universal claim; it does not prove that the rule fails on every input. Review examples, counterexamples and proof if needed.
Diagnostic 3: do endpoints matter?
An activity starts at time 1 and finishes at time 4. A second starts at time 4 and finishes at time 6. The rule allows the second to start exactly when the first finishes. May both be selected?
Explanation and prerequisite route
Yes. The compatibility condition is “next start is at least the previous finish”. Equality is allowed. In this lesson an activity written [1,4) occupies times from 1 up to, but not including, 4. Later, our point-covering problems use closed intervals [1,4], which include both endpoints. Keep those two conventions separate.
A good-looking next move needs a reason
greedy rule builds a solution one choice at a time, taking the option that looks best by a stated local test. “Shortest next job” and “activity that finishes first” are different rules. Before testing either one, write down exactly what choices are allowed and what final quantity you want to minimise or maximise.
A solution is feasible if it obeys every constraint. It is optimal if no feasible solution has a better objective value. There may be several optimal solutions. A greedy proof need only show that the rule produces one of them.
First try to break the proposed rule with a small example. Include an alternative feasible choice and compare their objective values. Success on a few examples suggests a conjecture but does not prove it.
The exchange argument: start from an unknown optimum
Suppose you want to prove that a first choice G is safe. Imagine an optimal solution, even though you do not know how to find it. If it already contains G in the required place, there is nothing to change. Otherwise try to replace one or two of its choices by G. Check two things separately: the changed solution is still feasible, and its objective is no worse.
If the exchange succeeds, there is an optimal solution agreeing with the greedy first choice. This does not mean every optimal solution makes that choice. Next explain why the remaining task has the same structure, so the same argument can be repeated. A first move alone does not prove the entire algorithm.
- State the objective and constraints.
- Choose an optimal solution and identify its first disagreement with the greedy rule.
- Describe a precise replacement.
- Check feasibility and compare the objective.
- Reduce to a smaller problem, or show that every unsorted order admits an improving exchange.
Why is an optimum available? A finite list of jobs has finitely many orders; a finite list of activities has finitely many subsets. At least one feasible choice exists, so a smallest or largest value is attained. For interval markers, choosing one endpoint from each interval gives a finite cover; the smallest achievable number of markers is then a nonnegative integer. We are not assuming that an arbitrary real-valued bound is always attained.
Worked example 1: a tempting choice can block a better pair
You have 6 preparation hours and may complete each project at most once. Project A takes 4 hours and earns 18 points. Projects B and C each take 3 hours and earn 12 points. Your goal is to maximise total points. The rule “choose the remaining project with the most points that still fits” selects A first. Is it optimal?
Reasoning
After choosing A, only 2 hours remain, so neither B nor C fits. The rule earns 18 points. But B and C together take 6 hours and earn 24 points. They are a feasible improvement, so the proposed rule is false.
To confirm the actual optimum, separate the possibilities. Any choice containing A cannot contain B or C and earns at most 18. Without A, taking both B and C earns 24, which is at least the value of either alone. Thus 24 is the maximum. We have proved more than “A looks unwise”: we have exhausted the two possible cases.
The lesson is about the rule, not about these particular numbers. A locally attractive choice may consume a resource needed by a better combination.
Your turn 1
Keep the 6-hour budget and the same durations, but change A’s value to 25 points. Does the same rule now fail?
Check your reasoning
Now A earns 25, while B and C together earn 24. Choices containing A cannot include either other project, so A is optimal for this input. One success does not rescue the universal rule disproved above. A rule may work on some inputs and fail on others.
Worked example 2: put shorter jobs first
Four jobs take 7, 3, 5 and 2 minutes. Every job is ready at time 0. They run one at a time without interruption, and all must be completed. Find an order that minimises the sum of their completion times.
Reasoning
Try the shortest jobs first: 2, 3, 5, 7. Their completion times are 2, 5, 10 and 17, whose sum is 34. Merely finding this order does not prove optimality. We need to show why changing another order towards this one cannot hurt.
Suppose two neighbouring jobs have durations a and b, with a > b, and earlier work ends at time T. In the order a then b, these two completion times sum to (T + a) + (T + a + b) = 2T + 2a + b. In the order b then a, the sum is 2T + 2b + a. The first sum exceeds the second by .
Jobs before the pair do not change. The pair still takes a + b minutes, so every later job starts and finishes at the same time as before. The swap therefore strictly reduces the total objective. A nondecreasing order means shortest to longest, allowing ties. If every neighbouring pair is already in that order, the whole list is ordered. Therefore any list that is not nondecreasing must have a neighbouring longer-before-shorter pair. Its improving swap shows that the list cannot be optimal. A nondecreasing order must be optimal because a minimum exists among the finitely many orders, and every minimum has that form. Equal durations may be interchanged without changing the result.
What made this exchange safe? Both orders are allowed, the later jobs are unaffected, and the change in the objective has a definite sign.
Your turn 2
All three jobs of lengths 6, 1 and 4 minutes are ready at time 0. Find the least sum of completion times.
Check your reasoning
Use the proved order 1, 4, 6. The completion times are 1, 5 and 11, so the minimum is 17. The sum of durations is 11; it is the last completion time, not the sum of all three completion times.
Worked example 3: finish early to leave room
Select as many fixed activities as possible, with no overlap. Each activity has a start time s and a later finish time f, so s < f; you may not shorten or move it. One activity may start exactly when the previous one finishes. The activities are A [0,4), B [1,2), C [2,5), D [4,6), E [5,7), F [7,8).
Reasoning
The earliest finish is B at time 2. Keep B and discard activities starting before 2. Among the remaining activities choose C, which finishes at 5; then E, which finishes at 7; then F. This gives B, C, E, F: four activities.
Here is the proof of the general rule. Among all maximum-size schedules, take one and call its first activity O. Let G be an activity with earliest finish among all available activities. Because G finishes no later than O, replacing O by G cannot conflict with any activity after O. Every later activity starts at or after O’s finish, and therefore also at or after G’s finish. We have a maximum-size schedule beginning with G.
Now remove G and look only at activities starting at or after its finish. The remaining activities of our optimal schedule must form a maximum-size schedule for that smaller problem. Otherwise we could put a larger remaining schedule after G and improve the original maximum, which is impossible. The same first-choice exchange therefore applies to an optimal solution of the smaller problem. Repeating it proves that choosing the earliest finish at every stage gives a maximum number of activities. With no activities left, the process stops. If several activities tie for earliest finish, any of them is safe for this unweighted counting objective.
The rule is earliest finish, not earliest start or shortest duration. It also relies on every selected activity contributing exactly one to the objective. Different rewards need a new argument.
Your turn 3
Choose the greatest number from P [0,3), Q [1,2), R [2,4), S [4,5), T [3,6), using the same endpoint rule.
Check your reasoning
Earliest finish chooses Q, then R, then S. They form a feasible chain of three. The exchange proof above establishes that no schedule has more. Choosing the earlier-starting P would leave fewer opportunities; the relevant comparison is the finish time.
Worked example 4: one marker can meet several intervals
Place as few points on a number line as possible so that every closed interval in this list contains at least one chosen point: [1,4], [2,6], [5,7], [6,9], [9,11]. Closed means that either endpoint counts. A point may serve several intervals.
Reasoning
Choose the right endpoint of the interval that ends first. Here that point is 4, which meets [1,4] and [2,6]. Remove those intervals. The next earliest right endpoint is 7, which meets [5,7] and [6,9]. The remaining interval [9,11] is met by 11. Thus three markers suffice.
Why can we safely put the first marker at 4? Any valid solution needs some point p inside [1,4]. Replace that point by 4. If another interval contains p, its left endpoint is at most p, hence at most 4. Its right endpoint is at least 4, because [1,4] ends first. Therefore that other interval also contains 4. The move loses no covered interval and adds no marker.
For the general argument, start with a minimum-size cover of the remaining intervals. Let r be their earliest right endpoint. Move one of the cover’s markers from that interval to r, using the same safe exchange. We have a minimum cover containing r. Keep r, and remove every interval it meets. The other markers must give a minimum cover of the intervals still uncovered: if fewer markers could cover them, those fewer markers together with r would improve the original minimum. We may therefore repeat the argument on this smaller covering problem. Each step removes at least one interval, so the finite process ends and proves the greedy method optimal.
There is also a quick lower-bound certificate for this example. The three intervals [1,4], [5,7] and [9,11] are pairwise disjoint. A single point cannot lie in two of them, so every valid solution needs at least three points. Our construction meets that lower bound.
Your turn 4
How many markers are needed for the closed intervals [0,2], [2,5], [4,6], [6,8]?
Check your reasoning
The points 2 and 6 meet all four intervals. At least two points are needed because [0,2] and [4,6] are disjoint. Thus the minimum is two. Sharing an endpoint is allowed here: 2 meets both of the first two closed intervals.
From following a rule to choosing the right rule
The examples use different exchange directions. For job ordering, a swap improves a numerical total. For activity selection, an earlier finish preserves room for all later choices. For interval markers, moving a point rightwards preserves every interval it previously met because no remaining interval ends earlier.
When a problem changes, ask which line of the proof survives. A fixed changeover gap preserves the finish-time comparison. Different job weights change the cost comparison. Different activity rewards destroy the claim that preserving the number selected preserves the objective. Problems 4–9 practise those distinctions.
For a minimum or maximum, look for two matching parts: a construction that achieves a value and a bound saying no solution can do better. Such a pair is often easier to communicate than a long list of trials.
Nine original written problems
Use paper for the proof. Try the first hint before the second. After reading a solution, close it and reconstruct the argument. The tiers below describe this lesson’s progression, not official examination categories.
Build the model: problems 1–3
1. A project rule under a budget
A preparation club has 8 hours. Each project may be chosen at most once: A takes 7 hours and is worth 19 points; B takes 4 hours and is worth 12; C takes 4 hours and is worth 11; D takes 1 hour and is worth 1. The rule repeatedly chooses the highest-value project that still fits. Find its score, find the true maximum, and prove the maximum.
Hint 1
Follow the rule completely; then compare it with a pair of medium-sized projects.
Hint 2
Separate choices that contain A from choices that do not.
Complete solution
The rule chooses A and then D, using all 8 hours and earning 20 points. B and C together also use 8 hours but earn 23 points.
To prove 23 is the maximum, first suppose A is selected. Only 1 hour remains, so at most D can be added; the score is at most 20. Without A, choosing B, C and D together is impossible because they need 9 hours. The feasible two-project scores are 23 for B + C, 13 for B + D, and 12 for C + D. A single project scores at most 12 in this case, and the empty choice scores 0. Therefore no feasible choice exceeds 23, and B + C attains it.
Proof check: Check both cases, the 8-hour constraint and the complete greedy run. A better feasible choice disproves the rule; the case analysis proves the optimum.
2. The sum is not the finishing time
Four jobs of lengths 3, 8, 2 and 5 minutes are all ready at time 0. They run one at a time without interruption and all must be done. Find the least sum of completion times, and explain why no other order gives a smaller sum.
Hint 1
Compare two neighbouring jobs when the longer one is first.
Hint 2
Their swap changes only their two completion times. Use Worked example 2.
Complete solution
Put the jobs in the order 2, 3, 5, 8. They finish at 2, 5, 10 and 18, so the sum is 35.
If any order has a longer job of duration a immediately before a shorter job of duration b, swapping them reduces the sum by a − b while leaving all later completion times unchanged. Any non-sorted order has such an adjacent descent. Consequently an optimal order is nondecreasing, and our order has the minimum sum. The total time 18 alone is not the objective: it is the same for every order.
Proof check: State readiness and non-interruption, identify the safe adjacent swap, and distinguish 35 from the final finishing time 18.
3. Shortest activity is a different rule
Three fixed activities are A [0,4), B [3,5), C [4,8). Activities may touch at endpoints but may not overlap. A proposed rule chooses the shortest activity first, deletes activities that conflict with it, and repeats. Run this rule, find the true maximum number, and identify the step where the earliest-finish exchange proof would fail for the shortest-activity rule.
Hint 1
B is shortest, but ask what it prevents you from selecting.
Hint 2
The exchange proof needs the replacement to finish no later than the first activity in an optimal schedule.
Complete solution
B has duration 2, whereas A and C each have duration 4. The shortest-first rule chooses B. B overlaps A during times from 3 to 4 and C during times from 4 to 5, so it deletes both and returns one activity.
A followed by C is feasible because C starts exactly when A finishes. It gives two activities. Three are impossible since B conflicts with each other activity, so two is the maximum.
The attempted exchange would replace A, which finishes at 4, by B, which finishes at 5. This would make the later activity C infeasible. Shorter duration does not imply earlier finish, so the crucial safe-replacement inequality is missing.
Proof check: Explain the actual overlapping time ranges and point to the failed finish-time comparison, not just the different answers.
Transfer the exchange: problems 4–6
4. Allow a fixed changeover time
The fixed activities are A [0,2), B [1,3), C [3,5), D [4,6), E [6,8), F [7,9). After each selected activity, allow at least 1 time unit before the next selected activity starts; no break is needed before the first or after the last. Find the maximum number that can be selected. Prove that, for any finite set of activities with this same fixed one-unit changeover rule, choosing earliest finish and then keeping only activities starting at least one unit later remains optimal.
Hint 1
After choosing an activity ending at f, the next start must be at least f + 1.
Hint 2
If G finishes no later than O, compare finish(G) + 1 with finish(O) + 1.
Complete solution
The greedy choice A finishes at 2. The next activity must start at or after 3, so choose C, finishing at 5. Next choose E, starting at 6. This gives three activities.
For the general proof, take a schedule with the maximum number and call its first activity O. Choose G with earliest finish among all activities. Every later activity in that schedule begins at or after finish(O) + 1. Since finish(G) ≤ finish(O), it also begins at or after finish(G) + 1. Replacing O by G therefore preserves the schedule and its size. Apply the same exchange to the remaining activities starting at or after finish(G) + 1. Repetition proves the greedy method optimal, including the case of no remaining activity. Applied to the given list, it proves that the feasible three-activity schedule A, C, E is maximum.
Proof check: Keep the same one-unit gap for every transition. Explicitly preserve compatibility after the exchange; an activity-dependent gap would require another proof.
5. Some jobs matter more
Every job is ready at time 0 and runs without interruption on one machine. A job of weight w contributes w times its completion time to the objective. (a) Two neighbouring jobs A and B have positive durations p and q and positive weights u and v. Show that putting A before B is no worse than the reverse precisely when p/u ≤ q/v. (b) Use this to minimise the weighted sum for A: duration 4, weight 3; B: duration 3, weight 5; C: duration 2, weight 2.
Hint 1
Write the two weighted contributions for each order, allowing previous jobs to end at time T.
Hint 2
Subtract the two expressions. All terms involving T cancel.
Complete solution
(a) If earlier work finishes at time T, the order A then B contributes u(T + p) + v(T + p + q). The order B then A contributes v(T + q) + u(T + q + p). Subtracting the second expression from the first gives vp − uq. Later jobs are unaffected because the pair takes p + q in either order.
Thus A before B is no worse exactly when vp − uq ≤ 0. Dividing by the positive number uv gives p/u ≤ q/v. Positivity matters: it allows division without changing the inequality direction.
(b) The duration-to-weight ratios are 4/3 for A, 3/5 for B, and 1 for C. Their increasing order is B, C, A. Their completion times are 3, 5 and 9; the weighted sum is 5 × 3 + 2 × 5 + 3 × 9 = 52.
For optimality, any order with a neighbouring inverted ratio can be improved by the exchange in part (a). An order not sorted by ratio must have an adjacent inversion. Therefore every minimum is sorted by ratio, apart from harmless ties. A minimum exists among the finitely many orders, so the displayed sorted order achieves it. Notice that shortest duration alone would put C before B and can be wrong for this changed objective.
Proof check: Compare weighted costs, not ordinary completion sums; explain why later jobs are unaffected and why the positive weights permit the ratio test.
6. Pair small with large
Six card values are 2, 3, 7, 10, 12 and 20. Divide them into three pairs to minimise the largest pair sum. Find the minimum. Then prove the general rule: for any positive integer n and any 2n positive numbers written in nondecreasing order, pairing the smallest with the largest, the next smallest with the next largest, and so on minimises the largest pair sum. Equal values are allowed.
Hint 1
Try pairing the two extremes. For the proof, begin with an optimal pairing and inspect the pairs containing its smallest and largest numbers.
Hint 2
If the smallest a is paired with b and the largest d with c, replace those pairs by (a,d) and (b,c). Compare both new sums with c + d.
Complete solution
The extreme pairs are (2,20), (3,12) and (7,10), with sums 22, 15 and 17. Their largest sum is 22. In any pairing, the card 20 must be paired with a value at least 2, so some pair has sum at least 22. The construction therefore gives the minimum.
For the general proof, choose an optimal pairing; one exists because there are finitely many pairings. Let a be the smallest remaining number and d the largest. If they are already paired, keep that pair. Otherwise their two pairs are (a,b) and (c,d), using four different cards even if some values coincide.
Replace them by (a,d) and (b,c). Because a ≤ c, we have a + d ≤ c + d. Because b ≤ d, we also have b + c ≤ d + c. Both new sums are at most the old pair sum c + d, and hence at most the old largest pair sum. Other pairs are unchanged. The exchange cannot increase the objective, so there is an optimal pairing containing (a,d).
Remove those two cards and repeat the argument among the remaining cards. Each step keeps a pairing whose largest sum is no worse. Eventually all pairs are the extreme pairs. Since we started from an optimum, the resulting extreme pairing is also optimal. The proof uses non-strict inequalities, so equal card values cause no problem.
Proof check: Give both the lower bound and attaining construction for the example. In the general exchange, check both new sums and all unchanged pairs.
Build an optimality certificate: problems 7–9
7. Markers with a certificate
Place the fewest points meeting all these closed intervals: [0,3], [2,5], [4,6], [5,8], [7,10], [9,12]. Give a set of markers and a lower-bound certificate that proves no smaller set works.
Hint 1
Use the earliest remaining right endpoint, then remove the intervals it meets.
Hint 2
Find three pairwise disjoint intervals from the original list.
Complete solution
Choose 3, 6 and 10. The marker 3 meets [0,3] and [2,5]; 6 meets [4,6] and [5,8]; 10 meets [7,10] and [9,12]. Hence three markers suffice.
The original intervals [0,3], [4,6] and [7,10] are pairwise disjoint, so no one point can meet two of them. Any valid set must therefore contain at least three distinct markers. Together with the construction, this proves that three is the minimum. The certificate proves optimality without testing every possible real-valued marker position.
Proof check: Every original interval must be covered, and the three witness intervals must really be disjoint, including their endpoints.
8. Cover points with equal-length windows
The points 0, 1, 2, 4, 5, 7, 8, 9 and 11 lie on a number line. Cover them with as few closed intervals of length 3 as possible; intervals may overlap and their endpoints may be any real numbers. Find the minimum. Prove the general rule for any finite point set and any fixed length L > 0: repeatedly take the leftmost uncovered point x and place [x, x + L].
Hint 1
A window beginning at the leftmost uncovered point reaches as far right as possible while still covering that point.
Hint 2
Take an interval [a, a + L] of an optimal remaining cover that contains x. Move it to [x, x + L]. Explain why no remaining point is lost.
Complete solution
Use the intervals [0,3], [4,7], [8,11]. They cover every listed point. The three points 0, 4 and 8 are pairwise more than 3 units apart, so no length-3 interval can contain two of them. At least three intervals are needed, and the displayed cover shows that three is the minimum.
For the general proof, let x be the leftmost point still needing coverage. An optimal cover of the remaining points has some interval [a, a + L] containing x. Thus a ≤ x ≤ a + L. Move that interval to [x, x + L]. A remaining point y formerly in it satisfies y ≥ x, because x is leftmost. It also satisfies y ≤ a + L ≤ x + L. Therefore y remains covered after the move.
So there is an optimal remaining cover containing the greedy window [x, x + L]. Remove the points this window covers and repeat. Each repetition removes at least x, so the finite process ends. It uses no more windows than an optimal cover, and is consequently optimal. An empty point set needs zero windows.
Proof check: Explain both inequalities x ≤ y ≤ x + L after the shift. Do not claim that points left of x stay covered; there are no remaining points there.
9. Choose the jobs as well as their order
Six jobs have durations 9, 4, 8, 6, 3 and 7 minutes. All are ready at time 0. One machine runs a chosen job to completion without interruption, and you have 25 minutes. (a) Complete as many jobs as possible. Among choices attaining that number, minimise the sum of completion times. Give the order and both optimum values. (b) Prove the corresponding rule for any finite list of positive durations and time budget B ≥ 0: choose as many of the shortest jobs as fit, and run those jobs in nondecreasing order.
Hint 1
Sort the durations. The sum of the k shortest is a lower bound for the total duration of every selection of k jobs.
Hint 2
For the second objective, compare the sorted selected durations with the first k durations of the full sorted list, position by position.
Complete solution
(a) The sorted durations are 3, 4, 6, 7, 8, 9. The first four sum to 20, so four jobs fit. The first five sum to 28. Every choice of five jobs takes at least 28 minutes, so five cannot fit in 25. Thus four jobs is the maximum.
Choose 3, 4, 6, 7 and run them in that order. Their completion times are 3, 7, 13 and 20, with sum 43. We now justify that no other four-job choice has a smaller sum.
(b) Write the full sorted list as a1 ≤ a2 ≤ … ≤ an. For any selection of k jobs, write its sorted durations as b1 ≤ … ≤ bk. We have bi ≥ ai for each i: the ith smallest selected value cannot occur earlier than the ith position in the full sorted list. Therefore every selection of k jobs has total duration at least a1 + … + ak.
Let k be the largest number of initial shortest jobs whose sum is at most B, allowing k = 0. Those k jobs fit. If k < n, every selection of k + 1 jobs has total duration at least the first k + 1 durations, which exceeds B. Hence k is the maximum count.
For a fixed selection, Worked example 2 proves that sorted order minimises the sum of completion times. In that order, the jth completion time is b1 + … + bj, which is at least a1 + … + aj. Summing these inequalities for j = 1,…,k proves that choosing the k shortest and sorting them also minimises the completion-time sum among all maximum-count choices. For k = 0 the sum is 0; for k = n every job is selected. This gives the claimed general rule and proves the value 43 in part (a).
Proof check: Prove the maximum count before the second objective. State why the ith selected duration is no smaller than the ith full-list duration, and handle an empty feasible selection.
Common mistakes and repairs
- “It worked on my examples.” Replace the sample list with an argument for an arbitrary allowed input, or find a counterexample.
- Changing the wrong objective. Total processing time, sum of completion times, weighted sum and number of selected jobs are different quantities. Write the exact objective before comparing choices.
- An infeasible exchange. Check resources, overlap, readiness, endpoint rules and every later choice affected by the move.
- Only proving the first choice. Explain why the remaining task admits the same argument and why the finite process ends.
- “Every optimum must look like mine.” You usually only need an optimum containing the greedy choice; ties may give other optima.
- Confusing the two interval models. Activities [s,f) allow a next start equal to f. Closed covering intervals [l,r] include both endpoints.
- Using an old proof after changing the rules. Identify the exact inequality or preserved quantity. If it no longer follows, the greedy rule needs a fresh proof.
Check your written proof
This is an editorial self-check, not official marking. A complete proof identifies the objective, states a valid comparison solution, describes the exchange, checks feasibility, compares the objective, and completes the repetition or bound-and-construction argument. If one item is missing, repair that step before trying a harder question. An automatic multiple-choice result cannot grade an arbitrary written proof.
Try six adaptive checks
These short questions test the decisions inside the arguments. Choose Start with the basics, or use Check my starting point if the ideas are familiar. The session adjusts question level from your responses and offers hints, explanations and a route back to the relevant lesson section.
Interactive practice loads here. You can also use the complete question set below.
Finish and return: record six responses, then choose See my session summary and review the explanations. Requesting a solution counts as a response; six responses mean session completion, not mastery. Retry one written problem without its solution. If you arrived from a country or paper link, use the completion screen’s return option to revisit it.
Use the idea in your paper
Return to Vietnam’s paper links. Before using a greedy rule in a new problem, write the objective and the exchange that would make it safe. If you cannot justify that exchange, test small counterexamples. For related proof tools, study the extremal principle and invariants; neither automatically proves a greedy rule correct.
Sources and authorship
Explanations, project settings, activities, practice questions and the timeline are original IMOolympiad Editorial Desk material. The exchange method is a standard mathematical technique. The Ministry’s release of the 2025–26 national papers and answers and the government-hosted official mathematics paper informed the preparation context. Official questions are linked, not reproduced or translated. This independent lesson is not affiliated with or endorsed by the Ministry or the IMO. Sources checked 21 October 2026.