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

[TOTAL]

На место каждого стертого ребра положим конфетку. Каждую конфетку подарим граничащей с ней клетке, а именно той, которая граничит ровно с одной конфеткой. Если клетка (2,2) получит конфетку, то одна из её соседок не получит. Т.е. по крайней мере 4 клетки останутся без подарка.

[lexus c.]

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

На место каждого стертого ребра положим конфетку. Каждую конфетку подарим граничащей с ней клетке, а именно той, которая граничит ровно с одной конфеткой. Если клетка (2,2) получит конфетку, то одна из её соседок не получит. Т.е. по крайней мере 4 клетки останутся без подарка.

TOTAL, а не могли бы вы пояснить ваше решение? Мне просто кажется, что оно доказывает, что минимальное количество рёбер не более 52, а не не менее.

[TOTAL]

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

TOTAL, а не могли бы вы пояснить ваше решение? Мне просто кажется, что оно доказывает, что минимальное количество рёбер не более 52, а не не менее.

Если по крайней мере 4 клетки останутся без конфетки, то конфеток (стёртых рёбер) не более 32, а оставшихся рёбер не менее 52 (=84-32)

[lexus c.]

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

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

TOTAL, а не могли бы вы пояснить ваше решение? Мне просто кажется, что оно доказывает, что минимальное количество рёбер не более 52, а не не менее.

Если по крайней мере 4 клетки останутся без конфетки, то конфеток (стёртых рёбер) не более 32, а оставшихся рёбер не менее 52 (=84-32)

Но ведь это требует доказательства того, что каждая конфетка будет подарена по крайней мере одной клетке. А вдруг найдутся такие, которые ни одной не подарены?

[TOTAL]

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

Но ведь это требует доказательства того, что каждая конфетка будет подарена по крайней мере одной клетке. А вдруг найдутся такие, которые ни одной не подарены?

Конфетка лежит на месте отсутствующего ребра. Между концами этого ребра (по условию!) есть путь по трём другим ребрам, т.е. по трём ребрам правой или левой (или и той и другой) по отношению к конфетке клетки. Вот одна из этих клеток и возьмет конфетку.