Випадкове блукання змійки на клітинній дошці

Умова задачі

Змійка довжини $k$ — це тварина, яка займає впорядкований $k$ -набір $(s_{1}, \ldots, s_{k})$ клітин на клітинній дошці $n \times n$ з квадратних одиничних клітин. Ці клітини мають бути попарно різними, а $s_{i}$ і $s_{i+1}$ повинні мати спільну сторону при $i=1, \ldots, k-1$ . Якщо змійка зараз займає $(s_{1}, \ldots, s_{k})$ , а $s$ — вільна клітина, що має спільну сторону з $s_{1}$ , то змійка може перейти й зайняти $(s, s_{1}, \ldots, s_{k-1})$ замість цього.

Спочатку змійка довжини 4 перебуває на дошці $\{1,2, \ldots, 30\}^{2}$ і займає позиції $(1,1),(1,2),(1,3),(1,4)$ , причому $(1,1)$ — її голова. Змійка неодноразово робить хід рівномірно навмання серед ходів, які вона може легально зробити. Оцініть $N$ — математичне сподівання кількості ходів, які зробить змійка, доки в неї не залишиться жодного дозволеного ходу.

Оцінка $E>0$ принесе $\left\lfloor 22 \min (N / E, E / N)^{4}\right\rfloor$ балів.

Пов’язані теми

Лінійні рівняння та системи

Олімпіадні задачі з математики

Задачі дня

Випадкове блукання змійки на клітинній дошці

Умова задачі

Пов’язані теми

Рекомендації щодо вивчення олімпіадної математики

Гурток за п’ять хвилин

П’ять років програми

Шість правил, підтверджених дослідженнями

Ритм олімпіадного року

Як зібрати задачі тут

Про проєкт

Автори задач

Що в архіві

Українські олімпіади й турніри

Міжнародні олімпіади

Змагання інших країн

Що є в кожної задачі

З чого почати

Хто це робить

Помилки та пропозиції

Автори задач

Богдан Рубльов

Українські олімпіади й турніри

Міжнародні й закордонні змагання

Дякуємо