Комбинаторные друзья

[grizzly]

Очередная задача из неструктурированного (пока) дайджеста нерешённых MSE задач.

За круглым столом рассажены $n$ гостей. Сидящие рядом считаются друзьями. За один ход мы можем поменять местами двух человек. Вопрос: за какое число ходов мы можем "подружить" всех гостей?

Похоже, эта задача тоже сложнее своей формулировки.

[iancaple]

Похоже на задачи конкурсов Зиммермана, где оптимальность ответов принципиально недоказуема, но из-за огромного числа участников 99% гарантия, что найдут оптимальные. В связи с этим интересно, человек, который дал свои оценки сверху для $n=4...16$, вел ли полный перебор или там эвристика.

[grizzly]

iancaple в сообщении #1057131 писал(а):

В связи с этим интересно, человек, который дал свои оценки сверху для $n=4...16$, вел ли полный перебор или там эвристика.

В комментариях автор пишет, что от 4 до 8 включительно он уверен в результатах и надеется, что его программа перебора написана без ошибок. Можно предположить, что для больших значений перебор был не полным.

В комментариях там скромно пытаются оценивать и сверху и снизу в общем случае. Я посмотрю эти оценки и, если имеет смысл, приведу здесь те, в которых смогу разобраться.

-- 27.09.2015, 23:47 --

На всякий случай предупрежу, чтобы не ввести случайно в заблуждение тех, кому сложнее с английским. По ссылке рассматривается 2 варианта задачи, из которых я сформулировал только второй (для функции $g(x)$ в тех терминах). Именно для этого варианта там приведены оценки в таблице.