Задачка с IV кубка памяти Колмогорова для 8–9 классов.

[lexus c.]

На клетчатой бумаге отмечены 49 узлов сетки, расположенные в виде квадрата 6 × 6. Какое минимальное число единичных отрезков с концами в отмеченных узлах нужно провести, чтобы между любой парой соседних узлов был путь не длиннее 3?

[TOTAL]

Каков шаг сетки?
Что такое "соседние узлы"?

[ha]

52. Доказывать-то почти нечего.

[lexus c.]

TOTAL в сообщении #317852 писал(а):

Каков шаг сетки?
Что такое "соседние узлы"?

Насколько я понял, шаг сетки предполагается равным единице, а соседними считаются узлы, расстояние между которыми по горизонтали или вертикали равно 1.

-- Вт май 11, 2010 11:48:12 --

ha в сообщении #317895 писал(а):

52. Доказывать-то почти нечего.

Да, 52 у меня тоже получилось, но вот доказать минимальность не получилось.

[Ales]

А у меня 54.

-- Вт май 11, 2010 14:12:02 --

Есть построение с 54 и вроде-бы доказательство что меньше нельзя.
Но правильно ли?

-- Вт май 11, 2010 14:12:37 --

Есть ли построение с 52? Если есть, то я что-то упустил.

[lexus c.]

Ales, ниже мой вариант.

[ИСН]

Узлы на концах внешних завитков нарушают условие.

[venco]

lexus c. в сообщении #318048 писал(а):

Ales, ниже мой вариант.

И какое получилось расстояние между точками (1,0) и (2,0)?

-- Вт май 11, 2010 10:56:08 --

ИСН в сообщении #318050 писал(а):

Узлы на концах внешних завитков нарушают условие.

Хотя, если завитки сделать "наружу", а не "внутрь", вроде получится правильное решение.

[Ales]

lexus c. в сообщении #318048 писал(а):

Ales, ниже мой вариант

Здорово. У меня есть доказательство, что меньше 52 никак.
(Хотя у меня было и для 54 .)

-- Вт май 11, 2010 18:04:22 --

ИСН в сообщении #318050 писал(а):

Узлы на концах внешних завитков нарушают условие.

Можно перенаправить. У меня внутри не получилось придумать свастику.

-- Вт май 11, 2010 18:06:23 --

Для 52 было доказательство, не мог придумать картинку, тогда придумал доказательство для 54 - неверно.

[lexus c.]

venco в сообщении #318051 писал(а):

Хотя, если завитки сделать "наружу", а не "внутрь", вроде получится правильное решение.

Да, простите, ошибся, рисуя это на компьютере, и даже не проверил. Изначально было так, как Вы заметили, будет правильно:


-- Вт май 11, 2010 18:10:15 --

Ales в сообщении #318057 писал(а):

Здорово. У меня есть доказательство что меньше 52 никак.

Опубликуете? :)

[Ales]

lexus c. в сообщении #318064 писал(а):

Опубликуете? :)

Если нужно и Вы просите, то да.
Доказательство не очень длинное.
Мне самому интересно проверить годится ли оно.
И есть ли другие способы?

Напишите более определенно и я сразу же здесь его выпишу (а то вдруг кто-нибудь хочет сам порешать).

[lexus c.]

Ales, напишите, пожалуйста. Может, серым шрифтом, чтобы тот, кто не хочет случайно прочитать решение, был спокоен.

[Ales]

lexus c. в сообщении #318074 писал(а):

Ales, напишите, пожалуйста. Может, серым шрифтом, чтобы тот, кто не хочет случайно прочитать решение, был спокоен.

Возьмем полную решетку - 84 мостика и будем их убирать по одному.
Каждый убранный мостик оставляет после себя лужу.
Если убрать мостик с краю, лужа поглощает одну клетку, если убрать мостик внутри - лужа забирает две клетки.
Требование о пути хотя бы в три мостика разрешает убирать мостики только по краю или внутри суши.
Всего 36 клеток. Нельзя убрать больше 36 мостиков, ведь каждый новый мостик ведет к потере клеточки (единицы площади).
Внутри есть четыре клетки - центры четырех квадратов 3х3, изолированные друг от друга.
Либо они остаются не залитыми водой и тогда мостиков можно убрать меньше 36,
или они заливаются и есть мостики убранные изнутри.
Поскольку все равно в каком порядке убирать мостики, можно начинать изнутри с этих центров и тогда мостики убранные с краю этих центральных клеток отбирают сразу по две клетки.
Значит всего можно убрать не более, чем 32=36-4 мостика.
84-32=52 осталось.

[lexus c.]

Ales в сообщении #318090 писал(а):

Если убрать мостик с краю, лужа поглощает одну клетку, если убрать мостик внутри - лужа забирает две клетки.
Требование о пути хотя бы в три мостика разрешает убирать мостики только по краю или внутри суши.

Вот этого я не понял. По краю и внутри суши можно, вне нельзя, но ведь вне нет мостиков. Или что это за вне такое?

[Ales]

lexus c. в сообщении #318098 писал(а):

Ales в сообщении #318090 писал(а):

Если убрать мостик с краю, лужа поглощает одну клетку, если убрать мостик внутри - лужа забирает две клетки.
Требование о пути хотя бы в три мостика разрешает убирать мостики только по краю или внутри суши.

Вот этого я не понял. По краю и внутри суши можно, вне нельзя, но ведь вне нет мостиков. Или что это за вне такое?

Нельзя убирать мостик, у которого с двух сторон лужи.
Когда убираешь мостик, две точки, которые он раньше соединял должны быть соединены тремя мостиками.
Значит этот мостик был на суше.