Контрпримеры малого размера для трехмерной задачи поиска устойчивых мэтчингов с циклическими предпочтениями

Рассмотрим $n$ мужчин, $n$ женщин и $n$ собак, каждый мужчина имеет полный список предпочтений женщин, каждая женщина полный список предпочтений собак и каждая собака имеет полный список предпочтений мужчин (мы рассматриваем так называемую 3D-CYC problem — трехмерную задачу с циклическими предпочтениями). Трисочетание есть набор $n$ непересекающихся троек, содержащих по одному представителю каждого гендера. Трисочетание называется устойчивым (так называемым stable matching (SM)), если не существует мужчины, женщины и собаки из разных троек предпочитающих друг друга партнерам в своих тройках. Гиптотеза Эрикссона, Состранда и Стримлинга (2006) состояла в том, что задача отыскания SM (так называемая 3DSM-CYC задача) всегда имеет решение. Постепенно гипотеза была доказана для всех $n\leqslant 5$. Однако К.-К. Лам и К. Пакстон (2019) предложили алгоритм конструирования матриц предпочтений для 3DSM-CYC размера $n=90$, при которых SM не существует. Вопрос о существовании контрпримеров меньшего размера оставался открытым. В этой работе мы построим наглядный контрпример для 3DSM-CYC размера $n=24$.