Задача MathCat 2019 ("жёлтый" уровень сложности, задача 10)

[worm2]

gevaraweb в сообщении #1423089 писал(а):

>30 ноября 2019 года состоится ежегодный математический флешмоб MathCat

Понравилась одна задача:

Лёня разрезал клетчатый квадрат $10\times 10$ по границам клеток на 3 части и сосчитал периметр каждой части. Все периметры оказались равны $N$. Найдите наибольшее возможное значение $N$.

P.S. Мне, кстати, не показалось, что "красный" уровень сложности превышает "жёлтый" (для самых высокобалльных задач).

[EUgeneUS]

$68$

[worm2]

Как у вас быстро получилось! Я долго решал. Ещё противно потом пример строить.

[EUgeneUS]

Неужели верно?
У меня в решении несколько дыр.

[worm2]

А... ну тогда наслаждайтесь дальше
Хотя у меня и само это число долго выходило.

[EUgeneUS]

Число (как оценка сверху) получается быстро: максимальный периметр фигуры, составленной из $N$ квадратов $1 \times 1$, равен $2(N+1)$.
Минимальная из максимальных фигур имеет $33$ коровы квадрата. Значит периметр фигур - $68$.

Строим пример.
Максимальный периметр имеет фигура, у которой ломанная, соединяющая центры соседних квадратов не имеет циклов. Таких фигур две - по $33$ квадрата.
Для фигуры из $34$, наиболее простой вариант - она должна иметь квадрат $2 \times 2$.
Строим внутри квадрата $10 \times 10$ "замейку" из $33$ квадратов. С одной и другой стороны от неё будет по "гребенке". Немного подбирая конфигурацию в районе концов "змейки" получаем требуемое.

[worm2]

EUgeneUS, мда. Почему-то до такого простого решения я не додумался.
Я сначала разбил квадрат на 100 частей (1 часть = 1 клеточке). У такого разбиения есть внешняя граница (которую мы по условию не трогаем) длиной 40, и есть внутренние границы общей длиной 180 единичных отрезков — границ между двумя соседними клетками. При стирании одного такого отрезка число частей либо совсем не уменьшается, либо уменьшается на 1. Таким образом, чтобы получить из разбиения на 100 частей разбиение на 3 части, мы должны стереть минимум $100-3=97$ отрезков. Если мы сотрём ровно 97 отрезков, останутся $180-97=83$ внутренние границы. При подсчёте суммарного периметра частей каждая из таких границ считается дважды, плюс внешняя граница единожды, получаем суммарный периметр $83\cdot 2+40=206$. Но это число не делится на 3. Ну давайте, значит, попробуем стереть 98 отрезков. Ага, вроде, получилось: $82\cdot 2+40=204=68\cdot 3$.
Потом я долго сражался с построением, не ведая, что фигура минимальной площади должна иметь 33 клетки. Ещё думаю, а чего это у них "жёлтый" уровень сложнее "красного"?

[EUgeneUS]

worm2
Сначала я тоже сделал один известный волшебный разрез, получив сложенное кольцо из $100$ квадратов. Потом нужно его порезать на три части, откуда получил число $206$. Но у меня даже не было доказательства, что оно максимально.

Потом догадался, что добавление одного квадрата к существующей фигуре может повлиять на периметр только четырьмя вариантами: $ +2, 0, -2, -4$.
Дальше было просто.