Давным-давно в одной железнодорожной компании решили сократить издержки и комплектовать туалетами только половину вагонов в составе поезда. Жалобы пошли нескончаемым потоком: на сортировочной станции вагоны не различали, так что в составе каждого поезда туалетов было случайное количество. Могло не быть вообще.
Тогда в системе вагоны пометили, условно говорят, 0 — нет туалета, 1 — есть туалет. И выпустили приказ: ставить по возможности одинаковое количество вагонов разных типов. Работа сортировочной станции усложнилась, но они справились. Однако поток жалоб не ослабевал.
Стали разбираться. Оказалось, что хотя в составе поезда и была примерно половина вагонов с туалетами, они нередко оказывались в одном конце состава. Выпустили ещё один приказ: чередовать вагоны.
Сортировщикам стало сложнее, но окей, справились и с этим. Но жалобы продолжали поступать.
Снова провели служебное расследование. Выяснилось, что, поскольку туалеты у вагонов были только с одной стороны, при неудачном раскладе расстояние между соседними туалетами могло достигать трёх вагонов. Это было неудобно вообще никому, а родителям с маленькими детьми — критично. Особенно если проходы были заставлены багажом.
Тогда вагоны пометили ещё одним признаком, система стала видеть, с какого конца у них туалет. И вот с этим на сортировочной станции стало совсем тяжело: поворотных кругов катастрофически не хватало на то, чтобы ставить вагоны не просто в определённом порядке, но ещё и определённым концом.
Но справились и с этим. Теперь расстояние до ближайшего туалета в поезде не превышало одного вагона.
Но жалобы валились прежними темпами: люди не знали, в какую сторону идти именно к ближайшему, а не к дальнему туалету!
Это затруднение решили просто: во всех вагонах нарисовали указатели —стрелки с надписью "Туалет". Но чтобы система работала, стрелки должны висеть и в тех вагонах, где туалета нет — а значит, становилось важным, как ставить и их тоже. Языком математики, все вагоны превратились в направленные объекты.
С этим сортировке было уже не справиться.
Решение
Ситуация стала критической, и тут кто-то, чьё имя не сохранилось, предложил решение. Если к каждому вагону с туалетом с того конца, где расположен туалет, прицепить вагон без туалета, то получится почти симметричная единица с туалетом почти посередине.
И сортировочная станция может просто комплектовать поезда из этих двухвагонных сцепов. И стрелочки не нужны. И любым концом можно ставить.
Ценой решения стала необходимость купить дополнительные вагоны, чтобы во всех поездах их было чётное количество. Ну и расстояние до туалетов лишь условно можно считать равным: в одном случае заветная дверь расположена в ближайшем вагоне, в другом надо ещё тамбур пройти. Но это уже мелочи.
=======================
Эту байку любил рассказывать выдающийся голландский информатик Эдсгер Дейкстра, а задачу в итоге назвали его именем.