Олимпиада им. Эйлера

Пронумеруем пробирки числами от до и бочки числами от до Назовем операцией последовательное наливание в пробирки номер номер ..., номер (именно в таком порядке) реактива из -ой бочки. Операцией назовем последовательное наливание реактива из -ой бочки в пробирки с номерами

Будем последовательно проводить операции пока какая-то пробирка не лопнет при операции (после чего операция прекращается). Это рано или поздно произойдет, так как среди реактива, которые надо наливать в пробирку обязательно найдутся два конфликтующих. Перед операцией в пробирке находятся реактивы от до в пробирке — от до в пробирке — реактив Поскольку пробирки с номерами от до не лопнули, реактив конфликтует именно с реактивом Уберем бочки с двумя конфликтующими реактивами, перенумеруем реактивы и бочки в том же порядке, в котором шли их старые номера. Про то, что убранные реактивы находятся в каких-то пробирках, можно забыть, так как они не повлияют на дальнейшие реакции.

Мы убрали два реактива, и сейчас в пробирке находятся реактивы от до (в новой нумерации), в пробирке — от до в пробирке — реактив Начинаем проводить операции пока какая-то пробирка не лопнет (это обязательно произойдет по той же причине, что и выше). Когда пробирка лопается, проделываем то же, что в предыдущем абзаце. Таким образом, потеряв одну пробирку, мы определяем одну пару конфликтующих реактивов. Значит, мы сможем определить все пары конфликтующих реактивов.