Odd-Length Exchanges in ABO-Only Kidney Exchange: A Feasibility Puzzle for the Classroom

Most classroom puzzles in operations research emphasize optimizing an objective; here, we instead pose a feasibility puzzle rooted in kidney exchange programs. We ask whether odd-length cycles—three-way exchanges as the canonical case—can arise when every donor-recipient pair is internally incompatible and compatibility is defined by ABO blood type alone. We formalize the puzzle as a mixed-integer feasibility model that encodes assignment, incompatibility, and donor-to-next-recipient implication constraints. Simple variable fixings collapse the model to a reduced formulation whose structure reveals a bipartition of the cycle-capable nodes (A to B and B to A), thereby precluding any odd cycle and certifying infeasibility for the three-way case; the same logic extends to all odd lengths $\ge 5$. We provide a concise Python and Gurobi implementation and an undergraduate classroom activity that uses the model to contrast feasibility reasoning with optimization thinking, connect blood-compatibility rules to mathematical constraints, and practice modular indexing on cyclic structures. The puzzle thus serves both as a correctness certificate for the ABO-only setting and as a compact teaching vehicle linking graph structure and integer programming.

Supplemental Material: Data is available at https://www.informs.org/Publications/Subscribe/Access-Restricted-Materials.