ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109869
Темы:    [ Упаковки ]
[ Метод координат в пространстве (прочее) ]
[ Куб ]
[ Четность и нечетность ]
[ Обход графов ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

N³ единичных кубиков просверлены по диагонали и плотно нанизаны на нить, после чего нить связана в кольцо (то есть вершина первого кубика соединена с вершиной последнего). При каких N такое ожерелье из кубиков можно упаковать в кубическую коробку с ребром длины N?


Решение

  Выберем в ожерелье какой-нибудь кубик и отметим его номером 1. Затем занумеруем остальные кубики по порядку, двигаясь вдоль нити в одном из двух возможных направлений. В кубике с номером n обозначим через An ту принадлежащую нити вершину, которая примыкает к предыдущему кубику.
  Выберем систему координат, совместив начало с вершиной коробки, направив оси вдоль её ребер и взяв в качестве единицы длины длину ребра кубика. Если ожерелье упаковано в коробку, то принадлежащие нити вершины каждого кубика имеют различные по чётности абсциссы. Значит, сумма этих двух абсцисс для каждого кубика – нечётное число. Следовательно, в случае нечётного N сумма всех этих абсцисс по всем кубикам – также нечётное число. Но каждая абсцисса повторяется дважды: каждая вершина An принадлежит двум кубикам. Значит, указанная сумма чётна. Таким образом, при нечётном N упаковать ожерелье в коробку невозможно.
  При чётном N в каждом кубике проведём диагональ, связывающую вершину вида  (ч, ч, н)  (то есть вершину, у которой первые две координаты чётны, а третья – нечётна) с вершиной вида  (н, н, ч).  Рассмотрим граф, образовавшийся на вершинах такого вида. Нетрудно понять, что он связен. Кроме того, каждая вершина внутри куба соединена с восемью вершинами, на грани – с четырьмя, а на ребре – с двумя вершинами. Следовательно, по известному критерию (см. решение задачи 30806), в этом графе существует цикл, проходящий по каждому ребру ровно один раз. Уложив кубики в порядке обхода этого цикла так, что просверленная диагональ каждого попадёт на соответствующее ребро, получим требуемую укладку нашего ожерелья.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1995
Этап
Вариант 4
Класс
Класс 10
задача
Номер 95.4.10.7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .