A teammate balances two shards by sorting record sizes descending and alternating — how do you disprove it?

## The claim under review A teammate proposes splitting sized records into two shards by sorting sizes descending and dealing them out alternately, aiming to minimise the larger shard's total load. They report that it passes their tests. Your job as reviewer is to decide whether the rule is *correct*, and "the tests are green" does not answer that question — a test suite samples inputs, while a correctness claim quantifies over all of them. ## Finding the counterexample Start with the smallest instance that can possibly differ. With one or two records every rule agrees. With three, the alternating rule pairs the first and third records against the second alone, and that pairing is exactly where it fails: it can be beaten whenever the two smaller records together are lighter than one big one plus a small one. Sizes `3, 2, 2`, already sorted descending. Alternating gives shard A = `3 + 2 = 5` and shard B = `2`, so the larger load is 5. But splitting `3` against `2 + 2` gives loads 3 and 4, a larger load of 4. Since a valid split with larger-load 4 exists, the rule is not optimal. One instance, three numbers, done — and small enough to paste into a review comment and to keep as a regression test. ## The search method, generalised Counterexample hunting is a craft with a repeatable order of attack: 1. **Smallest first.** Most greedy heuristics break at `n` of 3 or 4. Minimal counterexamples are easier to explain, easier to turn into a test, and usually expose the structural flaw rather than an accident. 2. **Structural extremes.** All values equal; one value dominating the sum of the rest; values that admit an exact even split; values that force ties in the sort. Ties and exact splits are where tie-breaking rules quietly decide the answer. 3. **Differential testing.** When hand search stalls, enumerate every possible assignment for small `n` (exhaustive for `n` up to roughly a dozen) and compare against the heuristic on random and adversarial inputs. This is the mechanical version of the same search, and it finds what intuition misses. 4. **Read the failed proof.** If you tried an exchange argument and the swap could not be made at some position, that position tells you what the counterexample must look like. Proof attempts and counterexample searches are the same activity approached from two directions. ## What a *failed* search proves Nothing. This is the point most reviews get wrong in the other direction: after a million random instances with no violation, the rule is still unproven. Counterexamples cluster in structured corners — exact ties, dominating elements, exact-split totals — that uniform random sampling rarely produces. The absence of a found counterexample is weak evidence, not a theorem. So the review has exactly three acceptable outcomes: a counterexample (the rule is wrong), a proof (an exchange or stays-ahead argument, written down), or an explicit downgrade — the rule is accepted as a heuristic with a stated guarantee and a monitored metric. ## The deeper reason no patch will fix it Before proposing a better tie-break, ask whether an exact greedy can exist at all. Deciding whether a set of sizes can be split into two equally-loaded halves is a classic NP-hard problem, and minimising the larger load is the optimisation version of it. So no efficient rule — greedy or otherwise — is exactly optimal on all inputs unless a famous open question resolves surprisingly. That reframes the review completely: the goal is not a correct greedy, it is a greedy with a known bound. The standard repair is to assign each record, largest first, to whichever shard is currently lighter. On the `3, 2, 2` instance it produces the optimal 3-versus-4 split, and in general this descending-order least-loaded rule is a well-studied approximation with a proven constant-factor guarantee — never worse than about a third above optimal for any number of shards, and tighter for two. It is still not exact, and saying so is the honest review comment. ## Writing the review A good comment does three things in three lines: gives the counterexample with concrete numbers, names what is actually being claimed (exact optimality versus an approximation), and states which of the three outcomes you expect back. Avoid "this feels wrong" — a counterexample ends the discussion, an intuition starts a longer one.