Расстановки без двух запрещённых троек

Какая запрещённая тройка появится, если с одной стороны от 5 найдётся возрастающая пара? Проверьте левую и правую стороны отдельно.

Пусть обе части уже убывают. Может ли между двумя числами левой части по величине находиться число, оставленное справа? Проверьте такую тройку.

1. Число 5 заставляет обе части убывать

Разделим ряд на числа слева от $5$, само $5$ и числа справа. Если слева найдутся два числа $a<b$ в таком порядке, то $a,b,5$ образуют запрещённую возрастающую тройку. Поэтому левая часть убывает. Если справа найдутся $b<c$ в таком порядке, то $5,b,c$ имеют вид $b<c<5$ и также запрещены. Поэтому правая часть тоже убывает.

2. В левой части не может быть пропуска по величине

Допустим, слева есть числа $u>v$, а число $t$ с $v<t<u$ осталось справа. Поскольку левая часть убывает, в ряду числа $u,v,t$ идут именно в таком порядке. При этом $v<t<u$ — второй запрещённый вид. Значит, если левая часть непуста, она состоит из всех чисел некоторого промежутка среди $1,2,3,4$, выписанных по убыванию. Например, допустимый по этому правилу набор $\{2,3,4\}$ даёт блок $4,3,2$; набор $\{2,4\}$ оставляет запрещающий пропуск $3$.

3. Доказываем достаточность найденного правила

Возьмём слева любой непустой промежуток чисел и запишем его по убыванию. Справа от $5$ запишем все остальные числа также по убыванию.

Возрастающая тройка невозможна:

• без $5$ хотя бы два из трёх чисел лежат в одной убывающей части;
• с $5$ понадобилась бы возрастающая пара слева.

Проверим второй запрещённый вид. В нём последние два числа должны возрастать. Они не могут оба лежать в одной части: каждая часть убывает.

Для тройки без $5$ остаётся только случай: первые два числа $u>v$ слева, третье $t$ справа. Запрет потребовал бы $v<t<u$, но все числа между $u$ и $v$ уже находятся в левом промежутке.

Тройка второго вида с $5$ потребовала бы возрастающей пары справа — её тоже нет. Итак, правило достаточно.

Если слева пусто, весь ряд убывает и также подходит.

4. Считаем все промежутки

По выбранному левому промежутку весь ряд определяется однозначно: слева и справа порядок уже задан. Среди четырёх чисел промежутков длины $k\ge1$ ровно $5-k$ — можно выбрать их наименьшее число от $1$ до $5-k$.

Выпишем все хорошие расстановки. Например, запись $15432$ обозначает ряд $1,5,4,3,2$.

Всего хороших расстановок:

$$1+4+3+2+1=11.$$

Можно поручить компьютеру две простые работы: сначала составить все расстановки чисел от $1$ до $5$, затем проверить каждую по условию.

1. Составляем все расстановки. Пять вложенных циклов выбирают первое, второе, третье, четвёртое и пятое числа. Названия first, second, third, fourth, fifth обозначают именно эти места. Если очередное число уже встречалось слева, команда continue пропускает его и берёт следующее значение того же цикла.

Здесь range(1, 6) даёт числа $1,2,3,4,5$: правая граница $6$ не включается. rows = [] создаёт пустой список расстановок, а rows.append(...) добавляет в него одну готовую расстановку.

2. Проверяем любые три позиции. В списке Python места нумеруются с нуля: row[0] — первое число, row[4] — пятое. Три цикла выбирают индексы i < j < k, поэтому числа a, b, c всегда идут слева направо. Например, i = 0, j = 2, k = 4 выбирают первое, третье и пятое числа: соседство не требуется.

Перед проверкой каждой расстановки ставим is_good = True — «пока подходит». Если найдётся тройка любого из двух запрещённых видов, меняем значение на False — «не подходит». Даже одна такая тройка исключает всю расстановку.

# Составляем все расстановки без повторяющихся чисел.
rows = []

for first in range(1, 6):
    for second in range(1, 6):
        if second == first:
            continue
        for third in range(1, 6):
            if third == first or third == second:
                continue
            for fourth in range(1, 6):
                if fourth == first or fourth == second or fourth == third:
                    continue
                for fifth in range(1, 6):
                    if fifth == first or fifth == second or fifth == third or fifth == fourth:
                        continue
                    rows.append([first, second, third, fourth, fifth])

# Проверяем все тройки позиций в каждой расстановке.
good_rows = []

for row in rows:
    is_good = True
    for i in range(0, 3):
        for j in range(i + 1, 4):
            for k in range(j + 1, 5):
                a = row[i]
                b = row[j]
                c = row[k]
                if a < b and b < c:
                    is_good = False
                if b < c and c < a:
                    is_good = False
    if is_good:
        good_rows.append(row)

# Выводим количество хороших расстановок и сами расстановки.
print(len(good_rows))
for row in good_rows:
    print(row[0], row[1], row[2], row[3], row[4])

В проверках or означает «или», and — «и», а == проверяет равенство. Команда if is_good: добавляет ряд в список хороших, только если значение осталось True после всех проверок. len(good_rows) считает сохранённые расстановки, а print выводит результат; пять чисел в последней строке печатаются через пробел.

Почему перебор полный? Для первого места подходят $5$ чисел, для второго — $4$ оставшихся, затем $3$, $2$ и $1$. Поэтому в rows попадут все $5\cdot4\cdot3\cdot2\cdot1=120$ расстановок. Ни одна не потеряется: её числа обязательно встретятся в соответствующих циклах. Ни одна не появится дважды: каждое сочетание значений пяти циклов встречается ровно один раз.

В каждом ряду первый выбранный индекс i принимает значения $0,1,2$ — после него должны остаться ещё два места. Индекс j идёт от i + 1 до $3$, а k — от j + 1 до $4$. Так проверяются все $10$ троек позиций, включая несоседние. Оба запрета проверяются для каждой тройки.

Программа выводит число хороших расстановок, затем каждую из них:

11
1 5 4 3 2
2 1 5 4 3
2 5 4 3 1
3 2 1 5 4
3 2 5 4 1
3 5 4 2 1
4 3 2 1 5
4 3 2 5 1
4 3 5 2 1
4 5 3 2 1
5 4 3 2 1

Получены ровно те же $11$ расстановок, что и в таблице основного решения. Программа проверяет каждую возможность, а основное доказательство объясняет, почему хорошие расстановки имеют именно такую структуру.

$11$

Наибольшее число заставляет обе соседние части убывать, а второй запрет дополнительно запрещает пропуски по величине в левой части.

При запрете троек полезно сначала закрепить самое большое или самое маленькое число: оно превращает часть запретов в условия на пары.

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

После получения необходимой структуры доказывайте и обратное: каждая построенная по ней расстановка должна проходить все исходные запреты.

Доказаны необходимость и достаточность структуры, взаимно однозначное соответствие с пустым блоком или интервалом, отсутствие двойного счёта. Полный перебор 120 перестановок и всех 10 троек индексов каждой подтвердил 11 и распределение 1,4,3,2,1.