Максимальный поток, баян и блуждания на прямой – конкурс

[Zealint]

Модераторам: ссылка на форум dxdy.ru, как на информационного спонсора, указана на странице конкурса.

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

На этот раз три задачи. Здесь приводятся краткие описания задач, а на странице конкурса (ссылка ниже) - полные описания.

Задача 1. Плохая сеть для поиска максимального потока.
Здесь предлагается отыскать сеть, в которой алгоритм Эдмондса-Карпа для поиска максимального потока выполняет как можно больше итераций поиска дополняющего пути. Данный алгоритм ищет минимальный по длине дополняющий путь, а в естественной реализации из всех минимальных выбирает лексикографически минимальный. Максимальное возможное число вершин - 256. Напомню, что теоретически алгоритм Эдмондса-Карпа выполняет $O(nm)$ поисков дополняющего пути, а на каждый поиск уходит $O(m)$ элементарных операций ($n$ - число вершин, а $m$ - число рёбер). И также напомню, что эта асимптотика является точной. Однако в конкурсе нужно придумать сеть, в которой число вершин ограничено, а количество операций поиска - максимально возможное для этого ограничения. У кого в сети будет больше итераций, тот и победил.

Задача 2. Королевский баян
Имеется шахматная доска размером $2n\times 2n$ ($n\in \mathbb N$). Сколькими способами можно расположить на ней $n^2$ королей так, чтобы они не били друг друга? Конкурс начинается от $n=12$, так как до 11 ответы известны уже более 10 лет [A018807].

Задача 3. Блуждания на прямой
Существует классическая задача о блуждании на прямой. Точка находится в начале координатной прямой и за один шаг обязана прыгнуть на $1, 2, \ldots, k$ делений вперёд или назад. Сколькими способами она может оказаться в начале координат ровно через $n$ шагов?
Для $k=1$ и $n=0,1,\ldots,10$ мы получим последовательность [1,0,2,0,6,0,20,0,70,0,252] (не надо обращать внимание на то, что здесь видны центральные биномиальные коэффициенты, это не важно). Последовательность удовлетворяет линейному однородному рекуррентному соотношению с полиномиальными коэффициентами:

$$ n\cdot a_n = 4\cdot (n-1)\cdot a_{n-2}, \qquad n\geq 2 $$

Ответы для $k=2,3,4$ тоже известны. Требуется вывести рекуррентные соотношения для $k=5,6,\ldots$. Кто дальше - тот и победил.

Несмотря на кажущуюся сложность, задача хоть и трудная (нет эффективного алгоритма для любого $k$), но не сложная для многих фиксированных $k$.

Если задачи Вас заинтересовали, прошу на страницу конкурса.

[Zealint]

Конкурс завершился. Предлагаю ознакомиться с его итогами.

Вторую задачу удалось пробить до $n=20$, что весьма неплохо. Последнюю никто не пытался решать.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.